チューリングマシン語り 前半

http://metanest.jp/tm/tm.xhtml にまとめました

id:propella:20070424:p1 のコメント欄の続き、のようなもの
(この日記では原則として実在の人名には「さん」を付ける方針であるため、本稿もそれに従っています)

チューリング機械まで

前世紀の前半において数学上重要だった話題に「そもそも計算とは何ぞや」という問題がある。そこでチューリングさんが考案し 1936 年に提示した、単純にして万能な計算機械が「チューリング機械」である
ウィキペディア http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
「数学的に議論するための、単純化・理想化された仮想機械である。」(ウィキペディアより引用)

万能*1

ここでいう、チューリング機械の万能性は、あとで出てくる「万能チューリング機械」と、かかわりは深いのだが、あくまでも別の概念であることに注意が必要である
ウィキペディアの「現実の計算との関係」にあるように、あらゆる計算する機械、さらにはあらゆる形式的な数学の体系を、チューリング機械の動作に還元できる、ということが、ここでの「万能」の意味である
ウィキペディアの「チャーチ=チューリングのテーゼ」のあたりも参照のこと

寄り道1 チューリング・テスト

戦後のことになるが、チューリングさんは、人間の脳を計算機でシミュレートする可能性について論ずることとなる。そのとき、まさにそのとき、どんな複雑な計算機械であっても、それをある計算機械で「真似ることができるという性質」によって、計算機の能力を想像の彼方まで見積もることを正当化しているのである
田中求之さんによる「チューリング・テスト再考」 http://mtlab.ecn.fpu.ac.jp/myNote/reconsidering_turing_test.html
の 5節 Universarity of Digital Computer のところにある

寄り道2 ノイマン機械

いわゆる「ノイマン型」、プロセッサと書き換え可能なメモリからなり、データとプログラムが同一視されるモデルは、メモリが十分であると仮定すればチューリング機械と同等の能力を持つ機械の実現と考えられる。そのような観点から、コンピュータの歴史上最初にそれを実現したとされる EDSAC を重要視することがある

万能チューリング機械

あらゆる機械を真似ることができるなら、チューリング機械を真似るチューリング機械はどうだろうか?
ここで、次のようなチューリング機械を考えてみる

このようなチューリング機械があれば、あらゆるチューリング機械の動作を真似ることができるわけである。そのような機械こそが「万能チューリング機械」である
チューリングさん自身によって示された万能チューリング機械は複雑なものであったが、単純化が流行った時期があるようである。しかしながら「面白い問題であるが,深い重要性はない.」(「ファインマン計算機科学」 pp. 64〜65 )

後半予告

後半書いた → id:metanest:20070425#turing

*1:万能、というと、まず「万能戦艦 Ν-ノーチラス」が思い浮かぶのはガイナ脳だろうか(次点は万能文化猫娘