Turing Trains

 

computational train track layouts

menu

Turing Machines

A Turing Machine is an idealised computer that can, in theory, simulate any computer program. There is much information on the web including Wikipedia and this useful introduction.

Turing machines use a tape divided into cells, with each cell holding a symbol. The machine can read or write a symbol to a cell, and move either left or right to the adjacent cell. The tape starts with 0 in all cells.

The machine stores 3 values:

  1. Symbol, 0 or 1 for a binary machine.
  2. Move, Left or Right, to the next cell.
  3. State, A B or C, and halt.

The machine also has a program, as a list of instructions. For each combination of State and Symbol, the values of Symbol, Move and State are updated.
eg. Instruction (A1: 0 R B) means if the machine is in state A and the Symbol is 1, then update Symbol to 0, Move to the Right and enter State B.

When the machine is run, it repeats the following Read, Write and Update loop each step:

  1. Write the Symbol to the current cell.
  2. Move to the next adjacent cell.
  3. Read the Symbol from the cell.
  4. If the State is 'halt' then Halt the machine. Else...
  5. Update the Symbol, Move and State values.

Busy Beaver Machines

The aim of busy beaver machines is to create a program that writes as many 1's to the tape as possible, or runs the machine for as many steps as possible before halting. These example machines implement a Busy Beaver using 2 symbols and 3 states. Machines start with Symbol 0, Move Right and State A.

Max 1's

This program produces the known maximum of six 1's (in 14 steps). From the web, the six instructions (for each combination of State and Symbol) are:
(A0: 1 R B) (A1: 1 R h) (B0: 0 R C) (B1: 1 R B) (C0: 1 L C) (C1: 1 L A)

If we run the machine, we find 7 (out of 12) lazy points never alter a value. They are redundant and can be removed. Also, we will not define Move for the halt state. So we end up with:
(A0: 1 R B) (A1: - - h) (B0: - - C) (B1: - - B) (C0: 1 L C) (C1: - - A)
where '-' denotes 'undefined'. This needs two points for A0 and two points for C0.

Turing Machine layout
Click grass to run/pause train Click points to switch 0/1 Click circle to reset train/points
lazy point Lazy points switch between upper 0 or lower 1 branch lines.
Trains arriving on a branch line switch the point to that line.
sprung point Sprung points allow branch line trains to join the main line.
All main line trains go straight ahead and never 'branch off'.

Layout

At the top of the layout is a horizontal tape containing six cells. Each cell has a lazy point to hold a symbol. Above them is a row of linked lazy points which select Left or Right. And below is a similar row of linked lazy points which select the Symbol value 0 or 1. At the bottom of the tape is a row of passive points which return the train to the current cell.

When the train enters a cell, it writes the symbol into the cell, then moves Left or Right to the adjacent cell and reads the cell symbol.

Below the tape, connected by a single track bridge, is the main layout. On the left are the State points. Outputs A0 and C0 set both Symbol and Move values. On the right, the train is routed back to select the next State.

Operation

Reset all points (click train on start circle) before each new run. The train leaves the station and sets the State Switch to A. It proceeds to the tape where the passive points guide the train to read the value from the central cell.

On returning to the central State Switch the train updates Symbol and Move values before updating the State Switch with a new State.

The yellow lazy points can be clicked to switch, although Turing Machines just run until the train returns to the station and halts.

Max Steps

This similar layout produces five 1's in 21 steps, which is a maximum run. The right most cell is unused. From the web, the six instructions (for each combination of State and Symbol) are:
(A0: 1 R B) (A1: 1 R h) (B0: 1 L B) (B1: 0 R C) (C0: 1 L C) (C1: 1 L A)

If we run the machine, we find 2 (out of 12) lazy points never alter a value. They are redundant and can be removed. Also, we will not define Move for the halt state. So we end up saving 3 points:
(A0: 1 R B) (A1: - - h) (B0: 1 L B) (B1: 0 R C) (C0: 1 L C) (C1: - L A)
where '-' denotes 'undefined'.

Turing Machine layout
Click grass to run/pause train Click points to switch 0/1 Click circle to reset train/points
lazy point Lazy points switch between upper 0 or lower 1 branch lines.
Trains arriving on a branch line switch the point to that line.
sprung point Sprung points allow branch line trains to join the main line.
All main line trains go straight ahead and never 'branch off'.

Turing Trains | cr31.co.uk | 2017

 

use your browsers 'zoom' option to enlarge layouts