アラン・チューリング生誕100周年

今日2012/6/23のGoogleのロゴは、チューリングマシンを模し、6つの問題を解くことのできるものだった。面白い。このロゴは今日限りかと思うともったいない。

アラン・チューリングについて検索して、気になったことを残しておきたい。

アラン・チューリングは1912年、イギリス・ロンドン生まれ。1936年にチューリングマシンを考案した人物として知られる。無限に長いテープに記録される「1」「0」などの情報をヘッドで読み書きすることにより問題を解いていく概念で、現代の計算機にも通じるものだ。・・・中略・・・ほかにもチューリングは第二次世界大戦中にドイツが使用していたエニグマ暗号を解読したりと、数々の功績を残している。
今日のGoogleホリデーロゴはアラン・チューリング生誕100周年より引用

デジタル コンピュータには2つのタイプがある。1つはノイマン型コンピュータ。ハンガリーの数学者フォン ノイマンが提唱したもので、ノイマンマシンとも呼ばれている。現在、地球上で稼働しているコンピュータのほとんどがこれ。もう1つは、イギリスの数学者アラン チューリングが提唱したチューリングマシン。こちらは、概念の域を出ず、実用化はされていない（と思う）。

チューリング マシンは左図のように、データを記憶するメモリセルが連続したテープと、その上を移動するヘッドからなる。ビデオテープをイメージすると分かりやすい。

ヘッドは図のように、2方向に移動するが、1回で移動できるのは1メモリセルのみ。さらに、ヘッドは真下のメモリセルの値を読んだり、値を更新する（書く）ことができる。ただし、メモリセルに許された値は、「0」か「1」、つまり１ビット。これに加え、チューリング マシンのstate（内部状態）を保持する内部レジスタを１つ持っている。これが、チューリング マシンのすべてである。

チューリングマシンが処理できるのは、ビット列操作だけではない。「計算可能な問題（アルゴリズムが存在する）」ならどんな計算も可能だ。
チューリングマシンの原理より引用

アラン・チューリング生誕100周年を記念して、オランダの2人の研究者が、LEGO Mindstorms NXTチューリング・マシンを製作し、その画像と動画の記事がWIRED.jpにある。「チューリング氏が考案したオリジナルのモデルでは、無限に長いテープが使われているが、LEGOの場合、ブロックを無限には供給できないという些細な問題があった。そこで、スイッチが32カ所になるようにテープのサイズを調整した」
LEGOで作成されたチューリング・マシン（動画）より引用

今日2012/6/23はコンピュータサイエンスの創始者であるAlan Turing（アラン・チューリング）の生誕100年である。

参考サイト
今日のGoogleホリデーロゴはアラン・チューリング生誕100周年
http://www.mdn.co.jp/di/newstopics/24002/?rm=1
チューリングマシンの原理
http://www.benedict.co.jp/Smalltalk/talk-73.htm
LEGOで作成されたチューリング・マシン（動画）
http://wired.jp/2012/06/22/lego-turing-machine/