Simplest Turing Machine

The definition of a TuringMachine includes the idea of a translation table, a symbol dictionary, and commands to move the tape head left or right (or builtin to the commands for read or write). What is the simplest Turing machine conceivable?


WikiStub

Define the TuringMachine thusly: A tape, a wheel to move the tape FORWARD or REVERSE, an overwrite head to READ or WRITE symbols from or to the tape, and a translation table or function to transform the symbol into another.

Anyone want to take a crack at it?

Then a 1-bit adder with carryover allowing arbitrary length (but then, how to specify data vs. instructions?)

 consisting of a move (forward: 1, reverse: -1), a binary symbol (1,0), and a transition function f.  Such can then be specified with a tuple of (move (1 || -1), symbol: (1 || 0), transition function: NAND):

Two options. Define a word size, built into the r/w head that always moves a fixed amount on every READ. Or, a special character could be used indicating separate words of arbitrary length.

MarkJanssen, Credit of NAND machine as the (untested) simplest TuringMachine to StephenWolfram.


See also GeneralPurposeComputer.


EditText of this page (last edited December 8, 2014) or FindPage with title or text search