**OTHER MODELS OF TURING MACHINES**

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 the power of a Turing machine are largely independent of the specific structure chosen for it. In this chapter we look at several ...

Start Free Trial

No credit card required