CODEWITHSUNDEEP
brainfuckcomputability
Eric Yu
Eric Yu

Reputation: 161

Turing-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.

Upvotes: 8

Views: 556

Answers (2)

rootmeanclaire
rootmeanclaire

Reputation: 838

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)

Upvotes: 2

Anubian Noob
Anubian Noob

Reputation: 13596

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.

Upvotes: 1

Related Questions