Formal-ity and the Church-Turing thesis

[Steven D'Aprano]

On Tue, 08 Oct 2013 10:46:50 +0530, Ravi Sahni wrote:

> On Tue, Oct 8, 2013 at 8:47 AM, rusi <rustompmody at gmail.com> wrote:
>> I can only say how ironic it sounds to someone who is familiar with the
>> history of our field: Turing was not a computer scientist (the term did
>> not exist then) but a mathematician.  And his major contribution was to
>> create a form of argument so much more rigorous than what erstwhile
>> mathematicians were used to that he was justified in calling that math
>> as a machine.
>>
>> The irony is that today's generation assumes that 'some-machine'
>> implies its something like 'Intel-machine'. To get out of this
>> confusion ask yourself: Is it finite or infinite? If the TM were finite
>> it would be a DFA If the Intel-machine (and like) were infinite they
>> would need to exist in a different universe.
> 
> With due respect Sir, you saying that Turing machine not a machine? Very
> confusion Sir!!!

The mathematical ideal Turing Machine has an infinitely long tape, 
equivalent to infinite memory, and may take an unbounded amount of time 
to complete the computation. Since no *actual* physical machine can be 
infinitely big, and in practice there are strict limits on how long we 
are willing to wait for a computation to complete, in the *literal* 
sense, Turing Machines are not *actual* machines. They are a mathematical 
abstraction.

But in practice, we can wave our hands and ignore this fact, and consider 
only not-quite-Turing Machines with finite amounts of tape, and note that 
they are equivalent to physical machines with finite amounts of memory. 
One could even build such a finite Turing Machine, although of course it 
would be very slow. Or one can simulate it in software.

So in that sense, computers are Turing Machines. Anything a physical 
computing device can compute, a Turing Machine could too. The converse is 
not true though: a Turing Machine with infinite tape can compute things 
where a real physical device would run out of memory, although it might 
take longer than anyone is willing to wait.



-- 
Steven