0

「Hello world tester」プログラムが決定不能な問題であることは、理論的なコンピューター サイエンスではよく知られています
。逆の問題を解決できますか:
入力と出力のセットが与えられた場合、与えられた入力と出力の間で 1 対 1 のマッピングを実現するプログラムを作成するプログラムを作成するためのアルゴリズムはありますか? 私はメタプログラミング
について知っていますが、私の質問はより理論的な興味深い一般的なケースに適用できるもの。

4

6 に答える 6

2

あなたの質問はあいまいに表現されています。

「プログラムが何をすべきか」をどのように指定しますか?
プログラムの機能の正確で完全な機械可読仕様は、すでにプログラムです。

したがって、あなたの質問に対する答えは、コンパイラです。

ここで、入力と出力のサンプルに基づいて関数を見つける方法を尋ねています。
それは、私には答えられない統計分析に関する質問です。

于 2011-11-25T03:12:38.347 に答える
2

この種の黙想には、非常に注意する必要があります。命題が成り立つプログラムと命題が成り立つプログラムを明確に区別しないことから、多くの混乱が生じます。保持されるプログラムのセットが有限である限り、それらの正しさの証明が常に存在します (ただし、この証明は不明な場合があります)。xP(x)xP(x)P(x)

この時点で、既知であり、既知であるプログラムと、すべての可能性を完全に列挙することによってのみ存在を示すことができるプログラムとを区別する必要もあります。例を挙げてみましょう:

入力を受け取らず、終了して「hello World」を生成する場合と生成しない場合がある 10 個のプログラムを取り上げます。次に、これらのプログラムのどれが正しく、どれが正しくないかを正確に判断するプログラムがあります。これらのプログラムを呼び出しましょう(x_1,...,x_10)。次に、i の 2 進数表現の j 番目のビットが設定されている場合、program の出力を(X_0,...,X_{2^10})取得X_iします。これらのプログラムの 1 つは、すべての 10 について正しく決定するものでなければなりません。これらの 100 のうちのどれが正しいものであるかを判断する方法はまったくないかもしれません(この時点でのメタ問題)。truex_jx_iX_j

これは、プログラムと入力/出力ペアの有限セットを考慮すると、常に完全な列挙に解決でき、すべての停止問題タイプのパラドクシーが即座に消えることを示しています。あなたの場合、各入力に対して生成されたプログラムのセットのサイズは 1 であり、入力/出力のペアのセットは有限サイズです (メタプログラムに提供する必要があるため)。したがって、完全な列挙は問題を非常に簡単に解決し、修正されたプログラムの正しさとメタプログラムの正しさの両方を簡単に証明することもできます。

注: 生成されたプログラムのセットは無限であるため、これは無限のプログラム セットを証明できる数少ないケースの 1 つですP(x)(実際P(x,input,output)、このセットは証明できます)。これは、セットが無限であることは必要条件にすぎず、この種のパラドックスが現れるための十分条件ではないことを示しています。

于 2011-11-25T09:35:56.187 に答える
1

入力と出力がどのように表示されるかを言わなかったため、質問は特定されていません。有限リストの場合、このPythonコードのように、答えは「はい」です。

def f(input,output):
    print "def g():"
    print "    x = {" + ",".join(repr(x) + ":" + repr(y) for x,y in zip(input,output)) + "}"
    print "    print x[raw_input()]"


>>> f(['2','3','4'],['a','b','x'])
def g():
    x = {'2':'a','3':'b','4':'x'}
    print x[raw_input()]
>>> def g():
...     x = {'2':'a','3':'b','4':'x'}
...     print x[raw_input()]
... 
>>> g()
3
b

無限集合の場合、どのようにそれらを提示しますか？入力の小さなサンプルのみを表示する場合、これはアルゴリズム全体を指定しません。最適なものを推測することは決定不可能です。「魔法のブラックボックス」がある場合は、連続した多くのマッピングがありますが、プログラムの数は数えられるだけなので、それは不可能です。

于 2011-11-25T09:14:34.427 に答える
1

「1対1のマッピング」の意味によって異なります。（そして、「入力」と「出力」もあると思います。）

私の推測では、与えられた任意のプログラムの入力と出力の例が与えられた場合、同等のプログラムを作成するアルゴリズムを考案できるかどうかを尋ねているのではないでしょうか? もしそうなら、答えはノーです。たとえば、1/1、2/2、3/3、4/4 の入力/出力を持つプログラムを作成できますが、次の入力値が 5 の場合、出力は 3782 になります。与えられた一連の結果から、次の結果が何であるかを知る。

于 2011-11-25T03:55:46.113 に答える
1

入力シーケンスを与えられて学習し、それ自体を更新して適切な出力シーケンスを生成するステート マシンを生成したいようです。出力シーケンスが同じ入力シーケンスに対して常に同じであると仮定すると、それは簡単に書けるはずです。時間帯に応じて出力を変更するなど、出力が決定論的でない場合、ステート マシンを自動的に生成することはできません。

于 2011-11-25T03:39:16.110 に答える
0

私は SLaks に同意すると思いますが、別の角度から物事を考えると、コンパイラーは何をするのでしょうか?

（編集：SLaksが彼の元の回答を編集したのを見ました。これは本質的に「あなたはアイデンティティ関数を説明している」でした）。

プログラムの意図された動作を記述するあるソース言語のプログラムを取り、その動作を示すターゲット言語で別のプログラムを「記述」します。

これは、プロセスの改良などの観点から考えることもできます。抽象的な仕様が与えられた場合、「より具体的な」(通常は非決定論的ではない) 実装への改良マッピングを構築できます。

しかし、あなたの質問に基づいて、これらのどれを意味するかを判断するのは本当に非常に困難です.

于 2011-11-25T03:16:16.723 に答える