X-Message-Number: 4010
Date: Wed, 15 Mar 95 11:25:56 EST
From:  (Perry E. Metzger)
Subject: Turing Machines

>From: 
>Subject: probability calculation
>
>Recently I suggested that feeling in animals might (for example)  require
>simultaneous real-time actions or conditions impossible for a Turing tape.
>John Clark responded, in effect, that the probability of this is virtually
>zero.
>
>Perhaps he would care to make this probability calculation explicit, or at
>least indicate clearly how he arrives at this conclusion.

I didn't read your original article, but anyone claiming that some
system we know of is capable of doing things that Turing machines
can't doesn't know anything about computability theory.

Turing machines with two tapes turn out to be provably equivalent to
Turing Machines. TMs with any finite number of tapes turn out to be
provably equivalent. TMs with a two-dimensional plane to work on turn
out to be equivalent. TMs with any finite number of heads turn out to
be equivalent. Arbitrary random access machines turn out to be -- you
guessed it -- equivalent to Turing Machines. In fact, any given trick
you can think of produces a machine that is provably equivalent to a
Turing Machine in the sense of being simulatable on a TM.

In fact, even Non-Deterministic Turing Machines are -- you guessed it
-- provably equivalent in computing power (although NOT in speed) to
Turing Machines.

The Church-Turing Thesis holds that Turing Machines are as powerful a
computing construct as you can produce. This is admittedly
non-provable but is believed the same way that people believe there is
a correspondance between Peano Arithmetic and the way that you can
count real world objects.

I would be very suprised to find a machine in our universe more
powerful than a Turing Machine.

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=4010