プログラミング言語-短いコードを持っているのは誰ですか？

Cで書かれたコードはJavaやBasicで書かれたコードよりも短いと誰かが言うでしょう（Cで書いている人）。 それとも本当に短いですか？



驚かれることでしょうが、2つのプログラミング言語をAとBと呼ぶと、すべてのプログラムでこれら2つの言語のコード長の差を補う定数があることがわかります。







本当に！



はじめに、いくつかの表記法。



言語Aと関数φの長さ（A、φ）を、言語Aで書かれた関数φを計算する最小のプログラムの文字数とする（ここで考える必要がある）



すべての関数のリストは、φ（1）、φ（2）、φ（3）、...として定義されています（無限に多くあります）



その結果、任意のiに対して次のような単一の定数cを取得します。

長さ（A、（i））<=長さ（B、（i））+およびその逆

長さ（B、（i））<=長さ（、（i））+



なんで？



言語Aでは、言語Bのインタープリターを作成し、言語Bのプログラムをパラメーターとして言語Aで作成されたプログラムに転送できるためです。逆の場合も同様です。 定数cは、言語Aと言語Bで記述されたインタープリタープログラムの長さの合計になります。



PSすべてのプログラミング言語でインタプリタを記述できるとは限りません。これは単なる一般的なケースと見なされているためです。



参照：Ming Li、Paul Vitanyi-コルモゴロフの複雑さとその応用の紹介。