<p>All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The &quot;parent language&quot; <a href="https://en.wikipedia.org/wiki/P%E2%80%B2%E2%80%B2" rel="nofollow noreferrer">P''</a> on which Brainfuck is based is explicitly specified as having &quot;increment/decrement this cell modulo m&quot; instructions.</p>
<p>So is Brainfuck with arbitrary-sized integer cells (no wraparound) actually Turing Complete? If not, is there some proof that it is not? For example, can we compute bounds on the BigNum-Brainfuck Busy Beaver numbers?</p>

CC BY-SA 4.0
2021-06-30T06:13:19.197Z
[Counter machines](https://en.wikipedia.org/wiki/Counter_machine) (with as little as 2 counters) are Turing complete. It should be straightforward to simulate these in Brainfuck with just a constant number of bigint cells.
Emil Jeřábek
CC BY-SA 4.0
2021-11-04T15:33:59.420Z
The Esolangs WIki has a section on their brainfuck page explaining variants that are known to be Turing complete inculding the one discussed on this question: https://esolangs.org/wiki/Brainfuck#Computational_class
Potato44
<computability><pl.programming-languages><turing-machines>
Is BigInteger-based Brainfuck Turing Complete?
user513093
# Is BigInteger-based Brainfuck Turing Complete?

(Asked by: username_0 on 2021-06-29)

All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The "parent language" [P''](https://en.wikipedia.org/wiki/P%E2%80%B2%E2%80%B2) on which Brainfuck is based is explicitly specified as having "increment/decrement this cell modulo m" instructions.

So is Brainfuck with arbitrary-sized integer cells (no wraparound) actually Turing Complete? If not, is there some proof that it is not? For example, can we compute bounds on the BigNum-Brainfuck Busy Beaver numbers?

**Tags:** computability, pl.programming-languages, turing-machines
> **Comments:**
> **username_1**: [Counter machines](https://en.wikipedia.org/wiki/Counter_machine) (with as little as 2 counters) are Turing complete. It should be straightforward to simulate these in Brainfuck with just a constant number of bigint cells.  
> **username_2**: The Esolangs WIki has a section on their brainfuck page explaining variants that are known to be Turing complete inculding the one discussed on this question: https://esolangs.org/wiki/Brainfuck#Computational_class  

---

## 0 answers

