G12FCO -- Formal Computation

Lecture 20 -- Minimalist computers

You may have been thinking that Turing machines were already rather simplified models of real computers. Here we explore how far we can push the notion of simplicity!

Simple universal programs

We start with an observation. We already know that a Turing machine might just as well have a binary tape -- that is, where the only symbols used are 0 and 1. That being so, we can interpret the tape as a pair of binary numbers: for example,

...	0	1	0	1	1	0	1	0	0	1	0	0	0	1	0	0	1	1	1	0	...
left											^	right

can be read as the numbers

left = 100101101 [or 361], right = 00100111 [or 228]

by reading outwards from the tape position. Now suppose, for example, we write 1 and move left:

...	0	1	0	1	1	0	1	0	0	1	1	0	0	1	0	0	1	1	1	0	...
left										^	right

corresponding to the numbers

left = 00101101 [or 180], right = 100100111 [or 457].

We see that the effect has been to double right and add one [because we wrote one], and to halve left, and that the symbol now under the read head is 1 because the old value of left was odd.

In other words, these changes could be emulated by a chunk of program looking rather like:

	if state = 17 and symbol = 1
	  then if "left is odd" then nextsymbol = 1 else nextsymbol = 0 endif
	       left = left / 2
	       right = right × 2 + 1
	       nextstate = 23
	endif

repeated over every possible state and symbol, and the whole shoved into a simple loop which also assigns symbol = nextsymbol; state = nextstate before going around again. Now, this could be a universal Turing machine, so we don't need all that many states, and what we then have is a universal program, which can, in principle, do anything that any computer can do, provided merely that it is started with the correct values of left, right, state and symbol; what is more, it needn't be a big program -- recall that the `Minsky' UTM had only 23 states, though more than two symbols. We deduce that we could build a universal program from any computing language with the following capabilities:

test whether a number is odd, double a number, halve it, increment it, assign numbers to variables, test for equality, logical and of two conditions, if statements and loops.

The only catch is that two of the numbers could be extremely large [though not horrendously so -- no bigger than the active part of the tape!]. But most of these capabilities are redundant!

Very simple universal programs

Let's get rid of a few of capabilities. If we can decrement numbers, we don't need to be able to double them, halve them, or test for odd:

double:	halve:	test for odd:
temp = 0 while number > 0 do decrement number increment temp increment temp endwhile while temp > 0 do decrement temp increment number endwhile	temp = 0 while number > 0 do decrement number increment temp endwhile while temp > 0 do decrement temp if temp > 0 then decrement temp increment number endif endwhile	temp = 0 while number > 0 do decrement number increment temp endwhile while temp > 0 do decrement temp increment number odd = 1 if temp > 0 then decrement temp increment number odd = 0 endif endwhile

double:

halve:

test for odd:

temp = 0
while number > 0
   do decrement number
      increment temp
      increment temp
endwhile
while temp > 0
   do decrement temp
      increment number
endwhile

temp = 0
while number > 0
   do decrement number
      increment temp
endwhile
while temp > 0
   do decrement temp
      if temp > 0
	then decrement temp
	     increment number
      endif
endwhile

temp = 0
while number > 0
   do decrement number
      increment temp
endwhile
while temp > 0
   do decrement temp
      increment number
      odd = 1
      if temp > 0
	then decrement temp
	     increment number
	     odd = 0
      endif
endwhile

We can clearly use similar loops to multiply or divide numbers by any constants, and to copy numbers, and to compare them. We use only non-negative integers, so an assignment of zero can also be replaced by a loop:

while number > 0 do decrement number endwhile

and any other constant assignment by assigning zero and then incrementing an appropriate number of times. Also, the logical and is redundant:

if status = 17 then if symbol = 1 then ...

So, we now need:

increment a number, decrement it, if statements and loops.

What is more, the ifs and whiles can all be reduced to a very simple form, namely tests against zero. Now we still have several variables; we don't need so many, as for example the three variables a, b and c can be encoded into the one number jumbo = 2^a×3^b×5^c, with an obvious extension to more variables. Now, for example, decrementing b corresponds to dividing jumbo by 3, which we can again do by the techniques above. We can't reduce everything to a single variable, because we need the temp variable above as an auxiliary; but we can get down to two.

Conclusion: all we need in a programming language is the ability to

increment or decrement either of two integers, and do ifs and whiles based on whether they are greater than zero.

Everything else is icing on the cake! [There are various alternative formulations of this result, most using goto statements to replace the ifs and whiles, but you need either two sorts of goto, or else an extra known zero variable, and you also then need to be able to label parts of the program.]

Note that our universal program is now a fixed, and quite small [a few thousand lines, even after all the expansions] program written in a tiny language for a computer which has only this minimal instruction set and the capacity to store two (admittedly rather large) integers. This program, running on this computer, can do anything that any other program on any computer, or indeed, by the Church-Turing thesis, that any effective process, can do. It may just be a little slower.

Minimalist machines

We can use the above result to show that all manner of simple machines can be universal. For example:

The three-ones UTM

A UTM need only ever have three of the squares on its tape be non-blank. We put three ones on the tape as markers, separated by distances corresponding to the two integers. We increment or decrement the integers by moving the markers left or right, and test against zero by seeing whether the outer markers are adjacent to the middle marker.

The blank-tape UTM

If we give our TM three heads [which need no longer read or write anything!], we can use the head positions instead of the three ones, so the tape can be completely ignored, and might as well be blank. We can move the outer heads to increment or decrement the variables, the inner head merely needs to know whether it has collided with an outer head. Variant on this theme: use two heads and a singly-unbounded tape, all you need to know is whether you've hit the end of the tape.

The paper-tape UTM

We have been writing arbitrary symbols on our tapes. But, back in the days of paper tapes and punched cards, once you had punched a hole, it was difficult to stick the chad back in and unpunch it! Represent the integers m and n as follows on the tape:

blank

Now:

To increment n, find the first blank column and punch a hole.
To decrement m, find the leftmost m column and punch the third hole in it.
To decrement n, find the leftmost n column, punch a second hole therein and then decrement m
To increment m, find the leftmost n column, punch a second hole therein and then increment n.

Left as an exercise: in real life, paper tape equipment could either read the tape or punch holes in it, but not both, and the tape could only pass through in one direction. Tweak the above so that an unbounded reel of paper tape is threaded through a punch, thence to a reader, thence to a take-up spool, and can also be universal.

Discussion

Of course, no-one is really interested in building any of these simple machines to do real computations. What they show is rather that some very simple systems can exhibit very complex behaviour. You would not expect -- at least, you wouldn't after the last few lectures! -- to be able to look at a real computer doing a real calculation and be certain of explaining what it was doing; it is just too complicated, and we now know that the complication is not just ignorance but is a matter of principle. The example of the original UTM shows that the complexity can be removed from the computer, at the expense of complicating the data; a standard computer can do everything that a complicated computer can. The current examples show that we can even remove most of the complexity from a standard computer; some very simple systems indeed can exhibit all the complications of a standard computer. In other words, you cannot expect to look even at these very simple systems and be able to analyse what they are doing -- they can do anything, and could be doing anything, and there is no general way of finding out.

This seems to be as good a place as any to solve the halting problem:

top of page

G12FCO home page. border=0

Previous lecture. border=0

Coursework 5 .