Turing Machine

An imaginary machine conceived by Alan Turing in the 1930s to help identify the kinds of problems that are potentially solvable by machines. The machine is a kind of simple computer. It consists of a long string of paper tape and a machine through which the tape can be fed. The machine can do four things: it can move the tape one space, it can place a mark on a space, it can erase a mark, or it can halt. Turing’s thesis states that this simple machine can solve any problem that can be expressed as an algorithm (if it has an unlimited supply of paper tape). As you might imagine, in practice it would be difficult to give instructions to a Turing machine so that it could solve a particular problem. The Turing machine is important theoretically, however, because it provides an indication of what kinds of problems computers can solve and what kinds they can never solve.

Sources:

⠀ Dictionary of computer and Internet terms / Douglas A. Downing, Michael A. Covington, Melody Mauldin Covington. — 10th ed. – 561 c. – 500