Formal-ity and the Church-Turing thesis
Steven D'Aprano
steve at pearwood.info
Tue Oct 8 03:50:14 EDT 2013
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
More information about the Python-list
mailing list