DUMB-Turing is a Turing machine based on Alan Turing's original mathmatical description.
Turing machines are mathematical models of computation. It is proposed by Alan Turing, and is used in the Church–Turing thesis to prove that anything computable can be computable by a Turing machine. This gives birth to the concept of Turing completeness. If a machine is Turing complete, it can compute anything.
Unfortunately, modern computers are not literal Turing machines. They are Turing complete, though, but it is different in structure from Turing's original design.
A Turing machine formally refers to a DFA (a meatly FSM) of finite size that has access to an infinite tape. The DFA takes the data on the current tape head as input, and based on the current state, takes a state transition while writing a symbol on the tape before deciding to move the tape head either left or right. By designing a set of state transitions, someone can perform any computation on the tape.
DUMB-Turing is a Turing machine in the Literal sense. It uses external SPI ROM and RAM for the transition table and (emulated) tape. This Turing machine has 128 states and an alphabet size of 256.
The transition table is modelled by an external SPI ROM. The table is made up of 2-byte entries of transitions. Each ROM is expected to be 4KB in size, thus there should be 32,768 entries in total.In each entry, the first byte dictates the tape data to be written, and the next byte dictates the tape-head movement direction and the next state.
There are 2 special states at 0x7F and 0x7E. They behave like other states except for what is read or written on the tape.
One change I made that is inconsistent with Turing's mathematical description is the use of a circular tape. The SPI controller will wrap around the address space when the tape head moves past the limit below 0x0 or above 0xFFFF. This gives the illusion of a circular tape of 64K-bytes. The SPI memory needs to be attached to the UIO[7:4] pins. This port uses different SCK, MISO, and MOSI than the Transition Table.
This machine cannot be used with bigger SPI memory, as it will use 3 3-byte addresses instead of 2. However, this machine can work with smaller SPI memory, provided that the SPI memory ignores the upper used address bits.
To achieve the best reasonably achievable performance, DUMB-Turing uses a tape cache as well as a tape movement predictor. The cache is a write-through cache that saves 8 bytes of data near the tape head. This allows the Turing machine to compute on a small range of tape efficiently. Furthermore, the tape movement predictor uses movement history to predict how the tape is going to move next. This allows prefetching some tape before the Turing machine needs it. These optimizations are usually only featured in much more complicated processors. But since the memory access pattern of a tape is always linear, they can be integrated here in a much more "dumbed down" version.
