🚀 go-pugleaf

pete@jura.uucp (Pete Bevin) writes:

>You can get away with four instructions in the following (rather
>inefficient) Turing-Machine-equivalent architecture.  Allow yourself a
>number of registers, each of which can hold large enough numbers for
>what you want to do.  Then, you only need:

>	Z(register):        Zero a register
>	S(register):        Increment a register (`S' for `successor')
>	T(r1, r2):          Transfer value from r1 to r2
>	J(r1, r2, address): Jump to address if r1 and r2 hold the same
>			    value.

>You wouldn't want to program it, but I guess it's fairly easy to reason
>mathematically about it.

The efficiency of such a machine is horrendous even compared to the
one-instruction machine (reverse subtract and skip on borrow). On the
latter you are at least able to do most arithmetic only about ten
times slower than a "normal" processor. The main limitation of the
latter is the lack of bitwise logic operations. Though these can be
simulated using subtraction, this is horribly slow (though not as bad
as on the 4 instruction machine above). If we make the single
instruction capable of both logic and arithmtic at the same time we
are home. A very general instruction would be

	x:=(a-b) and not (c>>d), skip on borrow

but that has 5 addresses. We can reduce this to 4 by letting x be
equal to one of the arguments, say b and to 3 by replacing d by a
constant, say 1. The latter makes arbitrary shifts more expensive. One
could consider to make the shift interact with the borrow flag, but I
think that would only complicate things.

One could consider what we the purpose of a one-instruction machine
is, apart from proving it can be done. None of the above machines will
be substantially smaller than normal machines if built in hardware, so
this is not a good reason. The code density will be horrible, as you
need more instructions and these are not very much smaller, if at all
(as they need memory operands).

So here is a challenge: design a machine that uses no more than 4 bits
per instruction (including operand fields), is Turing complete, not
terribly inefficient and which can be built using far less hardware
than current microprocessors. The latter would make it suitable for
massively parallel systems.

	Torben Mogensen (torbenm@diku.dk)