ABSTRACT
This chapter examines the Turing machines and what they can do by looking at a Turing machine without its tape; this is called a finite state machine. Alan Turing, a British mathematician, equated the concept of "computability" with the ability of a certain type of machine to perform a computation. An finite state machine, in response to a given stimulus and being in a given state, produces a response and goes into a new state. A typical Turing machine consists of two parts; a tape, which must be of potentially unlimited size, and the machine itself, which moves over the tape and manipulates its contents. To keep track of the parts of the tape it has already considered, the machine would do the now-familiar trick of overwriting digits with symbols which it subsequently ignores, just as people did with the parenthesis checker.
