A Geometrically Natural Uncomputable Function (2008)
xorshammer.com
xorshammer.com
In short, imagine I give you a set of dominoes that have strings on the top and the bottom. E.g.:
D = { banan/b , 0/an, a/a } (Where 0 is the empty string.)
A solution is a sequence of dominoes selected from D with replacement such that the string made up of the tops and the bottoms are the same. In the case of D, the sequence:
[banan/b , 0/an, 0/an, a/a]
is a solution. Solvable(X) = 1 if there exists a non-trivial solution for X and = 0 if not. So Solvable(D) = 1.
Solvable(X) is undecidable. Like a lot of these kinds of problems, the proof is gross, but the basic intuition is that I can encode the compute history of a Turing machine in a set of dominoes so that there is a solution iff the machine halts.
What are the most attractive Turing undecidable problems in mathematics? — https://mathoverflow.net/questions/11540/what-are-the-most-a...
But the question "is this function computable" is sensible to ask for any function N -> N.
I think you mean N->Bool, not N->N
I think this function R x R -> 2 is much simpler but satisfies the requirements:
f(x,y) = 1 if x = y. f(x,y) = 0 otherwise.
This has an obvious, natural geometric interpretation as the indicator function of the diagonal of the Cartesian plane.
Comparing two infinite streams produced by Turing machines is almost the definition of halting problem.
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.
A real number, in general, requires an infinite number of bits to describe, so it cannot be used as the input to an algorithm in standard models of computation such as Turing machines.
However, the version where the numbers have finite representations (such as floating point, fixed point, or rational numbers) are trivially computable.
There are results for particular finite representations of certain kinds of real numbers, such as https://en.m.wikipedia.org/wiki/Richardson%27s_theorem which applies to the equality of expressions involving arithmetic, exponentiation, and trigonometry, but I don't think this is clearly a geometric problem since the space of such mathematical expressions doesn't really have any obvious geometry
Which is why any charitable, non-sarcastic reading of my comment would take it to be referring to a subset of reals which are compatible with TMs and which make the claim true, instead of pointing out every possible way to misinterpret my comment deliberately. Be better.
Yes, they could have made their comment more accessible and mentioned the encoding (but I think then the problem may have sounded less "natural", since you'd have Turing machines mentioned). But you also could have noticed you're building a strawman argument, and instead just asked how does one encode Reals. Heuristics: if other person's argument sounds too absurd, there's a chance you're misunderstanding something.
Sure, charitable readings of informed readers will find it obvious. But less informed readers, or skeptical readers, will see the wrong interpretation. For a skeptical reader to then think "since they state its obvious, perhaps they refer to the general uncomputability of the reals", is not surprising.
Regarding the actual construction, once its well formulated, it becomes a lot less 'natural'. Since the definition is already taking about computable (or representable) reals, it is much less surprising that the result is a non-computable function. The beauty of the example is that the definition of the function never refers to any ideas from computational theory. Hence the article serves as a counter example to the theory "You never get uncomputable functions in fields outside of computational theory".
One easy definition of the reals is that each 'convergent' sequence of rational numbers defines a real number. Two sequences define the same real number when the sequence of differences converges to 0.
In this setting, the problem of deciding if two real numbers are equal is the same as deciding if a specific sequence converges to 0. Apparently there are 'reasonable' sequences for which this is an undecidable problem.
I'm afraid I can't give you two reals whose equivalence is undecided. I expect it will involve some rather weird descriptions of real numbers. I would love if someone could give some examples.
That said, I can give a suggestive non-rigorous example, where you can see the decider would have to have special knowledge to resolve. Consider encoding (a subset) of the reals as inputs to a universal TM, s.t. the programs they encode give Cauchy sequences of rationals with modulus of convergence 2^-n. Note that in general the only thing the putative equality decider can do (without disallowed special knowledge) is to query these input functions at specific indices. Suppose I give the decider what seems to be the easiest possible input: a(n) = b(n) = 0. There is no sequence of inputs n which can be fed to these functions such that they are definitely equal. If N is the largest n given yet, then it is still possible that a(n) represents the real 2^-(N+1) and b(n) the real 0. No finite decider program can correctly answer for infinitely many such pairs.
I suspect the additional rigor is mostly a matter of showing why 'special knowledge' is not allowed. That is certainly where my main objection lies. The 'decider' should get to inspect the Turing machine, and hence be able to prove things about them. I do find it plausible that something similar to the halting problem makes it impossible, but proving that does not seem trivial.
I also think a construction like: Take a binary sequence x_i where x=1 if 2i+1 is a perfect number, 0 otherwise. Make that into a real number x in the interval [0, 1] in the standard way. x here is certainly a computable real number.
Now the question is, does x equal 0.
The question 'do perfect odd numbers exist' is unanswered. If it were undecidable, then the above equality would be undecidable as well. It doesn't seem impossible to find a construction like the above, but for a known undecidable problem.