チューリング完全性の観点から、単純なループはネストされたループと同じくらい強力ですか?
2 に答える
1
チューリング完全性に関しては、そうです。
証明:たとえば、次のように、単純なループを使用してBrainf***インタープリターを作成することができます。
于 2011-01-16T00:24:26.190 に答える
0
ステップ数が固定されているループの場合(LOOP、FORなど):ループの全体の目的がにカウントされることを想像してみてくださいn
。単一のループではなくi
、外側のループでj
時間をループし、内側のループで時間をループする場合、なぜ違いを生む必要がありますか?n = i * j
プログラムでは、WHILE、GOTO、または同様の構成が許可されていないと想定します(割り当て、IF、および固定ループのみ)。その後、これらのプログラムはすべて、有限のステップ数の後に終了します。
表現力を高めるための次のステップは、反復回数が条件によって決定されるループを許可することです。この条件が満たされるかどうかは不明です(WHILEなど)。その後、プログラムが停止しないことが起こる可能性があります。(このタイプの表現力は、チューリング完全性としても知られています)。
これらの2つの形式のプログラムに対応するのは、2種類の関数であり、これらは歴史的に同じ時期に開発されたもので、原始再帰関数とμ再帰関数と呼ばれます。
入れ子の数はこれには影響しません。
于 2011-01-16T00:36:13.083 に答える