1L_a/扁平化 1L_a 程式設計
外觀
建立 1L_a 程式的一種方法是先編寫相應的 Brainf*** 程式,然後將其轉換為 1L_a。因此,是時候引入一種新的語言,扁平化 1L_a,它介於 1L_a 和 Brainf*** 之間。
如你所知,Brainf*** 是一種眾所周知的、一維的程式語言。與 1L_a 一樣,它也有 DP 和 IP,但 DP 只能在一行上移動,並且 DP 在字元陣列上移動,而不是位陣列上移動。它是圖靈完備的,並且有 8 個指令。以下是這些指令
| 指令 | 操作 |
|---|---|
| > | 將 DP 向右移動 |
| < | 將 DP 向左移動 |
| + | 增加 DP 指向的記憶體單元的值 |
| - | 減少 DP 指向的記憶體單元的值 |
| . | 輸出 DP 指向的字元 |
| , | 輸入一個字元並將其儲存在 DP 所在的單元格中 |
| [ | 如果 DP 所在的單元格為 0,則跳過匹配的 ] |
| ] | 如果 DP 所在的單元格為 0,則跳回匹配的 [ |
然而,作為圖靈陷阱(只包含少數指令且圖靈完備的語言),8 個指令有點太多了。因此,我們可以建立具有更少指令的 Brainf*** 等效語言。
如果可以在 Brainf*** 中實現該語言中的每個指令,並且可以在該語言中實現 Brainf*** 中的每個指令,那麼我們稱該語言為 Brainf*** 等效語言。
很明顯,我們可以透過對位陣列(如 1L_a!)而不是字元陣列進行操作,將 Brainf*** 減少到 7 個指令,這樣 + 和 - 指令就變成一個指令:切換操作,表示為 @。可以使用強大的流程控制來模擬字元陣列,但這會很笨拙,我太懶了,不想這樣做。幸運的是,已經有人替我們做好了這件事。
Brainf*** The new language --------- ---------------- > >>>>>>>>> < <<<<<<<<< + >>>>>>>>[<]@>[@>]<<<<<<<<<[@] - @>>>>>>>>@[<@]>[>]<<<<<<<<<[@] [ @[>>>>>>>>@[<@]>[>]<<<<<<<<<[@]>>>>>>>>[<]@>[@>]<<<<<<<<<@[@ ] >>>>>>>>>@<<<<<<<<<]>>>>>>>>>[<<<<<<<<<@>>>>>>>>>@]<<<<<<<<<] . >.< , >,<
我們稱這種語言為 Boolf***。由於 Brainf*** 是圖靈完備的,並且可以將任何 Brainf*** 程式轉換為 Boolf*** 程式,因此 Boolf*** 也是圖靈完備的。