8

セルがビットで、+ 操作と - 操作が少し反転するだけの場合、Brainfuck Turing は完全ですか? Brainfuck のような言語がセル サイズに関係なくチューリング完全であるという簡単な証明はありますか、それともチューリング マシンをシミュレートするプログラムを考える必要がありますか? 存在しない場合、どうすればわかりますか？

編集: 私の質問に対する答えが見つかりました: ビット セルを使用した Brainfuck はBoolfuckと呼ばれます。通常の Brainfuck はそれに還元できるため、Boolfuck はチューリング完全です。

4

2 に答える 2

2

この答えはあなたにぴったりです。言語のチューリングを完成させる機能について、非常に具体的な定義があります。

その要点は次のとおりです。

一般に、命令型言語がチューリング完全であるためには、次のものが必要です。

  1. 条件付き繰り返しまたは条件付きジャンプの形式 (例: while, if+ goto)

  2. 何らかの形式のストレージ (変数、テープなど) を読み書きする方法

于 2014-04-17T21:50:34.343 に答える
1

チューリング完全言語は、「単一テープのチューリング マシンをシミュレートする」ことができます。Brainfuck と Boolfuck は仕様に従っているため、どちらもチューリング完全です。

また、一方がチューリング完全である場合、もう一方はほぼ同じであるため、チューリング完全である必要があることに注意してください。ブレインファックではバイト単位で移動しますが、ブーファックではバイトを構成するビットを使用します。

于 2014-03-31T15:39:41.763 に答える