Re: Turing Machines and Physical Computation

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 11/20/04 

Date: Sat, 20 Nov 2004 20:22:36 GMT

"Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message news:...
>
> "Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message
> news:...
>>
>> "Eray Ozkural exa" <examachine@gmail.com> wrote in message
>> news:320e992a.0411192203.273c945b@posting.google.com...

>>> The latter camp has the precise terminology.
>>>
>>>> There is no
>>>> physical time constraint applied to when the calculation has to be
>>>> completed.
>>>
>>> If you mean *any* computation. But a Turing Machine is a *particular*
>>> computer. Not just *any* computer. Let's pay attention to our
>>> language.
>>>
>

http://www.mulhauser.net/research/tutorials/turing/
"The capabilities of Turing Machines, Universal Turing Machines, and finite
automata are easily confused, and usage outside the specialist literature
doesn't help.

Of the three, Universal Turing Machines are the most powerful. The Universal
Turing Machine was originally described independently but equivalently by
Alan Turing and Emil Post (see Davis 1965 or van Heijenoort 1967 for the
original papers). It is a general purpose digital computer which can
simulate any other digital computer. Formally, this means that for any other
computer M, a program p for M can be prefixed with a fixed length segment of
code s for Universal Turing Machine U such that sp causes U to perform the
same computation as p for M. The fixed length segment s just tells U how to
simulate the behaviour of M. This is much like the piece of software which
enables a Macintosh personal computer to emulate computers based on an
entirely different Intel chip set and thus to run their software unmodified.
It is widely -- and incorrectly -- held that a Universal Turing Machine can
simulate any physical process at all.

The name 'Turing Machine' is often used to include all kinds of Turing
Machines (Universal, uniform, non-uniform, oracle machines, etc.), but used
narrowly it simply picks out the class of ordinary Turing Machines which
lack the universal computational abilities described above.

Finally, the class of finite automata is set apart by the fact that they may
exist in only a finite number of distinct states. Unlike the Universal
Turing Machine, which may write any of an infinite set of binary strings on
its infinitely long tape, finite automata can display only a strictly finite
number of distinct states. Whereas the Universal Turing Machine can, for
intance, enumerate infinitely many natural numbers by virtue of its
unlimited tape capacity, any finite automaton for enumerating natural
numbers will always be limited by some largest number beyond which it cannot
continue.

Relations Between Computation Models
Their finiteness guarantees that for any finite automaton, there exists some
Turing Machine which can calculate the same function (i.e., which can
simulate it). Likewise, the definition of Universal Turing Machine
guarantees that for any Turing Machine, any Universal Turing Machine can
simulate it. Similarly, any Universal Turing Machine can simulate any finite
automaton. Some Universal Turing Machines running particular programs
compute functions equivalent to those computed by less powerful
(non-universal) Turing Machines or even finite automata, but no program can
give a non-universal Turing Machine universal power, and no finite automaton
has universal power."

Relevant Pages