2 ms·
> The speaker would simply have to point to a concrete algorithm that can be performed by a person with pencil and paper but not by a Turing machine (or vice ve
by lmm 8y ago
> The speaker would simply have to point to a concrete algorithm that can be performed by a person with pencil and paper but not by a Turing machine (or vice versa).
Humans do all sorts of things that Turing machines don't (e.g. a Turing machine can't hold a pencil), so the question there is what constitutes an "algorithm" which comes right back to the definition of computation. Even an example that was obviously "computation" in the intuitive sense wouldn't make the Church-Turing definition "false", it would just mean that it defines something different from what we thought it defines.