無制限の容量のセルを使用したテープでのブレインファック

コマンドシステムはBrainfuck言語とまったく同じですが、テープ上で実行され、セルには任意の整数を入力できるマシンを使用します。 算術演算のオーバーフローは発生せず、正の数に適用される「+」コマンドは常に正の結果を返します。 問題は、そのようなマシンで作業することは可能ですか、どのような問題が発生し、どのようにそれらを回避するのですか?



利点は明らかです:オーバーフローがないので、長い演算の必要がないので、任意の長さの配列などで等しく作業できます。 しかし、すぐに、セル( "[-]")をクリアするお気に入りの方法が機能しないことがわかります。セルに負の値があった場合、プログラムはループします。 同様に、コピーコマンド「[-> + <]」を自由に使用することはできません。これは、負でない数に対してのみ機能します。



プログラミング中に、セルの内容の兆候を注意深く監視する必要があることがわかり(最も簡単な方法は、負の数の出現を防ぐことです)、兆候が不明な数字が表示された場合、特別な方法でそれを操作します



ここでは、2つのタスクを検討します。最初に、演算子「if(a> b)C; else D;” aとbは負ではなく、CとDはいくつかのアクションです。次に、任意の数値の符号をゼロにし、コピーし、決定する方法を学習します。







条件付きステートメント。



そのため、テープには2つの非負の数aとbが書き込まれます(このセルで自分で選択します)。 これらの数値を比較し、結果に応じてアクションCまたはDのいずれかを実行する必要があります。使用されたすべてのセル(aおよびbが配置されたセルを含む)をリセットする必要があります。

この形式で演算子を書き直します。

 hは1です。 
 while(h){
   if(a == 0){D;  a = b = 1;  hは0です。  }
   if(b == 0){C;  a = b = 1;  hは0です。  }
   a--;  b--;
 } 


aとbが負でない場合、そのようなプログラムでは負の数を使用できません。 if(a == 0)B;演算子を実装するには テープ上に4つのセル「a 0 1 0」のブロックを作成し、コマンド「[>] >> [B>]」を実行します。 最初にキャリッジがブロックの最初のセルにあった場合、いずれの実施形態でも最後にキャリッジはその4番目のセルにあります。



プログラムは次のようになります(キャリッジと数値「a」はセル0にあり、数値「b」はセル4にあると考えられます)。

 >> + [
   << [>] >> [C-<< + >>>> [-] + <]
   > [<] << [D->> + <<<< [-] +>]
   <-> >>>-<<]


変数hとして、ブロック「a 0 1 0 b」からの単一性が使用されます-とにかく、リセットされた後、効果的な比較はありません。



次のように記述することで、プログラムを少し単純化できます。

 hは1です。 
 while(a){
   if(b == 0){C;  a = b = 1;  hは0です。  }
   a--;  b--;
 }
 if(h){D;  h = b = 0;  }


判明します

 >>> + <<<
 [> [>] >> [C-<< + <[-] + >>>>]
   <<<-<-]
 > [-] >> [D-]


プログラムの実行時間は、max(a、b)から線形です。



不明なサイン番号



テープに数字aを書きますが、これについては正か負かはわかりません。 1)リセットする、(2)別のセルにコピーする、(3)a> 0の場合にアクションFを実行する必要があります。 3つの問題をすべて一緒に解決します



それらを解決する方法は? チューリングマシンのテープでゼロ以外のセルを探すのとほぼ同じ方法で、0でつまずくまで左右に実行します。

 if(a){
   xは1です。
   while(x){
     y = 2 * x;
     while(x){
       x--;  ++;  b--;
       if(a == 0)x = y = 0;
     }
     x = 2 * y;
     while(y){
       y--;  a--;  b ++;
       if(a == 0){F;  x = y = 0;  }
     }
   }
 }  


変数aはbにコピーされ、アクションFはaの初期値が正の場合にのみ実行されます。 BFへの翻訳:

 [>> + <<<<< +
   [[-<++ >> + <]>
     [->-> + [>] >>
       [-<<<< [-] << [-]]
       <<<<<]
     << [-> ++> + <<] >>
     [-> +>-[>] >>
       [F-<<<< [-] <[-]]
       <<<<<]
     <]]


動作時間もabs(a)から直線的です。 ここで、ブロックではif(a == 0)x = y = 0; キャリッジはその場所から遠く離れており、そこに残っています。 しかし、この時点でサイクルが終了するため、これはあまり重要ではありません。

それで何? 8ビットBFマシンで実行できることはすべてここで実行できますか? ああ。 無限のビット深度を備えた車にとっては難しいタスクが1つあります。 つまり、テープ部分をクリーニングします。 ゼロで埋められることが保証されているピースが与えられない場合、それを作成することはできません。 私はそれを証明することはできませんが:(



All Articles