Next Previous Contents

5. Building the Turing Complete Coffee Machine

Do you pine for the nice old days, when men were men and build their own coffee machines?

This chapter is about assembling a smart, intelligent!, coffee machine. It will be a computer designed with a von Neumann architecture, comprised of a CPU, ROM/RAM and I/O and will also be suitable for generic use, a.k.a. Universal Turing Machine.

5.1 An adequate assembly language

Unlike other complex, but popular, systems that are either CISC or RISC, our machinery will be MISC: Mono-Instruction Set Computer!

Alas, our processor will understand just one command and yet, given enough memory and time, it is able to perform any action that your 3GHz Pentium IV could do, or just simulate it alltogether; It can solve any computable problem by running simple code like this: 


SBN     $mem1, $addr1
SBN     $mem2, $addr2
SBN     $mem3, $addr3
SBN     $mem4, $addr4
SBN     $mem5, $addr5
SBN     $mem6, $addr6
[...]

The magic command is called SBN $mem, $addr (Subtract and Branch if Negative), and does take the value of a memory cell $mem, subtract it from the accumulator (A is the only available register in this architecture) and store it back to the accumulator and memory $mem : [mem] <= A <= A-[mem]. If the result is negative, and only then, it jumps to the designated address $addr. If $addr points to the next command, there is no conditional jump. Now, with that command at hand you can subtract, add, zero memory addresses, move bytes around, multiply, compare and so on, so forth. What's best of all, you can easily build an optimizing compiler.

Voila. This is a great system for any Turing Complete problems plus, it is even simpler in coding than the original Turing Machine!

5.2 Hardware and interfacing

The great thing with this innovative MISC processor is that you need 0 bits to store the opcode of your commands. This makes your CPU much, much simpler: you only have to read a couple of operands each time. You might wish to extend the capabilities of your processor by extending the SBN instruction to 3 or 4 operands, so that it can directly load and store data from main memory. This is an exercise left to the reader; kudos to google.

The CPU diagram looks like this: 


<========= ADDRESS BUS ==============>
        =                =
        =  +---------+   =
        =  | CONTROL |   =
   +---------+  +-----------------+
   | ALU & A |  | Program Counter |
   +---------+  +-----------------+
        =  |  LOGIC  |   =
        =  +---------+   =
        =                =
<=========== DATA BUS ===============>

Now, all you have to do is just hook together some memory chips, for example by recycling static cache RAM from old 386 PCs, an ALU and a few glue components. You may pick one of TTL or CMOS for logic gates and latches; I'm a CMOS guy, but this really depends on your favourite flavor. You may build an 8, 16, 32, 64 bit or whatever width system you need. Just in case, for larger word widths, I have found preferable building the ALU with pre-programmed 27128 EPROMS instead of the harder-to-find 74x181s. Look around for a carry propagation unit, too.

The monolithic nature of this system allows only memory-mapped I/O, and requires special design provisions for bidirectional interfacing, but nothing more peculiar than what is seen in older-generation systems. AGC, the computer that drove Apollo 11 mission to the moon was making use of such techniques, so it should be sufficient in this case, too.

Note that the data bus has to be exactly as wide as the address bus, that implies that the notion of a byte is only applicable to 8 bit coffee machines, which you will eventually find that it is more of a feature than a bug. You will be surprised with what a coffee you can have for 8 or 16 bits bus! It is really a general-purpose piece of hardware, built for peanuts.

5.3 Software

Such a pure system will make a good fit together with the, famous for embedded systems controlling, FORTH programming language. The major prerequisite for doing so is to have a stack mechanism, which in this case can be constructed by a counter combined together with a memory pool.

If you want to claim a serious coffee development platform, C portability is an absolute must nowadays. Your choices might be hacking one of gcc, lcc or sdcc, which with proper tweaking at the back-ends will be able to spit out the specially crafted MISC assembly code. One day you might even want to rewrite another language like C, forget the D letter - it is taken already, so do not make again the same mistakes with your compiler please: http://www.gnu.org/software/gcc/projects/beginner.html

Just in case you thought of writing your own compiler, please read in advance about flex, yacc and just a little bit of related theory. In particular you will quickly appreciate Noam Chomsky's taxonomy on languages:

so on, so forth. Read ahead on Computability Theory.

5.4 A minor criticism on the Turing Machine

Because of the way a Turing Machine works (see for that http://plato.stanford.edu/entries/turing-machine/ ), it is a very complicated device to program, and debug at the end of the day. The reason is, that its behavior is a sequential process that is completely determined by the following parameters:

The major contemporary disadvantage of the Turing Machine (TM) is that it is of sequential nature, which implies that only a particular range of problems can be mapped to it in a straightforward way. TMs are suitable for problems that are described well on a serial storage medium (tapes) and don't make use of indexes for data reference. This is in contrast to the Coffee Machine (CM) that can handle any Random Access algorithms as well (with no compromise of simplicity).

Add to this, that TMs impose a very high and unnecessary complexity on item (3) in favor of keeping (1) and (2) simple. And just in case you don't agree that the so called Table of Instructions gets trully overwhelmed, have you ever tried to write a compiler for a Turing Machine? A system that isn't easily programmable and is hard to debug, should be considered a seriously questionable system, at least as far as Computer Engineering (!= CS) is concerned. For instance, try to simulate the Coffee Machine with a Turing Machine and vice versa. Hey, if you still disagree, show me the code.

Bottom Line: The Coffee Machine (CM), is a much better model for the von Neumann architecture and has a O(1) relationship with what is standard practice of weighting algorithms, in the current form of complexity theory.

Next Previous Contents

Hosting by: Hurra Communications Ltd.
Generated: 2007-01-26 17:58:13