This chapter discusses Turing machines. A Turing machine is the combination of a sequential, finite-state machine plus an external read/write memory storage medium called the tape (think of a ribbon of magnetic tape). The tape is a linear sequence of squares, with each square holding one of several possible symbols. The Turing machine's power to compute comes from its tape, for two reasons. First, Turing was the first to conceive of the idea of a stored program that could be changed by the operation of the machine itself. The program, and its input data, exist together on the tape as sequences of symbols. Second, because of the arbitrarily long length of the tape, a Turing machine has the ability to “remember” what has happened in the arbitrarily distant past.
Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.
To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.