``` Subject: Re: on the relations of traditional CS theory to modern programming practice From: rpw3@rpw3.org (Rob Warnock) Date: Sat, 20 Oct 2007 20:07:12 -0500 Newsgroups: comp.lang.lisp,comp.lang.functional Message-ID: <reSdndm0kZndO4fanZ2dnUVZ_smnnZ2d@speakeasy.net> ```
```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

```