completeness of a modified version of Brainfuck

Is Brainfuck Turing-complete if the cells are bits, and the + and - operations simply flip a bit? Is there a simple proof that Brainfuck-like languages are Turing-complete regardless of the cell size, or do I need to think of a program that simulates a Turing machine? How would I know if there isn't one?

EDIT: I found an answer to my question: Brainfuck with bit cells is called Boolfuck. Ordinary Brainfuck can be reduced to it, so Boolfuck is Turing-complete.

---

This answer should suit you well; it has a very specific definition of what features make a language turing complete.

Here's the gist of it:

In general, for an imperative language to be Turing-complete, it needs:

A form of conditional repetition or conditional jump (eg, while , if + goto )

A way to read and write some form of storage (eg, variables, tape)

---

A Turing complete language can "simulate any single-taped Turing machine." Brainfuck and Boolfuck are both Turing complete, because they follow the specifications.

Also note that if one is Turing complete, the other must be because they are nearly the same. With brainfuck, you are moving in bytes, but in boolfuck, you are using bits, which constitute bytes.

链接地址: http://www.djcxy.com/p/11630.html

上一篇: 限制c＃应用程序中的用户数

下一篇: Brainfuck修改版本的完整性