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