An Introduction to Formal Languages and Automata, 7th Edition

© VS148/Shutterstock.

CHAPTER 10OTHER MODELS OF TURING MACHINES

CHAPTER SUMMARY

In this chapter, we essentially challenge Turing’s thesis by examining a number of ways the standard Turing machine can be complicated to see if these complications increase its power. We look at a variety of different storage devices and even allow nondeterminism. None of these complications increases the essential power of the standard machine, which lends credibility to Turing’s thesis.

Our definition of a standard Turing machine is not the only possible one; there are alternative definitions that could serve equally well. The conclusions we can draw about ...