Universal-turing-machines is a project mainly written in JavaScript, it's free.
Implementations of universal turing machines
Turing machines are awesome, and modern computers are basically Turing machines with dynamic state transitions.
A programming language is said to be Turing complete if it has:
These are fine, but not very interesting. The more interesting way is to simulate a universal Turing machine.
The attempt of this project is to simulate a universal Turing machine with interesting languages, therefore proving them as Turing complete.
There are differing definitions of what a Turing machine is, but we'll try to use one that is as restrictive as possible while still recognizing all languages that other Turing machines recognize.
A Turing machine is a state machine with these properties:
Here is the formal definition of a Turing machine:
A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q, Σ, Γ are all finite sets and:
- Q- set of states
- Σ- input alphabet, not containing blank symbol ␢
- Γ- tape alphabet, where ␢ ∈ Γ and Σ ⊆ Γ
- δ-
Q × Γ → Q × Γ × {L,R}
is the transition function- q0 ∈ Q- start state
- qaccept ∈ Q- accept state
- qreject ∈ Q- reject state, where qreject ≠ qaccept — Michael Sipser
An alternative syntax explaining the same thing can be found here.
In order to be complete and accept all possible input, each implementation takes two files as input:
Here is an example state transition going from state 'start' to state 'first' on input 'a', writes the character 'c', and moves the head right:
start,a,c,R,next
For simplicity, all implementations assume that Σ and Γ contain only single-characters.
Note:
This means that in order for a state transition to not modify the tape, it must write the same symbol it read. Because this can be tedious, the '*' symbol is reserved and cannot be part of Σ or Γ:
An implementation does not necessarily output anything, but must use correct error codes to signify success (accept) or failure (reject).
Following Unix-style exit codes, 0 means success and non-zero means failure.