A Geometrically Natural Uncomputable Function (2008)

https://xorshammer.com/2008/09/04/a-geometrically-natural-uncomputable-function/

by yamrzou • 4 years ago

49 25 4 years ago

yamrzou2• 4 years ago

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.

puffoflogic5• 4 years ago

This seems like way too much effort to find a "natural" non-computable function.

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.

gnull3• 4 years 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.

puffoflogic5• 4 years ago

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.

curtisf• 4 years ago

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

puffoflogic5• 4 years ago

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.

bawolff• 4 years ago

I'm confused, why is that non-computable? Seems like it would be very easy to compute.

puffoflogic5• 4 years ago

The equality of reals is undecidable.

carnitine• 4 years ago

Equality on reals is not computable.

rocqua5• 4 years ago

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.

ogogmad2• 4 years ago

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.

rocqua5• 4 years ago

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.

puffoflogic5• 4 years ago

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.

jakedata• 4 years ago

This was covered https://en.wikipedia.org/wiki/I,_Borg

knaekhoved• 4 years ago

since there are 2^{\aleph_0} functions from \mathbb{N} to \mathbb{N}

I think you mean N->Bool, not N->N

ghancock• 4 years ago

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....

rocqua5• 4 years ago

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.

i_k_k• 4 years ago

My favorite "natural" undecidable function is the the Post correspondence problem (https://en.wikipedia.org/wiki/Post_correspondence_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.

ogogmad2• 4 years ago

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.

yamrzou2• 4 years ago

What are the most attractive Turing undecidable problems in mathematics? — https://mathoverflow.net/questions/11540/what-are-the-most-a...

A Geometrically Natural Uncomputable Function (2008)

Related Stories