8

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.

Eric Yu
  • 161
  • 3
  • 8
    It is allowed to write answers to your own questions. You should do that and then accept your answer, so that the question shows up as solved in the question list. – sepp2k Dec 22 '12 at 23:27

2 Answers2

2

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:

  1. A form of conditional repetition or conditional jump (e.g., while, if+goto)

  2. A way to read and write some form of storage (e.g., variables, tape)

Community
  • 1
  • 1
rootmeanclaire
  • 808
  • 3
  • 13
  • 37
  • Yes, and in fact, even something like `bool memory = false; if (memory) {memory=true;}` is turing complete, however, in order to keep things 'fair', Turing added the 'rule' for all of these to be infinite. Thus if should be `while` (So you can repeat infinite), `memory` should be a `int` or `byte` (As large as possible, but technically even a bool will be OK, since a byte is just 8 bits) and memory should also be a array, giving something like: `int memory[30000]; while (memory[0]) {memory[0]+=1;}` Familiar? – yyny Jun 16 '15 at 15:31
1

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.

Anubian Noob
  • 13,426
  • 6
  • 53
  • 75