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

    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 Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607