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.
For the context, I was looking for an example of Gödel's incompleteness theorem that didn't involve self-referencing, because I felt that Gödel's example that relied on self-referencing (https://news.ycombinator.com/item?id=25115746) did not match what I pictured in my mind as a "normal" undecidable statement. It just felt like a fancy version of the “This statement is false” paradox, which wasn't what I hoped for.
So I found that link here: https://mathoverflow.net/a/4725.
This is what people here do not understand: This function is "natural" because it's a continuous function over R, which is not defined by explicitly referencing computability. Certainly you can come up with less interesting examples which are discontinuous, or which reference computability, but people in the area wouldn't be surprised or care.
knaekhoved your comment is dead which I think is unfortunate because it seems better to inform you than bury your comment so I'll reply here: the page did mean N -> N, given the context of the previous paragraph. You may have thought what you did if you did not know that Card(N)^Card(N) is equal to 2^Card(N) by the laws of arithmetic for cardinal numbers. If you have not encountered those before there are enough on Wikipedia to show that equality https://en.wikipedia.org/wiki/Cardinal_number#Cardinal_arith....
Besides the equivalence, computable functions are about more than just decision problems. Computable functions are a subset of N -> N. I suppose the confusion is that undecidability (very similar to uncomputability) regards decision problems of the form N -> Bool. This class of functions is also what P vs NP, and general complexity theory tends to focus on.
But the question "is this function computable" is sensible to ask for any function N -> N.
Without more setup, you haven't described a problem that would normally be classifiable as computable or non-computable.
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
> A real number, in general, requires an infinite number of bits to describe
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.
If you claim a construction is obvious and dispells confusion, that construction should not have any readings that are obviously wrong.
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".
You could have said it's a function CR x CR -> 2 to refer to the Computable Reals. Instead you explicitly made it about the reals R, making it hard to be charitable.
All the ways of encoding Reals that you mention in your comment are limited to Rationals. It seems like you just didn't know that one can encode Reals too, which puffoflogic assumed readers to know.
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.
Well 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.
Your 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.
This example is discontinuous, so it's not interesting. Discontinuous functions f:R->R or f:CR->CR (where CR means Computable Reals) are always not computable.
Its because the real numbers are actually quite weirdly defined (for good reasons).
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.
Can you give an example of two computable reals who'se equivalence is undecidable?
I get the theory behind why the problem in general is not decidable, but I would love a constructive proof by example.
The question is in error. Decidability isn't a property of specific inputs to a problem, it's a global property of all inputs to a problem. If I give specific inputs then you simply prove whether they are equal or not and then the algorithm just outputs a constant result, so this sub-problem is always decidable. (In general properties indexed by a finite domain are decidable, just by encoding all the answers.) This tells you nothing about whether the original problem is decidable.
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 found your suggestive example on wikipedia earlier. Sadly it was no more rigorous than your example, nor did it cite sources that have more rigor.
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.
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.