1、23 4 5Before Turing Machine6Informal description7Informal descriptionFigure 14.1 The Turing machineInformal descriptionFigure 14.2 The Turing machine in the classic style8Informal description910Formal descriptionFormal description11Formal description12Table 14.1 Transition table for the Turing machi
2、neCurrent stateReadWriteMoveNew stateCb 1LDC11NABb bRCB11LDAb 1LBA1b RAFormal description13Formal description14Figure 14.3 Transition state diagram for the Turing machineExamples15ExamplesFigure 14.4 Example 14.116ExamplesFigure 14.5 The Turing machine for the incr(X)statement17ExamplesFigure 14.6 E
3、xample 14.2 18Figure 14.6 shows how the Turing machine can increment X when X=2.ExamplesFigure 14.7 The Turing machine for the decr(X)statement19ExamplesFigure 14.8 Example 14.3Figure 14.8 shows how the Turing machine can decrement X when X=2.20The Church-Turing thesis212223242526Figure 14.9 Step 1 in the proof27Figure 14.10 Step 3 in the proof28293031Figure 14.11 Taxonomy of problems323334Figure 14.12 The execution time for different algorithms35363738394041
