Re: Do Write Once TM's Halt?

Patricia Shanahan <pats@xxxxxxx> writes:

Torben Ægidius Mogensen wrote:
...
TM's don't have infinite tapes, they have unbounded tapes. The
important difference is that the tape at all times has finite support,
i.e., that it is blank outside a finite range (the size of which may
change during execution).
...

I think infinite input tapes might lead to an interesting model of
modern computer services.

The traditional Turing machine models a single batch computation, in
which the TM gets all the input, and either computes some function of
the entire input, or fails to do so going into a loop.

Many computer programs now operate as services, required to produce some
results based on the input so far, but then continue to process more
input. At least conceptually, they go on running that way for ever, and
always expect to find more input. This is the case, for example, for
on-line machine learning algorithms, and for web servers.

Such an online TM will still not have infinite tape, as at any given
time only a finite number of tape cells have been written.

However, whether that is a useful model of computation, and its
implications if it is useful, are separate questions from write-once and
read-only behavior.

Online TMs (and other online machine models) have been studied, and
you can talk about online complexity which involves answer times after
each input instead of total computing time. So such machines are
definitely worth studying.

In terms of what you can compute, online machines are no more powerful
than offline machines, as you can emulate an online machine by at each
time step feeding an offline machine all input received up to the
current time. But the complexity measures may be different.

Torben

.