Goldin and Wegner: "The Interactive Nature of Computing" (2008)

By definition, Turing machines either halt after writing a finite amount of output, or do not halt at all. This means that if we feed them an infinite input tape, they will either ignore an infinite tail of it, or never halt. From an algorithmic perspective, all the non-halting computations will be categorized as equivalent.

This is, however, not a very good model with respect to many important types of computation. For instance, operating systems are non-halting computations, but it seems weird to consider them all equivalent on the grounds that they "have no output." So it would make sense to use a more fine-grained theory to handle such situations.

New Concepts, New Problems

Once we take this different perspective, there are a lot of conceptual pitfalls to beware of. For instance, the 1-tape Turing machine will no longer be equivalent to the 2-tape machine when the inputs are allowed to be infinite: The usual simulation tricks such as using every second slot to simulate a second tape doesn't work because they require infinite time for preprocessing. When the input is infinite, the 1-tape machine is thus effectively finite-state.

This means that we should be careful about what we mean when we refer to "the Church–Turing hypothesis." There are several different notions of equivalence on the table, and many of these introduce new distinctions. Machines that we are used to think of as "equivalent to the Turing machine" are no longer guaranteed to be equivalent to Turing's original 1-tape machine. We should thus be more careful than usual in stating exactly what we mean by "the" Turing machine, and how we compare it to other architectures.

Equivalence Relations on Sets of Machines

If we want to determine whether two non-halting computations are equivalent, we can't simply check for equality of the outputs, since there will never be any output. There are several alternative options, but one of them is to introduce a limit concept for computations, and then define equivalence as equality in the limit.

Such a limit concept could for instance be the following:

• A tape t converges to a state w if any square on t eventually contains the same symbol as w — i.e., for all i there is a k such that for all j ≥ k, t(j) = w(j). A computation converges to a state w if its output tape does.
  

When a computation converges, any finite segment of the output tape will thus remain static after a finite amount of time. If we further require output tape to be unidirectional and write-only, this definition corresponds to an ongoing computation occasionally invoking a print command.

Machine Components

In addition to stating explicitly what notion of equivalence we  are using, we should further specify what type of machine we have in mind when we talk about "the" Turing machine. This means that we have to make the following decisions:

• How many storage devices (tapes) does the machine have, and which of these are infinite?
• In the initial configuration, do the infinite tapes contain only blanks from some point on? And if they do, can these tapes also contain arbitrarily long sequences of blanks elsewhere on the tape? (If they can, they will essentially have to be treated as infinite.)
• What commands to the tapes accept? For instance, are they unidirectional or bidirectional, and are they read-only, write-only, or read/write? (A stack defines a slightly more involved combination of these options.)
• Which tape is the designated output tape?
• Which tape is the designated input tape?
• What function defines the control flow?

I have written that the control flow is defined as a function because I think this makes the memory demands of the machine clearer. For instance, the processing unit of a finite state automaton can be conceptualized as a function with access to an external tape of finite length. By externalizing the memory components like this, we have to be more explicit about their size.

It should also be clear that once we have defined the different kinds of storage devices that we are interested in, we can combine them modularly in all sorts of ways. Just as in the classical theory, many of these combinations will yield equivalent machines, but not quite as often.

What About the Paper?

In the paper "The Interactive Nature of Computing," Dani Goldin and Peter Wegner make many of the above observations. Their starting point is not the difference between machines with finite and infinite inputs, but rather that of ongoing computations as opposed to closed input-output operations.

However, the two perspectives are equivalent as far as I can see, although it is difficult to assess because they refer to a different paper for technical details, and I haven't read that paper yet.

Along the way, they also refer to work by Jack Copeland, Peter Kugel, Jan van Leeuwen and Jiri Wiedermann for (what the text suggests is) additional mathematical detail.