5 ms·

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 i

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.

rocqua 4y ago
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.

rocqua 4y ago

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.