Chris F Clark <cfc@shell01.TheWorld.com> wrote:
+---------------
| Although I hate to participate in this thread, I have a simple
| question. Is it possible to prove that a machine which visits the
| tape only in sequential order is as powerful as a machine that can
| visit the tape non-sequentially, perhaps by appealing to multi-tape
| TMs in the argument?
+---------------
I don't think so. In fact, I think I can present a rather trivial
counterexample:
Let M be a multi-tape TM with N internal states and R rules
for which each of T tapes can only be visited in sequential
order [e.g., the forward direction]. Then it is not possible
for M to compute [that is, write onto (one or more of) the
tape(s) being used as the "output device"] a result which is
greater than N*R*T (and the actual limit might be much, much
smaller -- I'm just picking a "safe" value). For example, if
each of the T tapes starts out with a number of 1's representing
unary integers followed by infinite 0's, then it is not possible
for M to compute the product of those numbers if that result
would be greater than N*R*T [or whatever the actual limit is].
Whereas if as few as *one* of tapes is writable and reversable
[can both read & write and step both forwards & backwards],
then a TM with a fixed finite number of states & rules can
compute the product of the numbers on the tapes [or the square
of the number, say, if there's only one tape] no matter *how*
big that product might be!!
-Rob
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607