1行のソースコードでタスクを実行するプログラムを作成することは、一般的なプログラマーの趣味です。しかし、それは少し些細なことです。1 000 000行のコードを取得し、すべての改行を削除して、出来上がりです。1行！
したがって、物事を面白くするために、ステートメントを数えることができます。Cスタイルの言語の場合、ステートメントをカウントする簡単な方法はセミコロンをカウントすることです。したがって、100万のif-elsesをネストすることは問題ありません。
n個のステートメントを持つプログラムPがあるとします。一連の状態（変数値） s（sはベクトル）を通過し、出力xを生成します。2つの質問をすることができます：
- n個未満のステートメントを持つプログラムは出力xを生成できますか？
- n個未満のステートメントを持つプログラムはsのサブセットを通過できますか？
すぐに、いくつかのことが明らかになります。次のプログラムを受講してください。
int sum = a+b;
float mean = sum/2.0;
return mean;
これを1つのライナーにリファクタリング（または「デファクタリング」と言うべき）できます。
return (a+b)/2.0;
すべてのプログラムを1行にディファクタリングできますか？このプログラムを受講してください：
string x = "";
for (int i = 0; i<a; i++) // Should these semicolons count?
{
x = x + ".";
}
return x;
それはもう少し挑戦的です。
質問は、 n未満のステートメント、有限の数ですべての可能なプログラムを試すことによって徹底的に答えることができます（理論的には、無限に多くの可能な値を持つ定数を持つことができますが、実際の言語には、それらを格納するための無限のメモリまたは収容するための無限のディスクスペースがありませんソースコード）。
でも：
A. n個のステートメントでx（おそらくsを介して）を生成するプログラムPについて、 m個のステートメントでそれを実行できるQが（効率的な方法で）見つからないことを証明することは可能ですか？
B.最小のnを（効率的な方法で）見つけることができますか？
C.最小nは1であることが保証されていますか？
実際の言語の方が面白いでしょうが、あなたはあなたが望むどんな言語でも仮定することができます。あなたの言語が異常な場合は、あなたの言語での「ステートメント」の定義を提供してください。
私は命令型言語を想定しましたが、関数型言語への問題の適応は大歓迎です。
簡単な解決策があります。任意のPに対して、 Pを実行し、 xを記録します。ここで、 xを単純に出力するプログラムQを記述します。入力のあるプログラムの場合、各入力が正しい出力にマップされた状態で、非常に長いif-elseを作成します。
この解決策は不十分ですが、理由は完全にはわかりません。まず、無限の可能性のある入力の場合、それは不可能です（しかし、実際のプログラムは有限であると言って、私はすでにお尻をカバーしているので、実際の入力は有限であると言えます）。第二に、それは技術的にはsのサブセット、つまり空集合のみを通過します。第三に、それは本当に反気候的です。
この小さな巧妙なトリックを定義するのに役立つこともありがたいです。
PS：私の言葉の価値が何であれ、これは宿題ではありません。私は単に問題に興味を持ち、できるだけ明確に表現しようとしました。もちろん、宿題だったら…