|
== A paradoxical situation ==
Recently I have encountered a paradoxical situation. In the book of Lewis, H.R. and Papadimitriou, C.H. [1] on the page 246, the following Church-Turing thesis is formulated:
This is a duplicate post from [[Talk:Algorithm#A_paradoxical_situation]]. To keep the discussion in one place, please comment there is you are interested. — Carl <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 20:43, 19 March 2008 (UTC)
"''We therefore propose to adopt the Turing machine that halts on all inputs as the precise formal notion corresponding to the intuitive notion of an "[[algorithm]]."'' Nothing will be considered as an [[algorithm]] if it cannot be rendered as a Turing machine that is guaranteed to halt on all inputs, and all such machines will be rightfully called algorithms. This principle is known as the '''Church-Turing thesis'''."
As the conventional Turing machine does not in general satisfy this Church-Turing thesis, we come to a paradoxical statement:
''Turing machine refutes Church-Turing thesis''.
Indeed, a universal Turing machine cannot be "rendered as a Turing machine that is guaranteed to halt on all inputs."
By the way, if we take the original Turing machine described in the classical paper of Alan Turing (1936), as mentioned, we'll have more problems with the Church-Turing thesis.
[1] Lewis, H.R. and Papadimitriou, C.H. Elements of the Theory of Computation, Prentice-Hall, Upper Saddle River, N.J., 1998
With respect to all discussion participants, [[User:Multipundit|Multipundit]] ([[User talk:Multipundit|talk]]) 20:41, 19 March 2008 (UTC)
| 