Talk:Computability theory (computer science): Difference between revisions

Revision as of 00:43, 21 February 2008

Revision as of 20:41, 19 March 2008

Line 288:

For anyone keeping this article on their watchlist: there is currently an attempt at merging a number of articles on (non-)recursive/(un)decidable/(un)computable sets/languages/decision problems into a single, thorough article. The experiment currently sits at [[Recursive languages and sets]]. Comments are very welcome. [[User:Pichpich|Pichpich]] ([[User talk:Pichpich|talk]]) 00:43, 21 February 2008 (UTC)

== 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:

"''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)