チューリング機械（1936年）：汎用計算は何を保証できるのか

記事

チューリングは規則に従う計算を形式化し、一部の判定課題には一般的な機械的解法がないことを示した。同じ年、チャーチは別の方法によって関連する否定的な結果に達した。この成果は数学的な計算可能性に関するもので、チューリングが一人で最初の電子計算機を作ったことではない。実際の計算機は、論理、電子工学、記憶装置への複数の貢献を通じて発展した。

チューリング機械は実際に何をするのか

チューリング機械は、マス目に分かれたテープ、記号を読み書きするヘッド、有限個の内部状態を持つ数学的モデルです。規則は、現在の状態と読んでいる記号から、記号を書き、ヘッドを動かし、状態を変えるという動作を指定します。長い計算は、説明されない判断の働きからではなく、意図的に単純化されたこれらの手順から組み立てられます。

テープは、計算の必要に応じて延ばせる記憶領域を表します。実際のコンピューターがすでに無限のメモリを持つという主張ではありません。このモデルは、電子部品やクロック速度などの工学的な選択を脇に置き、手続きに何が計算できるかという問いを、特定の装置がどれだけ速く動くかと分けて考えられるようにします。

万能機械の「万能」とは何か

異なる機械は、異なる命令の一覧で記述できます。チューリングは、一つの機械が別の機械の符号化された記述を読み、その計算を模倣できることを示しました。記述を変えれば、課題ごとに新たな数学的機械を用意せずに、課題を変えられます。これが万能機械の中心的な考えです。

万能とは、考えられるすべての問いにすぐ答えを出すという意味ではありません。モデル内で表される、規則に従った計算を再現できるという意味です。模倣には多くの手順がかかったり、終わらずに続いたりすることがあります。この区別を明確にすると、汎用コンピューターの考えが、問題を無制限に解けるという主張に変わるのを防げます。

どんな限界があり、ハードウェアはどう続いたのか

この研究は一階述語論理の決定問題、すなわち、すべての論理式について、あらゆる解釈のもとで真となるという意味で論理的に妥当かどうかを、一つの機械的方法で判定できるかを扱いました。チューリングの否定的な結果は、そのような方法の限界を明らかにしました。個別に解決できる場合もありますが、全体のあらゆる場合に必ず成功する一つの手続きを約束することができないのです。チャーチも別の方法で関連する否定的な結果を得ました。

この数学的探究は、後の電子計算機の製作計画と区別する必要があります。プログラムと計算可能性を精密に考える方法を与えたのであり、1936年の完成した機械ではありません。その後の歴史は、論理設計、記憶装置、部品、プログラミングの実際的な問題へと枝分かれします。それぞれの貢献をたどることで、現代のコンピューターには一度きりの発明の瞬間ではなく、多くの先行者がいることを説明できます。

年代と精度

1936年（計算可能な数の論文） 記録された日付

記録された年・月・日に基づいて位置づけています。不明な精度を推定で補ってはいません。

地図の代表地点

ケンブリッジ

主な学術活動の場の一つを表している。完成までの過程や後の研究には、プリンストンなどもかかわった。

代表地点の座標 · 52.205°, 0.117°

地点は、写本の所蔵先、実験室、観測地など、一つの代表的な場所を示します。研究がそこでしか行われなかったことを意味せず、共同の発見を一つの国に帰属させるものでもありません。

参考文献

• チューリングの1936年論文とケンブリッジ大学キングス・カレッジのアーカイブ
• ケンブリッジ大学キングス・カレッジ | アラン・マシスン・チューリング
• キングス・カレッジ・デジタルアーカイブ | アラン・チューリングについて
• アラン・M・チューリング | On Computable Numbers, with an Application to the Entscheidungsproblem（計算可能な数について、ならびに決定問題への応用）
• ケンブリッジ大学キングス・カレッジ | 決定問題

参考資料は、外部リンクなしの書誌タイトルとして表示します。個々の事実や背景を支えるもので、記事のすべての解釈を保証するものではありません。日本語版は英語版の本文を翻訳し、英語版が独立に選定した参考資料の原URLを保持しています。日本語の原資料であることや、日本語を母語とする編集者による独立した校閲が済んでいることを示すものではありません。