Halting problem encoded in computable distributions: computable PDEs can have noncomputable solutions
fkasummer · x · 2026-10-25
lusichu highlights that the halting problem can be encoded into a conditional probability over a computable joint distribution; fkasummer adds the related classic result that even computable differential equations can fail to have computable solutions.
The attached image is Pour-El & Richards' 1981 paper in Advances in Mathematics: the 3D wave equation with computable initial data can have a unique — but noncomputable — (weak) solution, i.e., computable input does not guarantee computable output.
More from Research
- Vik Paruchuri answers 'self-topped benchmark is suspect' with open audit — VikParuchuri · 2026-10-25
- Datalab benchmarks 17 open OCR models on OmniParseBench; Chandra OCR 2 tops at 90.1 — VikParuchuri · 2026-10-25
- Datalab releases OmniParseBench and ranks 17 open OCR models — VikParuchuri · 2026-10-25
- Proposal: report AUC only, or add a dev set to tune thresholds per eval — antoine_chaffin · 2026-10-25
- Adaptive Skill Granularity Framework Routes Coding Agent Skills at Runtime, Hits 100% Success — dair_ai · 2026-10-25
- Study: LLMs rewriting their own ARC-AGI-3 harnesss gain just 2.8 points, not significant — omarsar0 · 2026-10-25