チューリングマシン 2011/6/6 アランチューリング • • • • • • 1912-1954 計算機科学の父 計算機理論の偉い人 ENIGMA解読 チューリングテスト "On Computable Numbers, with an Application to the Entscheidungsproblem"（「計算可能数、ならびにその ヒルベルトの決定問題への応用」、1936年5月28日） • ゲーデルとの関連 • 1954、同性愛関係？でリンゴに青酸化合物を塗り自 殺 チューリングテスト • 機械に知性があるか否かどうやって判定する のか？ • 中国人の部屋（操作マニュアルにて対応） • 部屋＋操作マニュアルが知性を持つ 計算可能数 • 計算できるとうことはどういうことか • 有限のステップ • 形式化されたステップ アルゴリズム • チューリングマシン Church・Turingのテーゼ 数論（自然数）上の関数の構成法 • Godel • Church・Kleene • Turing ramda記法 いずれも同等の計算力を持つ 計算可能関数の概念を定義（計算可能数） チューリングマシン • 有限の内部状態 • 無限のテープ • テープ上に記録・削除・読み取りができる • 「計算可能」なものはすべてチューリングマシ ンで構成できる チューリングマシンの状態遷移 • • • • • 内部状態 ｑ テープ上の記号（アルファベット） 次の状態ｑ‘ テープに書き込む記号（アルファベット） テープヘッドの移動方向 いろいろな表現がある チューリングマシンシミュレーター たとえば • http://ironphoenix.org/tril/tm/ • http://download.cnet.com/Tuatara-TuringMachine-Simulator/3000-12512_410784567.html プログラムの一例 • • • • • • • • • • 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,> • • • • • • • • • • 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,_,> Ｎ本テープチューリングマシン • タプル数は２＋３N • 一本テープチューリングマシンで模倣可能 • 説明はホワイトボード上にておこなう 万能チューリングマシン • 通常のチューリングマシンはある特定の問題 に対する計算をおこなう • 任意のチューリングマシンの挙動を計算する チューリングマシンを構成することができる • 停止問題 チューリングマシン • Mechanical http://www.youtube.com/watch?v=WJ-ODmFjmrU • LEGO http://www.youtube.com/watch?v=cYw2ewoO6c4 • Comway’s Life Game http://www.rendell-attic.org/gol/tm
© Copyright 2024 ExpyDoc
