4 ms·
And you represent real numbers as Turing machines printing continuous streams of digits? Comparing two infinite streams produced by Turing machines is almost t
by gnull 4y ago
And you represent real numbers as Turing machines printing continuous streams of digits?
Comparing two infinite streams produced by Turing machines is almost the definition of halting problem.
- puffoflogic 4y agoWell yes, if you dig far enough into any uncomputable function you'll find something that is a version of the halting problem, by definition. That it's really close to the surface here but just deep enough that my answer never self-references or directly references TMs or any property thereof is precisely why I felt it was a good example.
- gnull 4y agoYour example has nothing to do with geometry, it's incomputable because of encoding you use for real numbers. There isn't anything special about diagonal line that makes it incomputable. I only skimmed the linked article very quickly, it seems to actually construct special shapes which that make it incomputable, not the encoding they chose. Your example is fun, I'm not against it. What I'm trying to say is that there's different ways to be geometric for an incomputable problem.