8

Brainfuck は、非常に小さなコンパイラで知られています。私は非常に小さなデバイスを持っており、そのデータにはおそらく最小の頭脳明晰コンパイラでさえ収まりません。ブレインファックよりもさらに小さなコンパイラを持ち、チューリング完全な言語である難解なプログラミング言語はありますか? これは古くなっていますが、まだあなた自身の答えを自由に持ち込んでください。私はチェックします

4

6 に答える 6

0

TinyBFの命令数は BF の半分であるため、TinyBF 用のコンパイラを作成する方が簡単です。

=   Switch direction (- <-> +) (default: +)
+   Change data in selected direction. BF equivalents: - +
>   Change cell in selected direction. BF equivalents: < >
|   Jump in selected direction. BF equivalents: ] [
==  Output. BF equivalent: .
|=| if switch is positive, =|=| if switch is negative.  Input. BF equivalents: ,

実行可能な選択肢となる可能性があるBF に似た言語は他にもたくさんあります。

于 2016-02-26T18:13:22.017 に答える
0

他の候補は、J. Lambek (1961)のInfinite Abacusです。条件付きジャンプを備えた P マシンの前身。

無限のカウンターと 2 つの命令:

  • n+: 位置 n でカウンタをインクリメントします。
  • n- else p: 位置 n のカウンターが正のデクリメントの場合、そうでない場合は命令 p にジャンプします。

nアドレスを Böhm の the >andに簡単に置き換えることができます<が、コンパイラにはより多くのバイトが必要になると思います (命令が少ないということは、ケースが少ないことを意味します)。

>また、コンパイラのサイズを縮小するために、P" のand<を直接アドレス指定に置き換えることもできます。

もう 1 つの候補は、H. Wang の B マシン(消去不可能な無限テープを備えたチューリング マシン) です。

4 命令:

  • テープヘッドを右に移動し、次の命令に進みます
  • テープヘッドを左に移動し、次の命令に進みます
  • 現在のテープセルをマークして次の命令に進む
  • 現在のタップセルがマークされている場合はジャンプし、そうでない場合は次の命令に進みます

チューリングの完全性を失うことなく、条件付きジャンプではなく条件付きループを使用して、バリアントを確実に定義できます。

C のこれらのコンパイラのサイズはわかりませんが、アセンブリのインタープリタは明らかに小さいです。

欠点は、特に Wang の write once テープの場合、メモリ サイズです。

于 2018-09-05T07:46:24.390 に答える