6. Example 2: A Turing machine

A: For the second example, I would like to describe a generic Turing machine as an evolving algebra.

Three universes of the EA, called Control, Char and Displacement, are nonempty finite sets. InitialState and CurrentState are distinguished elements of Control, Blank is a distinguished element of Char. CurrentState is a dynamic distinguished element; initially, CurrentState = InitialState. Another universe, Tape, is a countable infinite set; call its elements cells. Head is a dynamic distinguished cell. Move is a possibly partial function from Tape x Displacement to Tape.

Q: What kind of Turing machines are you talking about? Is the tape linear? Is it one-way infinite or two-way infinite?

A: The kind of Turing machine is determined by further restrictions on Displacement and Move. You can choose Displacement = {+1,-1}, and Move to be such that Tape with unary operations Move(c,+1), Move(c,-1) is isomorphic to natural numbers with the successor and (partial) predecessor operations. This will give you a model with a linear one-way infinite tape. You can choose Displacement and Move in a way that gives rise to two linear tapes or to one two-dimensional tape, and so on.

We need some additional basic functions though. A dynamic function TapeCont maps cells to characters, and functions NewState, NewChar and Shift map the cartesian product Control x Char to Control, Char and Displacement respectively. It is required that TapeCont(c) = Blank for all but finitely many cells c. The transition rules are as follows.

CurrentState := NewState(CurrentState,TapeCont(Head))
TapeCont(Head) := NewChar(CurrentState,TapeCont(Head))
Head := Move(Head,Shift(CurrentState,TapeCont(Head))

Recall that all rules fire every time in a simultaneous fashion.

Q: By the way, the usual definition of Turing machine is shorter.

A: What usual definition?

Q: A Turing machine is a quadruple, namely, a set of control states, a set of characters, a transition function and the initial state.

A: In isolation, this short definition does not really define Turing machines. For example, one cannot derive from that definition that a Turing machine has a tape. Recall that after giving the short definition, one proceeds to define configurations, etc. These additional definitions are absorbed by the general EA framework. The short definition provides, however, a convenient notation for Turing machines.

Q: You did not define what your Turing machines compute.

A: I have to repeat the usual definitions.

Q: As an exercise, let me list the integrity constraints: CurrentState belongs to Control, Head belongs to Tape, and TapeCont maps Tape to Char.

A: That is correct. Again all constraints are easy to check in advance and again they can be stated in the form t = true where t is a closed term.

Q: But the constraint on TapeCont is a universal statement: For every cell, the value of TapeCont is a character.

A: Taking for granted that the constraint is satisfied initially, it reduces to the constraint Char(TapeCont(Head)) = true.

Q: I guess, it isn't always so easy to check whether a constraint t = true will be eventually violated.

A: This is an undecidable problem. To prove this, modify the Turing machine example by introducing a subuniverse Nonhalting of the universe Control. In an obvious way, the halting problem for Turing machines reduces to the problem whether the constraint CurrentState belongs to Nonhalting is violated. But of course the Nonhalting universe is very artificial and unnatural. Often, constraints are checkable in advance. Certainly, your demon, able to evaluate a bounded number of closed terms at a time, should have no trouble to check, in each state, the validity of a constraint t = true.

Q: You defined the tape to be infinite. I prefer finite tapes growing if and when necessary.

A: The predefined geometry of Turing tapes makes the distinction somewhat artificial. In this connection it makes more sense to consider Kolmogorov-Uspensky machines [KU] with (finite at every moment) tapes of changing geometry. (We discussed KU machines once [Gu3].) The tape of a KU machine gives rise to a dynamic universe in a very natural sense. To handle this situation, we may use a countable universe Reserve (also dynamic) and an external distinguished element New subject to the integrity constraint New Reserve. Whenever it is required that the tape gets another cell, New is deleted from Reserve and added to the tape. Of course, when we evaluate New next time, it belongs to Reserve again. Actually, adding a new element to the tape requires some work because, contrary to Reserve, the tape has a relatively rich structure. Let me skip the details.

Q: By the way, the halting problem easily reduces to the following decision problem: Given an EA, tell whether it will eventually reach a state with contradicting updates. Thus, this consistency problem for EAs is undecidable. I imagine that for certain applications only consistent EAs are appropriate. What do you do?

A: Often very simple syntactic restrictions suffice to ensure consistency. Sometimes, it may be appropriate to require that, for each basic function f, the guards of different updates of f are mutually exclusive. This guarantees that no basic function is updated twice at the same step. (Since the problem of mutual exclusivity of given boolean formulas is co-NP complete, one may want to require some kind of explicit mutual exclusivity.) In general, every evolving algebra A can be modified into a consistent variant A' making 2 steps per each step of A and halting (with setting an error flag to true if desired) when A encounters inconsistency. The idea is to check the consistency of A 's transition rules in given state of A before executing them.