計(jì)算機(jī)導(dǎo)論課件：ch17[Part5.Advanced Topics] Theory of Computation

1、Brooks/Cole, 2003Chapter 17TheoryofComputationBrooks/Cole, 2003Brooks/Cole, 2003Brooks/Cole, 2003Figure 17-1Statements in simple languageBrooks/Cole, 2003Brooks/Cole, 2003Figure 17-2Turing machineBrooks/Cole, 2003Figure 17-3TapeBrooks/Cole, 2003Figure 17-4Transition stateBrooks/Cole, 2003-AABBCCDD-#

2、&1same as read blank1same as read 1-BCCABDBD-1 or blank# or &1not 11not 1not a blankblank-Brooks/Cole, 2003Figure 17-5Transition diagram for incr xBrooks/Cole, 2003-StartIncrForwardForwardAddedBackwardBackward-#11&same as read#-ForwardForwardAddedBackwardBackwardStopIncr-#1&anynot #-

3、Brooks/Cole, 2003Figure 17-6Steps in incr x statementBrooks/Cole, 2003Figure 17-7Transition diagram for decr xBrooks/Cole, 2003-StartDecrForwardForwardDeleteBackwardBackward-#1blank&same as read#-ForwardForwardDeleteBackwardBackwardStopDecr-#1&1not #-Brooks/Cole, 2003Figure 17-8Transition di

4、agram for the loop statementBrooks/Cole, 2003-StartLoopCheckCheckForwardForwardEndProcessBackwardBackward-#not 11not &anynot #-nonenone-CheckStopLoopForwardForwardStartProcessBackwardBackwardCheck-#same as read1same as read&same as readsame as read#Brooks/Cole, 2003Brooks/Cole, 2003Symbol-12345678-12345678-12345678Symbol-9incrdecrwhilex-9ABCDEFBrooks/Cole, 2003Brooks/Cole, 2003A Classical Programming Question:Brooks/Cole, 2003Figure 17-9Step 1 in proofBrooks/Cole, 2003Figure 17-10Step 2 in proofBrooks/Cole, 2003Figure 17-11Step 3