# [FOM] Re: On Physical Church-Turing Thesis

Martin Davis martin at eipye.com
Sun Feb 8 18:29:33 EST 2004

Dmytro Taranovsky  wrote:

<<These claims are *not* due to Church or Turing. The thesis as
formulated by Church and Turing involves finite computation by human
mind without insight or ingenuity and without use of non-recursive
physical machinery. That thesis is vague because of ambiguities in
"without insight or ingenuity"; if these terms are defined narrowly,
then the thesis essentially becomes vacuously true.>>

In fact there is good evidence that Church and Turing both realized the
relevance of the "Church-Turing thesis" to physical devices. Here is Church
reviewing Turing's original paper:

<<[Turing] proposes as a criterion that an infinite sequence of digits 0
and 1 be 'computable' that it shall be possible to devise a computing
machine, occupying a finite space and with working parts of finite size,
which will write down the sequence to any desired number of terms if
allowed to run for a sufficiently long time. As a matter of convenience,
certain further restrictions are imposed on the character of the machine,
but these are of such a nature as obviously to cause no loss of generality
>>

Turing in a 1947 address emphasized the relation between the computers
being envisaged and his earlier work. For more on these topics see my paper:

The Myth of Hypercomputation,'' {\em Alan Turing: Life and Legacy of a
Great Thinker}, Christof Teuscher, ed., Springer 2004, pp. 195-212.

Copies available by email on request.

Martin



More information about the FOM mailing list