   Next: The Argument From Irreversibility Up: COGNITION IS NOT COMPUTATION: Previous: The Computational Conception of

# Rudiments of Computational Reversibility

Computationalism relies upon automata like Turing Machines (TMs) to fix the concept of computation. But what's a Turing Machine? To some readers these automata will be old hat, but let's play it safe and ask cognoscenti to return with us to the elementary aspects of computability theory upon which the Argument From Irreversibility is built.

Put intuitively, TMs include a two-way infinite tape divided into squares, a read/write head for writing and erasing symbols (from some finite, fixed alphabet) on and off this tape, a finite control unit which at any step in a computation is in one particular state from among a finite number of possible states, and a set of instructions (= program) telling the machine what to do, depending upon what state it's in and what (if anything) is written on the square currently scanned by it's head. Formally speaking, a TM is a set, specifically a quintuple , where: S is a finite set (of states); is an alphabet containing the special ``blank" symbol b, but not the symbols L (for ``left") and R (for ``right"); is the initial state; is the halt state; and f is a transition function from to {h} {L, R}).

This formalism makes it easy to render the notion of a configuration of a TM precise, but an informal account will suffice for our purposes: We'll say that a configuration is composed of four pieces of information: first, the state the TM is in; second, information representing what's to the left of the square currently scanned by the read/write head; third, the single symbol being scanned; and four, the contents of the tape to the right of the head. In a moment, we'll concretize the notion of a configuration by explaining and analyzing the particular TM specified in Figure 1. But first some notation for computations: Let denote configurations. We write to indicate that TM M has moved ``in one step" from configuration to . For every TM M, is the reflexive, transitive closure of . A computation by some TM M is a sequence of configurations where such that  Figure 1: Gordon's 19 in 186

There are many ways to steamline the full set-theoretic description of TMs. One such method is the state diagram approach used in Figure 1. This TM, ``Gordon's 19 in 186," is designed to start on a 0-filled infinite tape and produce, after 186 steps, 19 1's. Let's ``hand simulate" an initial segment of the computation of Gordon's TM -- let's label the machine G -- so that we completely fix the core mathematical concepts. The alphabet used is simply 0, 1 . The initial state of G is 0 (represented by the node labeled 0), and at the outset we'll assume that the tape is filled with 0's. The first thing G does is check to see what symbol it finds under its read/write head. In this case it initially finds a 0, so the arc labeled with 0 R is taken, which means that the head moves one square to the right and the machine enters state 5. At this point, since there is another 0 found beneath the head, the 0 is changed to a 1, and the machine reenters state 0. It now finds a 1, and hence takes the arc labeled 1 R to state 1 (i.e., the machine moves its head one square to the right, and then enters state 1) -- etc. The machine's activity can be perfectly captured by a tedious catalogue of its configurations from start to finish, e.g.,          If this is your first exposure to TMs, you will doubtless be struck by how primitive and unassuming they are. But the surprising thing is that TMs apparently capture computation in all its guises. More precisely, whatever can be accomplished by way of an algorithm, by way of a programmed supercomputer, by way of a neural network, a cellular automaton, etc. -- whatever can be accomplished by any of these can be accomplished by a TM. Furthermore, we know that augmenting the architecture our TMs doesn't give them any additional power. For example, if we give a TM two tapes rather than one, nothing which was impossible for the one-tape machine becomes doable for the two-tape creature. (This is a fact we revisit below.) Usually, such a fact is established through a so-called ``simulation proof," the essence of which consists in showing that the new automaton can be perfectly simulated by the original one. Now, Bennett  has established that TM computation can be logically reversed in a ``useful" way. It was clear before Bennett that computation can be logically reversed in non-useful ways, and in fact this result is sufficient for our argument. Non-useful ways of reversing TM computation are easy to come by; here's one: First, go get some paper, a pencil, and an eraser. Next, watch a given TM M in action, recording each configuration through which it passes. Finally, using your list of configurations, build a new TM which goes from the last entry on your list to the first in such a way that it visits your entries in reverse sequence.

Though we are informal here, it should be obvious that (in keeping with the inaugural writings of Turing and Post, in which the notion of a human computist is primitive) we have here a straightforward algorithm, call it , for reversing computation. You are encouraged to try your hand at simulating on the TM shown in Figure 1. All you need is some patience, and, as we say, a pencil, an eraser, and sufficient paper.

If you're short of time, we suggest a shortcut constructive ``proof" as a substitute: Purchase the software ``Turing's World" , run one of the TMs that come bundled with this package, and then use the REVERSE command to step back through the configurations your selected machine has run. You can be sure that the existence of some such algorithm as is precisely what enables you to carry out this reversal using ``Turing's World" .

It will be helpful if we set off the relevant proposition as a theorem: Theorem 1. For every computation , there exists a computation which can be obtained from the original computation via some algorithm .   Next: The Argument From Irreversibility Up: COGNITION IS NOT COMPUTATION: Previous: The Computational Conception of

Selmer Bringsjord
Fri Sep 6 11:58:56 EDT 1996