Close

Background

A project log for TMD-1: A Turing Machine Demonstrator

Develop a Turing machine that is simple to program and easy to understand.

Michael GardiMichael Gardi 07/07/2020 at 23:240 Comments

Not going to go into too much detail here. I just want to provide enough Turing machine background so that the pieces being designed and built will make sense.

Turing Machines 101

The Turing machine was invented in 1936 by Alan Turing.  By providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove the properties of computation in general.

A Turing machine mathematically models a mechanical machine that operates on a tape. More explicitly, a Turing machine consists of (mostly from Wikipedia):

    1. Write a symbol from the finite alphabet replacing the one that was there. Note that the symbol written might be the same as before or different
    2. Move the head either one cell to the left or one cell to the right. 
    3. Assume the same or a new state as prescribed by the go to state.

Discussions