Non-computability of solutions of certain equations on digital computers (2022)

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.