5．チューリングマシンと計算

内容

1. スライド　1 5．チューリングマシンと計算
2. スライド　2 ５−1．チューリングマシンとその計算
3. スライド　3 TMの概略
4. スライド　4 TMの数学的定義
5. スライド　5 TMの図式表現（状態遷移図）
6. スライド　6 TMの様相
7. スライド　7 TMの状態遷移図例
8. スライド　8 TMの形式的定義例
9. スライド　9 TMの計算例
10. スライド　10 TMの例２
11. スライド　11 TMの計算例２
12. スライド　12 練習
13. スライド　13 5-2.多テープTM
14. スライド　14 多テープTMの状態遷移関数
15. スライド　15 多テープTMとTMの等価性
16. スライド　16 テープ１
17. スライド　17 5-3．ランダムアクセスマシン（RAM）
18. スライド　18 RAMとTMの等価性
19. スライド　19 5-5.非決定性TM
20. スライド　20 NTMの状態遷移関数
21. スライド　21 NTMの計算の木
22. スライド　22 DTMによるNTMのシミュレーション
23. スライド　23 非決定性TMとTMの等価性
24. スライド　24 テープ１（入力テープ）は常に入力文字列を含み、 決して変更しない。
25. スライド　25 Nの遷移可能の選択数の最大値をｂとする。 木のすべての節点に対して、
26. スライド　26 １．テープ１にNへの入力　　をセットし、 　　テープ２、テープ３は空とする。
27. スライド　27 5-5．チャーチ・チューリングのテーゼ（計算の定義）