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