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