23 ms·

Not an expert on the Church-Turing thesis, but I suppose to find a counterexample, one has to be rigorous in defining the problem. And defining the problem incl

Not an expert on the Church-Turing thesis, but I suppose to find a counterexample, one has to be rigorous in defining the problem. And defining the problem includes defining the output. If the problem is "compute and output the decimal representation of the square root of two", then neither the human nor the Turing machine can do it in finite time, because that decimal representation is infinite. In fact, as far as I know this falls out of the scope of the Church-Turing thesis because most definitions of algorithms include that they must run in a finite number of steps, so there is no algorithm to do that. If the problem is "compute and output a symbolic representation of the square root of two" (in some symbol system where it is finite), then the human and the machine can both do it. If the problem is "compute and output a segment whose length is sqrt(2) times the length of this segment"... I don't think that's what computation is about. You might as well claim the Church-Turing thesis is false because a Turing machine cannot wave its hand.

andrewla 8y ago
The problem is that the Church-Turing thesis is not rigorously defined, and it was in the attempt to rigorously define the parameters that the research in the video was done. I think that qualitatively we can agree that the ruler-and-compass construction of the square root of two is an algorithm. It's a repeatable procedure that can be described in a finite set of steps, and will always yield a provably correct answer. Whereas "waving a hand" is not an algorithm, but the same qualitative definition. The speaker wrote a paper that proved the Church-Turing thesis for sequential algorithms, primarily by defining in strict terms what a sequential algorithm is. Ruler-and-compass constructions are not sequential algorithms by this definition, and the difficulty in specifying the parameters for a generalized "algorithm" is apparently what leads him to the conclusion that the Church-Turing thesis cannot be true in general.

andrewla 8y ago

The problem is that the Church-Turing thesis is not rigorously defined, and it was in the attempt to rigorously define the parameters that the research in the video was done. I think that qualitatively we can agree that the ruler-and-compass construction of the square root of two is an algorithm. It's a repeatable procedure that can be described in a finite set of steps, and will always yield a provably correct answer. Whereas "waving a hand" is not an algorithm, but the same qualitative definition. The speaker wrote a paper that proved the Church-Turing thesis for sequential algorithms, primarily by defining in strict terms what a sequential algorithm is. Ruler-and-compass constructions are not sequential algorithms by this definition, and the difficulty in specifying the parameters for a generalized "algorithm" is apparently what leads him to the conclusion that the Church-Turing thesis cannot be true in general.