Turing Machine: Universal Machine
Explore how programs can be written onto tape, opening the path to universal machines and the halting problem.
機械の記述も、テープ上のデータとして読む
Universal Machineでは、あるTuring Machineのルール表そのものを記号列としてテープへ載せます。入力だけでなく「どんな機械を実行するか」もデータになり、interpreterがその記述を読みながら対象機械の1ステップを模倣します。
万能機械の考え方は、Turing Machineの記述を別の機械が読めるデータとして扱う発想につながります: Stanford Encyclopedia of Philosophy: Turing 。
まず2本のテープを見ます。上がprogram tape、下がinput tapeです。ここではStepせず、機械と入力が分かれていることを確認します。
第4章の中心は「速く計算する機械」ではなく、「機械の説明をデータとして読む機械」です。
Universal Overview
program tape + input tape最初は操作を出さず、program tapeとinput tapeが別の役割として並ぶことを読みます。
読む順番Universal Overview最初は操作を出さず、program tapeとinput tapeが別の役割として並ぶことを読みます。発見チェックに答えると、機械記述の符号化へ進みます。
Universal Map
Program tapedata flow
Input tapedata flow
Interpreterdata flow
Decoded ruledata flow
Halting boundarylimit
シリーズの終点機械化できる強さと、機械化できない問いを同時に見るUniversal Machineは、Turingシリーズを計算可能性の入口へつなぐ第4章です。PreludeからMechanicalまでの見方が、ここでprogram-as-dataへつながります。
Universal Machineで新しくデータになるものは？