[FOM] Re: On Physical Church-Turing Thesis

[Martin Davis]

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