チューリングマシン: コンピューターが存在しないときに計算についてどのように話せばいいのでしょうか?

1950 年 10 月に、「機械は考えることができるか?」と題する論文が発表されました。この論文では、テストを行う人とテストを受ける人（実際の人間と機械）が離れているときに、テストを行う人に通信機器を通じてランダムな質問を投げかけ、話している相手が実際の人間か機械かを推測させるという恐ろしいテストを提案しています。

複数回のテストの後、機械が各参加者に平均して 30% 以上の誤判断をさせることができれば、機械はテストに合格し、人間レベルの知能を備えているとみなされます。

ロボットが人間のような知能を持つことができると人々が認識したのはこのときが初めてだった。このテストは、何百万人もの SF ファンが話題にしているチューリング テストです。この記事により、著者のアラン・チューリングは「人工知能の父」という称号も得ました。

「人工知能への道」、つまりコンピュータ開発の歴史の源泉は、チューリングが24歳のときに発表した論文です。この論文で、彼は「計算可能性」の厳密な数学的定義を与え、有名な「チューリングマシン」の概念を提案しました。チューリング マシンは特定のマシンではなく、考えられるすべての計算可能な関数を計算するために使用できる、非常にシンプルでありながら非常に強力なコンピューティング デバイスを作成できるメンタル モデルです。

チューリングがチューリングマシンを発明したため、チューリングが実際に「コンピューターを発明した」と主張する人が時々現れます。ただし、チューリング マシンは実際のコンピューターの設計と同一ではありません。チューリングマシンはマシンの抽象的なモデルでさえありません。チューリングが実証したように、チューリング マシンは、テーブルの上の紙に何かを書く人のモデルであることがわかります。では、チューリングはなぜチューリングマシンを発明したのでしょうか。そして、チューリングマシンは私たちをどこに導くのでしょうか。

1チューリングの論文「計算可能数について」

これらの質問に答える最善の方法は、教科書を脇に置いて紙を開くことです。今日では、1936 年のジャーナルを借りるのに、図書館カードに記入したり、図書館員が蔵書室からジャーナルを取りに来るのを 1 時間待ったりする必要はありません。代わりに、モルト ウイスキーを片手に、自宅でくつろぎながら Google にアクセスできます。私たちが探しているチューリング論文は次のとおりです。

論文アドレス: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

この論文にはいくつか誤りがあるが、長所は欠点を上回っている。ジョエル・デイビッド・ハムキンスが指摘しているように、チューリングは計算可能な実数を計算可能な小数展開を持つものとして定義しましたが、これは実際には真実ではありませんが、修正するのは難しくありません。

チューリングの論文の意図は、タイトル「計算可能数について、その決定問題への応用」に述べられています。「決定問題」(決定問題) は、与えられた一階論理式が有効であるかどうか、つまりすべての解釈において真であるかどうかを判断する効率的な手法があるかどうかを問うものです。

チューリングは次のように考えを展開しました。

実数を計算する人間と、有限個の条件 q1、q2、... qR... のみを満たすことができる機械を比較することができます。機械には長い「テープ」が通っていて、四角形と呼ばれるセクションに分かれていて、それぞれのセクションに「記号」が書かれていました。書かれた記号の中には、計算される実数の 10 進数列を形成するものもあれば、大まかな「記憶術」のメモに過ぎないものもありました。この下書きは消すことができます。私の主張は、テープ上で紙をスライドさせて、記号に着地してそれを使って何かを行うというこの種の計算には、デジタル コンピューティングで使用されるすべての計算が含まれるというものです。

…

簡単に言えば、「計算可能な数」とは、有限の手段を使用して小数表現を計算できる実数です。私の定義によれば、数値の 10 進表現が機械によって書き下ろせる場合、その数値は計算可能です。

チューリングはそれを定義して証明しましたが、これは典型的な数学論文であり、読者が本文で説明されているメカニズムをどのように実装するかについての議論を期待している典型的な工学論文ではありません。チューリングのタイトルと記事から、チューリングは主に小数点以下無限桁までの実数の計算に関心があったことがわかります。

この論文には、他にも多くの重要な貢献があります。

• 万能チューリングマシンと、そのマシンをデジタル形式でエンコードするアイデア
• このようにエンコードされたマシンの停止問題と対角化の決定不可能性

この論文を執筆した後、チューリングは理論計算科学の分野への扉を開きました。

2ユニバーサルチューリングマシン

チューリングが万能チューリングマシン (UTM) のアイデアを思いついたきっかけは定かではありませんが、一度思いついたら、その存在は明らかだと思ったのでしょう。チューリング マシンの目的は、デスクで作業する事務員をシミュレートすることであり、チューリング マシンは事務員と同じように動作し、マシンの状態とテープ上の記号に応じて、指定された一連の変換規則に従ってこの操作またはその操作を実行するため、このような日常的なタスクを実行するにはチューリング マシンが必要であることは明らかです。チューリングの論文では構築の詳細がやや曖昧だったが、誰も気にしていなかったようだ。

そして今、完璧に設計された汎用チューリングマシンが誕生しました。数十年前、ケンブリッジ大学のケン・ムーディ博士は、ユニバーサルなミンスキーキージェネレータを書きました。

リンク: http://www.igblan.free-online.co.uk/igblan/ca/minsky.html

このようなマシンには有限の数のレジスタがあり、各レジ​​スタには任意の大きさの非負の整数を格納できます。これには、3 つの異なるタイプのラベル付き命令で構成される有限プログラムがあります。

• レジスタRをインクリメントしてラベルLにジャンプ、またはR + → L
• レジスタRをテスト/デクリメントし、ラベルL0 / L1にジャンプ、またはL0↞R− → L1
• 割り込み。

このようなマシンはチューリングマシンよりもプログラミングが簡単ですが、それでも真のコンピューターには似ていません。

Moody は、 NとN×N間の標準的な一対一変換を使用して、整数のリストを 1 つの整数にパックします。彼は、スタックへのプッシュやスタックからのポップなどの処理を実行するための小さなレジスタ マシンの小さなライブラリを作成し、実際のプロセッサのフェッチ実行サイクルを彷彿とさせる設計を作成しました。全体のプロセスは次のスライドでご覧いただけます。マシン本体は次のようになります。

下の図は機械の全体構造を示しています。 （両図はケンブリッジ大学の理論計算科学教授アンドリュー・ピッツ氏によって作成された。）

驚いたことに、この機械の構造は非常にシンプルです！

3停止問題

停止問題は明らかに解決不可能です。そうでなければ、フェルマーの最終定理など、多くの数学的推測を解くことが難しくなります。フェルマーの最終定理では、x、y、z、n>2 を検索して、終了するかどうかを尋ねるプログラムを記述するだけです。ただし、停止の決定不可能性は厳密に表現され、証明されなければなりません。

一般に信じられていることとは反対に、チューリングの論文は停止問題について議論したのではなく、むしろ彼が「循環性」と呼んだ停止問題に関連する特性について議論した。チューリング マシンが「最初の種類の記号 (つまり、0 と 1) を有限数だけ書き込む」場合、それは循環的です。チューリングは実数を無限のバイナリ文字列として近似することを特に好んでいたため、循環性は重要だと思います。物理学者クリストファー・ストラチーは1965年に『コンピュータジャーナル』誌に宛てた手紙の中で、チューリングが停止問題が決定不可能であることの証明を彼に伝えたと主張した。

4チューリングとモーリス・ウィルクス

2009 年 9 月、デビッド P. アンダーソンは、チューリングに対する一般大衆とはまったく逆の見解を持っていたモーリス ウィルクスにインタビューしました。

デビッド・P・アンダーソン: チューリングの 1936 年の意思決定問題に関する論文はなぜそれほど重要だとお考えですか?

モーリス・ウィルクス: エンジニアは、ストアド プログラムのアイデアを三位一体の壮大な理論として捉え、「これは本当に素晴らしい、これがやり方だ」と言うと思います。

その論文に書かれた考えは、私が言っていることと実質的に意味のある点で何ら変わりません。その論文が出版されたのは彼にとって幸運だった。つまり、アロンゾ・チャーチは他の方法を使って同じ結果を得たのだ。

記事のURL: https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext

モーリス・ウィルクスはインタビューを受けたとき96歳だったことに注目すべきです。彼は有名なコンピュータの先駆者であり、EDSAC（電子遅延記憶自動計算機）の父です。この奇妙な答えの中に、チューリングの高い地位に対する彼の嫉妬が見て取れる。この二人は明らかに仲が悪い！モーリス・ウィルクスの理論に対する軽蔑も見られます。機械を数値としてエンコードすることはプログラム内蔵型コンピュータの先駆けでしたが、チューリングの研究は純粋数学であり、工学的な意味合いはありませんでした。チューリングは実用的なコンピュータ工学に非常に興味を持っていましたが、実際の工学に携わろうとする彼の多くの試みは繰り返し失敗しました。

教会についてのコメントについてどう思いますか?

5プリンストンのチューリングとチャーチ

チューリングが研究を行っていた当時、多くの研究者は「効果的な計算可能性」というアイデアに注目していました。ここで私は読者にチャーチの「初等数論における解決不可能な問題」（下図参照）を読むことをお勧めします。

論文リンク: https://www.jstor.org/stable/2371045?origin=crossref

正直に言うと、この論文は読みにくいですが、話を元に戻してくれます。この論文では、λ 計算の定義、再帰関数の定義 (Kleene/Gödel の意味)、および λ 計算におけるパラダイムの存在と同値性に関するいくつかの決定不可能な結果を​​示します。チャーチとクリーネは、ラムダ定義可能関数と再帰関数の同等性を証明していました。そして、チューリングがプリンストンにいた頃には、ラムダ定義可能関数とチューリング計算可能関数の同等性も証明され、実質的に計算可能な関数はまさに数学的に同等なクラスに属するものであるとするチャーチ＝チューリングのテーゼが生まれました。

6チャーチ＝チューリングのテーゼは正しいですか？

よく言われるように、この命題が真か偽かは証明できません。なぜなら、「効果的に計算可能」というのは正確な概念ではないからです。チューリング計算可能関数は、宇宙の存続期間中は計算できない多くの関数を含んでいるため、かなり包括的なクラスと考えることができます。アッカーマン関数の助けを借りれば、簡単に例を得ることができます。

アッカーマン関数の現代的な形式は次のとおりです。

記事リンク: https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html

f(n)=A(n,n)と定義した場合、偶数f(4)を計算することはできません。 g(n)=A(4,n)は原始的な再帰ですが、計算するのはほぼ不可能です。

1930 年代までデジタル コンピュータは存在しなかったものの、効果的な計算可能性の概念は数学者にはよく知られていました。妥当性の概念は、ギリシャ幾何学の直線構造とコンパス構造にすでに現れています。妥当性は、決定問題とヒルベルトの第 10 問題の不可欠な部分でもあります。ゲーデルの再帰関数やチャーチのラムダ計算と比べて、チューリングの概念の優れた点は、それが非常に明らかに正しいということだ。ゲーデル自身も、彼の再帰関数が計算の考え方を捉えているかどうか確信が持てず、チャーチの考えが正しかったかどうかも分かりません。チューリングの考えだけが単純で自然でした。チューリングの考えは他のモデルと同等であることが証明されており、それらすべてに対して合理的な説明を提供します。彼は 1937 年の論文「計算可能性と λ 定義可能性」でこの事実を指摘しました。

この論文の目的は、著者らが提案した計算可能関数が、チャーチのλ定義可能関数、およびヘルブラントとゲーデルが提案しクリーニーが開発した一般再帰関数と同一であることを証明することです。これらの同じ関数はすべて、X で定義されたすべての関数が計算可能であり、すべての計算可能な関数が一般に再帰的であることを証明します。

チューリングは「計算可能」と書いたが、私たちは「チューリング計算可能」と書くべきであることに注意してください。