Turing Machine

• A theoretical model of computation introduced by Alan Turing.
• Consists of an infinite tape, a read-write head, and a finite set of states.
• Reads symbols, writes symbols, moves the head, and changes state based on rules.
• Can simulate any computer algorithm.
• Fundamental concept in theoretical computer science.

Recursive and Recursively Enumerable

• Recursive enumerable (r.e.) language: accepted by a Turing machine that may not halt.
• Recursive language: accepted by a Turing machine that always halts.

Universal Turing Machine

• A Turing machine that can simulate any other Turing machine.
• Takes description of another machine and its input as input.
• Simulates the behavior of the specified machine on the given input.
• Shows that any computation can be performed by a single machine.
• Important for defining what it means for a computation to be algorithmic.

Church-Turing Hypothesis

• Any function that can be effectively computed can be computed by a Turing machine.
• Any problem that can be solved by an algorithm can be solved by a Turing machine.
• Not a theorem but a widely accepted principle.
• Implies that algorithmic complexity is tied to the number of steps required by a Turing machine.