N-Tape Turing Machine
Recognises recursively enumerable languages (RE) · Strictly more powerful than PDA
# N-Tape Turing Machine Configuration
states:
q0:
transitions:
- tapeReads: ['0', '_']
nextState: q1
tapeWrites: ['0', 'X']
tapeMovements: ['R', 'R']
q1:
transitions:
- tapeReads: ['1', 'X']
nextState: qaccept
tapeWrites: ['1', 'X']
tapeMovements: ['S', 'S']
- tapeReads: ['_', '_']
nextState: qreject
tapeWrites: ['_', '_']
tapeMovements: ['S', 'S']
qaccept:
transitions: []
qreject:
transitions: []
tapes:
- name: Input
alphabet: ['0', '1', '_']
- name: Work
alphabet: ['0', '1', 'X', '_']
initialState: q0
acceptStates:
- qaccept
rejectStates:
- qreject
Want a specific preset configuration added? Request it by email at contact@csvisualizer.com.
Frequently Asked Questions
A Turing machine is a mathematical model of computation consisting of an infinite tape divided into cells, a read/write head, a finite set of states, and a transition function. At each step the machine reads the current cell, writes a symbol, moves the head left or right, and transitions to a new state. Turing machines can compute anything a modern computer can.
A Turing machine accepts its input by entering a designated accept state, and rejects by entering a reject state. Unlike DFAs, a Turing machine may also run forever without halting — this is called looping. The halting problem (deciding whether a machine halts on a given input) is undecidable.
A multi-tape Turing machine has several independent tapes each with its own read/write head. Multiple tapes can make programs significantly easier to write, but every multi-tape machine can be simulated by a single-tape machine — so the two models recognise exactly the same class of languages.
Each tape can be configured as infinite (extends in both directions), left-bounded (a fixed left end, like a standard TM), right-bounded, or both-bounded (finite tape). The boundary setting is per-tape and can be changed in Tape Settings before running the machine.
The Church-Turing thesis is the hypothesis that any function computable by an effective algorithm can be computed by a Turing machine. It is a thesis rather than a theorem — it cannot be formally proved — but decades of research have found no counterexamples, and all known models of general computation are equivalent in power.