UTM定理

計算可能性理論において、UTM定理（普遍チューリングマシン定理）は、計算可能関数の集合のゲーデル数付けに関する基本的な結果である。これは、他のあらゆる計算可能関数を計算できる計算可能な普遍関数の存在を主張する。 ^[1]普遍関数は普遍チューリングマシンの抽象バージョンであるため、定理の名前が付けられている。

ロジャーの同値定理は、計算可能関数のゲーデル数列をs _mn定理と UTM 定理の観点から特徴づけます。

定理は、 2変数の部分 計算可能関数 uが存在し、1変数のすべての計算可能関数fに対して、すべてのxに対してとなるeが存在することを述べています。これは、各xに対して、f ( x ) とu ( e , x ) が両方とも定義されていて等しいか、両方とも未定義であるかのいずれかであることを意味します。^[2]${\displaystyle f(x)\simeq u(e,x)}$

この定理は、φ _e ( x ) をu ( e , x ) と定義すると、シーケンス φ ₁、 φ ₂、... が部分計算可能関数の列挙になることを示しています。定理のステートメント内の関数は、ユニバーサル関数と呼ばれます。 ${\displaystyle u}$

• ロジャース、H. (1987) [1967]。再帰関数の理論と効果的な計算可能性。MITプレスペーパーバック第1版。ISBN 0-262-68052-1。
• Soare, R. (1987)。再帰的に列挙可能な集合と次数。数理論理学の展望。Springer- Verlag。ISBN 3-540-15299-7。