7

動機: 関数の代わりに自然数を使用することで、一次関数のない言語でおもちゃの関数型プログラミングを使用できるようにしたいと考えています。

ユニバーサル関数は関数 f : N -> (N -> N) であり、同等に f : N * N -> N であり、可能なすべての計算可能な関数を列挙します。つまり、f(k) が 2 乗関数であるような数 k があり、f(j) が n 番目の素数関数であるような数 j があるということです。

このような関数を作成するには、任意のチューリング完全言語 (プログラミング言語コンパイラ、ラムダ計算、チューリング マシンなど) を使用して、すべてのプログラムを列挙します。評価だけでなく、足し算、合成、カリー化などの関数の操作もできるようにしたいです。たとえば、2 つの関数 f,g のインデックスが与えられた場合、関数 f+g、または g で合成された f のインデックスは何かを知りたいです。これにより、「おもちゃの関数型プログラミング」が可能になります。

そのようなコード ライブラリを作成する良い方法は何ですか? 私は、10 の階乗を計算するのに苦労する最小限のチューリング ターピットを探しているわけでも、高度なコンパイラを書きたいわけでもありません。追加やループを書く可能性など、いくつかの基本的な機能が必要ですが、それ以上ではありません。

すべての高級言語でのソリューションを歓迎します。疑似コード、Haskell、および Python が推奨されます。任意精度の演算を想定できます。使用evalまたは類似のものは許可されていません。

明確化: 列挙型関数は、すべての部分再帰 (計算可能な)関数で構成されます。これには、一部の入力で停止しない関数が含まれます。その場合、ユニバーサル関数はハングします。もちろんこれは避けられません。参照: m-再帰関数 - http://en.wikipedia.org/wiki/Μ-recursive_function。

4

7 に答える 7

9

あなたが望むのは通訳と呼ばれるものです。

まず、必要なプロパティを持つ列挙は、最初の 2^32 または最初の 2^64 整数で操作したい興味深い関数に適合しません。したがって、メモリ内のどこかに割り当てられ、ポインターを介して参照される、より大きな整数が必要になります。

それでは、既存の構文でプログラムを表す文字 (文字列) の配列を使用しないのはなぜですか? それがあなたを幸せにするなら、そのような文字列を整数と考えてください。計算する関数の番号は、f1()+f2()(f1 の表現)、"+"、および (f2 の表現) で構成される文字列です。あなたはアイデアを得る...

このアプローチにないのは、関数の表現の単一性です。これは、おそらくあなたの質問に暗示されていました(よくわかりません)。私が確信しているのは、表現の単一性は、関数表現に対する単純な、または計算可能な合成操作を持つことと互換性がないということです。たとえば、そうでない場合、停止問題には簡単な解決策があります。

于 2009-11-25T15:12:15.093 に答える
1

While it is not too hard to enumerate all possible expressions in some language, you won't be able to restrict these to those expressions that denote terminating functions.

But if you are not interested in termination, using combinators (with some arithmetic primitives thrown in for usefulness) might be the best way, since you avoid introducing variable names that way.

于 2009-11-25T17:11:29.983 に答える
1

Pascal が言ったように、あなたが望むのはインタープリターですが、もっと良い方法があります: プロセッサーをインタープリターとして直接使用してください。

数値 N (たとえば、大きな int 配列として) をバッファに直接入力し、このバッファをマシンコードとして実行します。

コンピューターが実行できるすべての可能な機能には、N が存在します。残念ながら。すべての N が有効なプログラム (これは要求されていません) または終了プログラム (これは不可能です) であるとは限りません。

一方、この関数は、World of Warcraft、Service Pack 6 を含む Microsoft Office 17、および Windows 9 などの宝石を生成します。

于 2009-11-26T08:42:08.773 に答える
0

何かがプログラムであるかどうかを判断し、辞書順ですべてのプログラムをリストできるようなプログラミング言語を使用できます。組み合わせ爆発を少しでも回避するために、ユーザー定義の名前 (変数、関数など) を正規化された形式で割り当てることができます。明らかに、これにより膨大な数の関数が生成され、どれが実際に役立つかを選択するのは容易ではありません。トリミングの自動方法は、実際に必要な関数を除外するか、組み合わせ爆発を有用なほど十分にトリミングできないか、またはその両方になります。

これのもう 1 つの欠点は、数値から関数に移行するのが非常に難しくなることです。関数 433,457,175,432,167,463 を見つけるのに、約 400 京の関数を列挙するよりも優れた方法を見つけるのは困難です。

もう 1 つの方法は、シンボルを数値にマッピングし、それらを効果的に連結することによって、関数を数値にエンコードすることです。

記号は、+、-、:=、==、<、if、then、endif、do、end_do_condition、enddo、およびステートメント区切り文字であると想定します。関数呼び出しのようなものを含まず、掛け算と割り算を必要とする非常に最小限のセットに対して、変数なしで 11 個のシンボルがあります。(論理演算子が 1 つまたは 2 つなければ、これが機能するかどうかは実際にはわかりません。) 変数名を 5 つ追加すると、4 ビット文字を使用するプログラミング言語ができあがります。これは、最大 16 文字が 64 ビットの符号なし整数に収まることを意味します。

これを取得すると、関数間のすべての可能な関係は算術関係として表現できますが、実際に正しく理解するには非常に複雑な関係になります。

要するに、これは理論的には可能ですが、実際にはあまりにも不器用です。選択した非関数型言語で関数型言語のインタープリターを作成する方がおそらく簡単でしょう。

于 2009-11-25T15:47:00.933 に答える
0

このような関数を作成するには、任意のチューリング完全言語 (プログラミング言語コンパイラ、ラムダ計算、チューリング マシンなど) を使用して、すべてのプログラムを列挙します。

それができるかどうかはよくわかりません... チューリング教会のテーゼに反しているように感じます。すべてのプログラムを列挙するには、最初にどのプログラムが有効でどのプログラムが無効かを判断するアルゴリズムが必要ですが、それは不可能です...それを気にせず、言語で誤ったプログラムを許可しない限り。

しかし、正式なシステムのゴデル化はあなたを助けるかもしれません.コードをデータとして持つことで、Lispを試してみます。

于 2009-11-25T15:55:28.033 に答える
0

わかりません。ただし、計算可能なすべての関数を列挙することはできません。短い答え:そうでなければ、普遍的なウイルス対策が存在するためです. 長い答え: そのような列挙があった場合、列挙自体を計算する関数もそのセットに含まれるからです。ラッセルのパラドックスのように。

あなたの質問に対する別の答えは、計算可能なすべての関数を「リスト」したいということです。そのためには、それらを素数として表し、それらの構成を乗算として使用することができます。これにより、一意性が保証されます。因数分解すると、逆関数が得られます。

于 2009-11-25T16:02:47.797 に答える
0

簡単な質問ではありません。すべての関数を1つずつ生成できる関数ジェネレーターから始めなければならないと思います。これにより、列挙が行われます。

無限の複数の次元を処理する必要があるため、考えてみましょう。

問題を、n 個のパラメーターと基本演算 +、-、*、/ を持つ関数に還元してみましょう。
1 つの操作だけですべての関数を作成しましょう。

a +
a a + b
a -
a a - b
a *
a a * b
a /
a a / b

これらの関数のいくつかは他の関数よりも意味があり、それらのいくつかは同等である可能性があることは簡単にわかると思いますが、少なくとも、ループを介して生成できるマッピングです。

次の反復では、これらの関数のそれぞれに簡単に追加できます

  • すべての操作で既存のパラメーターの 1 つ
  • すべての操作を含む 3 番目のパラメーター

その後、手順 2 を繰り返すことができる関数の膨大なリストができます。

は、sin や log (テイラー級数) などのより複雑な関数をすべて推定する関数であるため、これらもこの関数スペースでカバーする必要があります。

これは役に立ちますか？この投稿を自由に編集してください。

あなたの投稿を読み直してください。数値だけでなく、すべてのプログラム関数を列挙したい場合は、もっと複雑になると思います。関数のソースを圧縮し、zipファイルを大きな数として扱うことにより、マッピング「関数<->番号」を操作することは理にかなっていると思います。逆に、任意の番号を解凍して、便利な機能が作成されるかどうかを確認できます:-) しかし、zip ファイルでさえない番号がたくさんあると思います。

しかし、すべての関数にそれを表す数値があるという要件を満たすでしょう:-)

于 2009-11-25T15:10:06.000 に答える