N-Tape Turing Machine

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.