193 lines
8.1 KiB
HTML
193 lines
8.1 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
|
|
<HTML>
|
|
<HEAD>
|
|
<META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
|
|
<TITLE>Coffee Making: Building the Turing Complete Coffee Machine</TITLE>
|
|
<LINK HREF="Coffee-6.html" REL=next>
|
|
<LINK HREF="Coffee-4.html" REL=previous>
|
|
<LINK HREF="Coffee.html#toc5" REL=contents>
|
|
</HEAD>
|
|
<BODY>
|
|
<A HREF="Coffee-6.html">Next</A>
|
|
<A HREF="Coffee-4.html">Previous</A>
|
|
<A HREF="Coffee.html#toc5">Contents</A>
|
|
<HR>
|
|
<H2><A NAME="s5">5. Building the Turing Complete Coffee Machine</A></H2>
|
|
|
|
<P>
|
|
<P>Do you pine for the nice old days,
|
|
when men were men and build their own coffee machines?
|
|
<P>
|
|
<P>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
|
|
<A HREF="http://www.wordiq.com/definition/Turing_machine">Turing Machine</A>.
|
|
<P>
|
|
<P>
|
|
<H2><A NAME="ss5.1">5.1 An adequate assembly language</A>
|
|
</H2>
|
|
|
|
<P>
|
|
<P>Unlike other complex, but popular, systems that are either CISC or RISC,
|
|
our machinery will be MISC: Mono-Instruction Set Computer!
|
|
<P>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:
|
|
<P>
|
|
<BLOCKQUOTE><CODE>
|
|
<PRE>
|
|
|
|
SBN $mem1, $addr1
|
|
SBN $mem2, $addr2
|
|
SBN $mem3, $addr3
|
|
SBN $mem4, $addr4
|
|
SBN $mem5, $addr5
|
|
SBN $mem6, $addr6
|
|
[...]
|
|
</PRE>
|
|
</CODE></BLOCKQUOTE>
|
|
<P>
|
|
<P>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 <EM>: [mem] <= A <= A-[mem]</EM>.
|
|
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.
|
|
<P>
|
|
<P>Voila. This is a great system for any Turing Complete problems plus,
|
|
it is even simpler in coding than the original Turing Machine!
|
|
<P>
|
|
<H2><A NAME="ss5.2">5.2 Hardware and interfacing</A>
|
|
</H2>
|
|
|
|
<P>
|
|
<P>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
|
|
<A HREF="http://www.google.com/">google</A>.
|
|
<P>The CPU diagram looks like this:
|
|
<P>
|
|
<BLOCKQUOTE><CODE>
|
|
<PRE>
|
|
|
|
<========= ADDRESS BUS ==============>
|
|
= =
|
|
= +---------+ =
|
|
= | CONTROL | =
|
|
+---------+ +-----------------+
|
|
| ALU & A | | Program Counter |
|
|
+---------+ +-----------------+
|
|
= | LOGIC | =
|
|
= +---------+ =
|
|
= =
|
|
<=========== DATA BUS ===============>
|
|
</PRE>
|
|
</CODE></BLOCKQUOTE>
|
|
<P>
|
|
<P>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.
|
|
<P>
|
|
<P>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.
|
|
<A HREF="http://www.sandroid.org/Apollo/">AGC</A>,
|
|
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.
|
|
<P>
|
|
<P>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.
|
|
<P>
|
|
<P>
|
|
<H2><A NAME="ss5.3">5.3 Software</A>
|
|
</H2>
|
|
|
|
<P>Such a pure system will make a good fit together with the,
|
|
famous for embedded systems controlling,
|
|
<A HREF="http://www.wordiq.com/definition/Forth_programming_language">FORTH</A> 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.
|
|
<P>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
|
|
<P>
|
|
<P>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:
|
|
<UL>
|
|
<LI>regular grammars (the abstract formalism for regular expressions), </LI>
|
|
<LI>context free grammars (any BNF-described language is such)</LI>
|
|
</UL>
|
|
so on, so forth. Read ahead on
|
|
<A HREF="http://www.wordiq.com/definition/Computability_theory">Computability Theory</A>.
|
|
<P>
|
|
<P>
|
|
<H2><A NAME="ss5.4">5.4 A minor criticism on the Turing Machine</A>
|
|
</H2>
|
|
|
|
<P>Because of the way a Turing Machine works (see for that
|
|
<A HREF="http://plato.stanford.edu/entries/turing-machine/">http://plato.stanford.edu/entries/turing-machine/</A> ), 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:
|
|
<UL>
|
|
<LI>(1) the State the machine is in, </LI>
|
|
<LI>(2) the Symbol (or number) on the square it is scanning, and </LI>
|
|
<LI>(3) a Table of Instructions</LI>
|
|
</UL>
|
|
<P>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).
|
|
<P>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.
|
|
<P>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.
|
|
<P>
|
|
<P>
|
|
<HR>
|
|
<A HREF="Coffee-6.html">Next</A>
|
|
<A HREF="Coffee-4.html">Previous</A>
|
|
<A HREF="Coffee.html#toc5">Contents</A>
|
|
</BODY>
|
|
</HTML>
|