- #1

nomadreid

Gold Member

- 1,707

- 222

The longer version: A simple proof that there are non-computable functions can be easily seen by the fact that there are only countable number of Turing machines but an uncountable number of functions. Fine. But then one might think that if one had an infinite amount of time, then one could solve the halting problem by simply testing each pair, (program, input). That is, the halting problem is for finite automata, that is, where the procedures are of finite length, so that by presenting this "solution", one is effectively re-defining Turing machines, allowing them to be defined in terms of formulas that are of infinite length, allowing the set of the number of Turing machines to have the same cardinality as the number of functions from the integers to integers, thereby throwing the proof based on infinities out the window. However, the standard proof of the existence of non-computable functions rests not on the comparable cardinalities, but rather on the contradiction one would have if one said that allowed the sort of indirect self-reference stemming from "a Turing machine able to handle the output of all Turing machines". Why wouldn't this proof still work in this case? Or if it would, why wouldn't you be able to just tick off all possibilities in infinite time?