チューリングマシン 2011/6/6.

Presentation on theme: "チューリングマシン 2011/6/6."— Presentation transcript:

1 チューリングマシン 2011/6/6

2 アランチューリング 1912-1954 計算機科学の父 計算機理論の偉い人 ENIGMA解読 チューリングテスト
"On Computable Numbers, with an Application to the Entscheidungsproblem"（「計算可能数、ならびにそのヒルベルトの決定問題への応用」、1936年5月28日） ゲーデルとの関連 1954、同性愛関係？でリンゴに青酸化合物を塗り自殺

3 チューリングテスト 機械に知性があるか否かどうやって判定するのか？ 中国人の部屋（操作マニュアルにて対応） 部屋＋操作マニュアルが知性を持つ

4 計算可能数 計算できるとうことはどういうことか 有限のステップ 形式化されたステップ アルゴリズム チューリングマシン

5 Church・Turingのテーゼ 数論（自然数）上の関数の構成法 Godel Church・Kleene ramda記法 Turing
いずれも同等の計算力を持つ 計算可能関数の概念を定義（計算可能数）

6 チューリングマシン 有限の内部状態 無限のテープ テープ上に記録・削除・読み取りができる
「計算可能」なものはすべてチューリングマシンで構成できる

7 チューリングマシンの状態遷移 内部状態 ｑ テープ上の記号（アルファベット） 次の状態ｑ‘ テープに書き込む記号（アルファベット）
内部状態　ｑ　 テープ上の記号（アルファベット） 次の状態ｑ‘ テープに書き込む記号（アルファベット） テープヘッドの移動方向 いろいろな表現がある

8 チューリングマシンシミュレーター たとえば http://ironphoenix.org/tril/tm/

9 プログラムの一例 8,_,3,_,< 8,1,8,1,> 8,X,8,X,> 8,A,8,1,> 9,*,10,_
9,1,9,1,< 10,_,H,_ 10,1,10,_,> 10,X,10,_,> 10,A,10,_,> 1,1,13,1,< 13 ,_,2,*,> 2,_,3,_,< 2,*,2,*,> 2,1,2,1,> 2,X,2,X,> 2,A,2,A,> 3,1,4,_,< 3,X,9,X,< 4,1,4,1,< 4,X,5,X,< 5,*,8,*,> 5,1,6,A,< 5,A,5,A,< 6,_,7,1,> 6,*,6,*,< 6,1,6,1,< 7,*,7,*,> 7,1,7,1,> 7,X,5,X,< 7,A,7,A,>

10 Ｎ本テープチューリングマシン タプル数は２＋３N 一本テープチューリングマシンで模倣可能 説明はホワイトボード上にておこなう

11 万能チューリングマシン 通常のチューリングマシンはある特定の問題に対する計算をおこなう
任意のチューリングマシンの挙動を計算するチューリングマシンを構成することができる 停止問題

12 チューリングマシン Mechanical http://www.youtube.com/watch?v=WJ-ODmFjmrU LEGO
Comway’s Life Game