Turing Machine

Program: RMtm.z80

This is a 26-state Turing Machine. Each state is represented by a letter and the machine is in one state at a time. Imagine a long strip of paper tape, with a number of 'cells', each having the value 0 or 1. The machine starts at the left in its initial state, a, and moves along the paper, one cell at a time, left or right, as instructed by its  TM 'program'. When it lands on a cell, it reads the value there and looks up its state in a table, which provides the TM with the following instructions, depending on the contents of the cell:

• overwrite the current value with a new one

• move to the left or right one cell or stop

• go to the next state

The program starts by allowing the user to populate the table, highlighted in yellow at the top, with a new TM. When the 'Enter' key is hit, the user then enters data as 1s or 0s on the 'tape' in the yellow space below the table. When the 'Enter' key is again hit, the data is copied to a green highlighted area lower down (this is a recent enhancement) for your reference, and then the TM gets to work.

In the TM program shown above, unary numbers on the 'tape', consisting of a series of 1s separated by single 0s are to be added together. The data provided to the TM were the numbers 1, 2, 3, and 4, which you can see highlighted in green. The TM summed them to 10 as expected. 

The program starts in state a, encounters a 0, then moves one cell to the right until it encounters a 1, which it replaces with a 0, again moves to the right and enters state b. It keeps moving to the right until it encounters a 0 which is replaced with a 1 . It then enters state d and moves to the left until it encounters a 0 at which point it enters state a again. The process is repeated until it encounters two zeroes in succession while moving to the right. 

A running commentary is kept of the machine state. It started in state a and stopped in state c as shown.

Here's another TM program. It will make a copy of a unary number on the 'tape', the new number being printed to the right of the original, and separated from it by a 0:

001010

rrllrs

acdef

011110

rrrllr

bbcdeb

It should be fairly straightforward to adapt this program to make multiple copies of a unary number. The copies could then be added together by using code from the first TM program, effectively multiplying two numbers together.