Turing Machines

Mathematical Logic · Axiom Academy

The universal model of computation that formalized the notion of algorithm and decidability A Turing machine is a simple abstract computational device consisting of: An infinite tape divided into cells, each containing a symbol from a finite alphabet A read/write head positioned over one cell at a time A finite set of states that control the machine's behavior A transition function that determines the next action based on the current state and symbol A Turing machine is formally defined as a 7-tuple: 3. Configurations and Computation Steps A configuration describes the complete state of a Turing machine at a given time: This represents: the tape contains string u , the head is over the first symbol of v , and the machine is in state q . Computation is a sequence of configurations C₀ C₁ C₂ ... starting from the initial configuration. 4. Accepting, Rejecting, and Looping Given an input string w , a Turing machine M can have three possible outcomes: 5. Turing-Recognizable vs. Turing-Decidable There are two fundamental classes of languages in computability theory: A language L is Turing-recognizable if there exists a Turing machine M such that: If w L, then M either rejects w or loops A language L is Turing-decidable (or simply decidable ) if there exists a Turing machine M that always halts such that: 6. Multi-Tape and Other Variants Several variants of Turing machines exist, but remarkably, they all have the same computational power:

This is the written version of the interactive lesson above. See the full Mathematical Logic course.