3TURING MACHINES AND TURING COMPLETENESS
Spend enough time around programming languages, and two phrases inevitably appear: “Turing machine” and “Turing completeness.” In this chapter, we’ll explain what these phrases mean and why they are important. Specifically, we’ll introduce the halting problem and discuss Alan Turing’s fantastic solution to it. That will set the stage for discussing Turing machines and Turing completeness. We’ll end by simulating a Turing machine in Python.
The topics of this chapter fall under the heading “theoretical computer science,” which is a branch of mathematics, not software engineering. As we’ll see below, theoretical ...
Get Strange Code now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
