マセマティカ エテルナ
オープンアクセス

概要

チューリングマシンの計算を理解するための方法

ジョン・ニクソン

この論文は、チューリング マシン (TM) の動作を記述する方法の第一原理調査です。テープの長さが有限に制限されている TM の結果を使用して、TM の計算を高速化する方法を示します。このようなルールの冗長性のないセットは、既約正規 (計算) ルール (IRR) と呼ばれ、任意の長さのテープの TM に対してそれらを生成するアルゴリズムについて説明します。このアルゴリズムは、無料で利用できるように C++ で実装されています。調査した例では、IRR の数が有限または無限であることを示しています。無限である場合のいくつかの TM については、それらの再帰式が見つかりました。これは常に可能であると予想されます。これらの式は、各例の IRR を個別に調べ、正しく推測して帰納法で証明することによって見つかりました。調査した例では、次に読み取られるシンボルに応じてどの IRR が他の IRR に続くかを示す表が見つかり、TM の動作に関する多くの情報を提供します。この方法により、汎用 TM を分析して、翻訳サイクルがどのように機能するかを発見することが可能になると期待されます。