6．チューリングマシンの符号化と 　計算不可能性

内容

1. スライド　1 6．チューリングマシンの符号化と　計算不可能性
2. スライド　2 ６−１．TMの符号化
3. スライド　3 アイディア
4. スライド　4 状態の符号化
5. スライド　5 アルファベットの符号化
6. スライド　6 受理状態の符号化
7. スライド　7 初期状態と空白記号の符号化
8. スライド　8 状態遷移関数の符号化
9. スライド　9 これらをまとめて、
10. スライド　10 入力テープの符号化
11. スライド　11 ６−２．万能チューリングマシン
12. スライド　12 万能TM
13. スライド　13 UTMの動作
14. スライド　14 TMとUTM
15. スライド　15 ６−３．TMの限界（計算の限界）
16. スライド　16 計算の表
17. スライド　17 入力記号
18. スライド　18 TMで認識不可能な言語
19. スライド　19 証明（対角線論法）
20. スライド　20 TMにおける停止能力
21. スライド　21 　　この言語は、必ず停止する言語では認識できない。 背理法（対角線論法）により...
22. スライド　22 言語間の関係
23. スライド　23 ６−４.言語と問題
24. スライド　24 判定問題
25. スライド　25 判定問題の例
26. スライド　26 言語と問題
27. スライド　27 ６−５．停止性問題
28. スライド　28 定理
29. スライド　29 入力　　　　　　　　に大して、コピーを作り文字列　　　を構成する。
30. スライド　30 もし、　　　　　　　が必ず停止することがあらかじめ判別できれば、 　　　　をシ...
31. スライド　31 6−6．停止性問題の別証明
32. スライド　32 DataのDとしては、どのようなデータでもかまわないはずである。 よって、Dと...
33. スライド　33 次に、halttester2(P)を元に、次のような関数を構成する。
34. スライド　34 このとき、プログラムfunny1()に、 引数として、funny1()を与えた...