《计算机科学导论》教学课件Unit-14Theory-of-Computation.ppt
-
文档编号：6245758
资源大小：969.74KB
全文页数：41页
- 资源格式： PPT
下载积分：22文币 交易提醒：下载本文档，22文币将自动转入上传用户（ziliao2023）的账号。
微信登录下载
快捷注册下载
账号登录下载
|
友情提示
2、试题类文档，标题没说有答案的，则无答案。带答案试题资料的主观题可能无答案。PPT文档的音视频可能无法播放。请谨慎下单，否则不予退换。
3、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。
5、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者搜狗浏览器、谷歌浏览器下载即可。。
|
《计算机科学导论》教学课件Unit-14Theory-of-Computation.ppt
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
