質問

関数の列挙の概念について学びました。実際には、プログラミング言語に対応しています。

通過する発言で、教授は、すべての合計関数のクラス(つまり、すべての入力に対して常に終了する関数)が いいえ 列挙可能。つまり、すべての合計関数を書くことができるが、他の機能はないプログラミング言語を考案できないことを意味します。

それでは、適切な計算能力が必要な場合、私たちが(明らかに)非終了の可能性を受け入れなければならないのはどうですか?

役に立ちましたか?

解決

対角線化のため。 $(f_e:e in mathbb {n})$が、$ mathbb {n} $から$ mathbb {n} $までのすべての合計計算可能な関数の計算可能な列挙であった場合、$ f_e $が合計であるように、 $ g(i)= f_i(i)+ 1 $も完全な計算可能な関数になりますが、列挙にはありません。それは、シーケンスに関する仮定と矛盾します。したがって、関数の計算可能な列挙は、正確に合計計算可能な関数で構成することはできません。

普遍的な計算可能な関数$ h(e、i)$を考えるとします。ここで、「ユニバーサル」は$ h $が計算可能なバイナリ関数であり、すべての合計計算可能な単一関数$ f(n)$には$ e $があります$ f(i)= h(e、i)$ for all $ i $。また、前の段落のために、$ g(n)= h(e、n)$が完全な関数ではないような$ e $もある必要があります。それ以外の場合、$ H $は、すべての合計計算可能なunary関数を含む、計算可能な合計unary関数の計算可能な列挙を提供します。

したがって、すべての関数が関数のシステムであるという要件は、合計であり、そのシステムに普遍的な関数の存在と互換性がありません。原始的な再帰関数などのいくつかの弱いシステムの場合、すべての関数は合計ですが、普遍的な関数はありません。普遍的な機能を存在させるために、チューリングの計算可能性など、普遍的な機能を持つより強力なシステムには、単に部分的な機能が必要です。

他のヒント

明確にするためには、数学的な関数を区別する必要があります(私はそれらを呼び出します 関数 そして、しばしば数え切れないほど多くあるので、それらはまったく列挙できません)とあなたが書くことができる機能:私はそれらを呼び出します プログラム またはまた 計算可能な関数.

可算セット$ e $のサブセット$ s $は呼び出されます 計算可能 $ e $の要素$ x $を与えられたプログラムがある場合、$x∈S$の場合は「はい」、$ x not∈S$の場合は「いいえ」と応答します。 (そして彼は常に何かに応答しなければなりません)セットは呼ばれます 再帰的に列挙可能 プログラムが「いいえ」と言う代わりに応答しないことを許可されている場合。 (プログラムがあらゆる順序で$ s $のすべての要素を印刷する必要があることを要求することは同等です)

の合計であるすべてのプログラムのセット 有限セット列挙可能 有限セットのすべての要素でプログラムを実行するだけで、すべてが終了した場合は「はい」を返す通訳を書くことができるからです。 (しかし、それらのどれもそうでないかどうかはわかりません)

あなたの教授は、合計であるすべてのプログラムのセットは 無限セット列挙できません プログラムを無限の数の要素で実行するだけではないからです。

しかし、これはこれが悪いという意味ではありません:

  1. たとえば、すべてのプログラムがある場合はセットです 確かに 合計です 列挙可能 すべての証明を列挙し、プログラムが合計であることを証明するかどうかを機械的に確認できるためです。

  2. 列挙可能なセットでさえ実用的ではありません。なぜなら、手順がいつか終了するかどうかを確認せずに永遠に待つ必要がある可能性があるからです。すべての合計機能を列挙するプログラムの使用方法がわかりません...

あなたが書くすべてが静的タイピングだけで終了することが保証されるいくつかのプログラミング言語があります!あなたが多項式に結合したことを保証するいくつかさえあります。彼らは今のところほとんど学問的であり、それらに書くことはおそらくあなたがPythonで書くという制約をより多く感じるようになるでしょうが、これに取り組んでいる多くの研究者がいます。

だからあなたの質問に答えるために:ある意味では、はい。潜在的な非ターミネーションは、チューリングを完全に(今のところ最高の計算能力)にするために必要です。しかし、これは、合計機能が列挙可能かどうかという事実に直接関連しているとは思いません。それでもすべての総プログラムを書くことができます!

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top