1

チューリング完全性の観点から、単純なループはネストされたループと同じくらい強力ですか?

4

2 に答える 2

1

チューリング完全性に関しては、そうです。

証明:たとえば、次のように、単純なループを使用してBrainf***インタープリターを作成することができます。

http://www.hevanet.com/cristofd/brainfuck/sbi.c

于 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 に答える