O'Reilly logo

An Introduction to Formal Languages and Automata, 6th Edition by Linz

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required