Turing Machines

A Turing machine is an imaginary computing machine invented by Alan Turing to describe what it means to compute something. The “physical description” of a Turing machine is a box with a tape and a tape head. The tape consists of an infinite number of cells stretching in both directions, with the tape head always located over exactly one of these cells. Each cell has one of a finite number of symbols written on it. The machine has a finite set of states, and with every move the machine can change states, change the symbol written on the current cell, and move one space left or right. The machine has a program which specifies each move based on the current state and the symbol under the current cell. The machine stops when it reaches a combination of state and symbol for which no move is defined. A countable set S (or language) is called recursively enumerable if there exists a Turing machine that always halts when given an element of S as input, and that never halts when given an input that does not belong to S.