シンプルループとネストループ

チューリングの完全性の点でネストループほどシンプルなループは強力ですか？シンプルループとネストループ

2011-01-16 banx

「パワフル」とはどういう意味ですか？ –

「強力」とはどういう意味ですか？表現力に関しては、どちらも同等です。データ構造を調整する必要があるかもしれません。 – miku

あなたの質問を編集してください。 –

チューリングの完全性の点では、そうです。

証明：

手順（LOOP、FORおよび同様）の一定数のループの場合http://www.hevanet.com/cristofd/brainfuck/sbi.c

2011-01-16 00:24:26

校正可能な資料はありますか？どのような仮定の下で？ – banx

しかし、この例のおかげで、メインの内側でwhileループが使用されています。しかし、あなたが助けてくれる参考資料をお手伝いできるなら、私は正式な証拠を求めています。 – banx

@banx：私がリンクしてくれた通訳がひどく書かれていた。しかし、単純なループを使ってBrainfuckの解釈を書くことはかなり簡単です。概念は単純です：命令ポインタを動かし、終わりに達するまで繰り返します。 –

は：全体を想像してみてそれはここで例えば、単純なループを使用してBrainf***インタプリタを書くことが可能ですループの目的はnにカウントされます。外側のループでi回、内側のループでj回ループすると、なぜ違いが生じるのですか？n = i * jは単なるループではありませんか？

プログラム内でWHILE、GOTOまたは同様の構文が許可されていないと仮定します（代入、IF、および固定ループのみ）。そして、これらのプログラムはすべて有限個のステップの後に終了します。

さらなる表現性の次のステップは、ループを許可することです。この条件が満たされているかどうかはわかりません（例えば、WHILE）。それでは、プログラムが停止しないことがあります。（このタイプの表現力はTuring-completenessとも呼ばれます）。

これらの2つの形式のプログラムには、歴史的に同じ時間に開発された2種類の機能があり、primitive recursive functionsとμ-recursive functionsと呼ばれています。

この場合、ネスティングの数は影響しません。

2011-01-16 00:36:13 miku

ループは単純に一定量のステップをカウントする非常に簡単なシナリオを想定しています。一般に、内部変数はループの停止条件に影響します。 – banx

@banx：テキストを追加しました。 – miku

答えて