Non-computability of solutions of certain equations on digital computers (2022)
A 2022 math paper on “Non-computability of solutions of certain equations on digital computers” prompts debate over a classic result: that there exist continuous, computable functions whose derivatives are uncomputable. Commenters unpack how this is constructed using ideas from the halting problem and computable analysis, and why such functions are extremely unlikely to be physically realizable despite being well-defined mathematically. The conversation broadens into what computable real numbers are, why basic operations like equality and ordering on them can be undecidable, and what all this implies (or doesn’t) for analog, quantum, and physical computation.
Significance of the result
- Central question: is a computable continuous function with an uncomputable derivative “big news” or just a pathological curiosity.
- Several commenters lean toward “parlor trick / nothing-burger”: mathematically cute, but not revealing deep new facts about computation.
- Others stress it is still interesting that such behavior is possible within smooth analysis, even if not physically realizable.
Intuition for a computable function with uncomputable derivative
- Computability of a real‑valued function is framed as “approximable to any desired precision by an algorithm.”
- Construction idea: encode a recursively enumerable but undecidable set into the derivative using many tiny “bumps” in the graph.
- The bumps get exponentially smaller and narrower as you go along a computable enumeration of the set, keeping the function itself easy to approximate.
- To approximate the derivative at a point, you’d need information about the entire infinite pattern of bumps, effectively solving an undecidable problem.
- This explains why numerical differentiation can fail even when numerical evaluation is straightforward.
Physical realizability and “uncomputable physics”
- Several comments question whether such functions or PDE solutions can exist as physical processes.
- Arguments: real physics has finite precision, Planck‑scale limits, and likely cannot implement such extreme constructions.
- Some note that whether spacetime is truly continuous and real‑valued is itself an assumption, not experimentally provable.
Computable reals and (un)decidable properties
- Discussion of computable reals: numbers given by algorithms that approximate them to arbitrary precision.
- Key points:
- Equality and ordering on computable reals are, in general, undecidable; only inequalities are semidecidable.
- This connects directly to the halting problem via reals whose binary expansion encodes machine behavior or open conjectures.
- There is debate and clarification around what “decidable” vs “semidecidable” means in this context.
Differentiation, integration, and numerical practice
- Differentiation as an operator on computable functions can be noncomputable; an example family is sketched using smooth functions converging to zero with nonzero derivatives at a point.
- In contrast, integration over reals is said to be computable via interval arithmetic and Darboux sums.
- Some argue this has little practical impact: it concerns highly pathological inputs unlike those arising in standard scientific computing.
Measure, randomness, and typical reals
- Side discussion: rationals in [0,1] have measure zero, so a “random real” is almost surely irrational and in fact uncomputable.
- This is used to highlight how unintuitive real‑number probability and exact equality are, and why physical measurements never access “inaccessible” reals.