Re: Smaller UTM than Rule110

From: Mcintosh Harold V. (mcintosh_at_servidor.unam.mx)
Date: 01/11/05 

Date: Tue, 11 Jan 2005 01:44:43 +0000 (UTC)

"Tim Tyler" <tim@tt1lock.org> wrote in message
news:IA4AuK.n2q@bath.ac.uk

> Do you consider every machine which is Turing-equivalent
> to be a Turing machine?

What I personally consider may not be what someone else
would say; also consider that informal discussion may not
be what one would wrinte in a formal presentation.

On one level, there are variants on the "checking squares
on a roll of paper" theme wherein the tape can be erased
or not, whether multiple tapes can be used, dimensionality
of the writing surface varies, many or few states and
symbols can be used, and so on. Some results are probably
pure playing; others such as the exchange of states for
symbols are both interesting and useful. The essential
equivalence of quite a few of these variants has been
studied and documented; the results may have been foreseen,
nevertheless it is reassuring to have them.

On another level, the whole mechanism changes: think of
Gödel numbers, the Lambda Calculus, Markov Algorithms,
Post Systems, and even WireWorld and IBM 709's. Still,
they all compute the same things and give the same
results, which leads to Church's Thesis, that there is
only one kind of computation, or Turing's thesis, that
his little machine does it. On a practical level, they
all compute the same things because the core mechanism
of any of them can be programmed in the others, so it is
never necessary to compare the actual computations.

> If so, why does the term "Turing equivalent" exist?

I guess, it is because of this other level. Would you
say that factoring large primes is the same as scribbling
tally marks on a roll or paper? Or just that you can
(presumably) solve the same problems get the same results
either way?

> Why don't all machines that can compute the same functions
> as Turing machines get classified as *being* "Turing machines" -
> rather than being merely "Turing equivalent".

I doubt that Post would have liked that!

- hvm 

-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG