CHAPTER 12
LIMITS OF ALGORITHMIC COMPUTATION
CHAPTER SUMMARY
We have claimed that Turing machines can do anything that computers can do. If we can find a problem that cannot be done by a Turing machine, we have also identified a problem that is not in the power of even the most powerful computer. As we will see, there are many such problems, but instead of dealing with all of them in detail, we find one case to which all the others can be reduced. This is the halting problem. While this is a highly abstract issue, several practically important consequences follow.
Having talked about what Turing machines can do, we now look at what they cannot do. Although Turing’s thesis leads us to believe that there are few limitations to the power of a ...
Get An Introduction to Formal Languages and Automata, 6th Edition 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.
