修改後的Brainfuck版本的圖靈完備性

是Brainfuck圖靈完成如果單元是位，並且+和 - 操作簡單地翻轉一點？是否有一個簡單的證據表明Brainfuck-like語言不管單元大小如何都是圖靈完成的，還是我需要考慮一個模擬圖靈機的程序？我怎麼知道如果沒有一個？修改後的Brainfuck版本的圖靈完備性

編輯：我找到了我的問題的答案：Brainfuck與位單元被稱爲Boolfuck。普通的Brainfuck可以減少到它，所以Boolfuck是圖靈完整的。

來源

2012-12-22 Eric Yu

允許您對自己的問題編寫答案。你應該這樣做，然後接受你的答案，這樣問題就會在問題列表中顯示出來。 – sepp2k

圖靈完整語言可以「模擬任何單張圖靈機」。 Brainfuck和Boolfuck都是圖靈完整的，因爲它們遵循規範。

另外請注意，如果一個人是圖靈完整的，另一個必須是因爲他們幾乎相同。隨着brainfuck，你正在以字節移動，但在boolfuck中，你正在使用位，它們構成字節。

來源

2014-03-31 15:39:41

This answer應該適合你;它對什麼特徵使語言完成的定義有一個非常具體的定義。

下面是它的要點：

一般來說，對於命令式語言是圖靈完備的，它需要：

有條件的重複或條件跳轉的形式（例如， while，if + goto）

讀寫某種形式的存儲的一種方式（例如，變量，磁帶）

來源

2014-04-17 21:50:34 FracturedRetina

是的，事實上，甚至像'bool memory = false;如果（內存）{內存=真實;}'是圖靈完備，但是，爲了保持事情的公平，圖靈添加了所有這些'規則'是無限的。因此，如果應該是'while'（所以你可以重複無限），'memory'應該是'int'或者'byte'（儘可能大，但是從技術上講，即使是bool也是可以的，因爲一個字節只有8位）和內存也應該是一個數組，例如：'int memory [30000]; while（memory [0]）{memory [0] + = 1;}'熟悉？ – YoYoYonnY

修改後的Brainfuck版本的圖靈完備性

回答

相關問題