Nsryjdtyk

BrainF is a programming language that makes itself Turing-Complete using only 8 symbols (6 if you ignore I/O).

The two most notable ones that pushes it to Turing-Completeness are '['and ']', essentially BF's gotos and labels.

Normally, programs in BF use multiple sets of '', but I was wondering, exactly how many pairs of these brackets have to be used to make BF Turing-Complete?

More simply, what is the least amount of brackets that you'd need to simulate an n-state Turing Machine (Give the number of brackets for 1, 2, and three state Turing Machines)?

Notes:

We are assuming an infinite tape and no computational limits.

It is a 2-symbol Turing Machine

I'm not 100% sure that it's impossible to do this with two sets of brackets. However, if the cells of the BF tape allow unbounded values, three sets of brackets are enough. (For simplicity, I'll also assume that we can move the tape head left past its starting point, although because this construction only uses a finite region of the tape, we could lift that restriction by adding sufficiently many > commands at the start of the program.) The construction below requires assuming Artin's conjecture to be able to compile arbitrarily large programs; however, even if Artin's conjecture is false, it will still be possible to show Turing-completeness indirectly via translating an interpreter for a Turing-complete language into BF using the construction below, and running arbitrary programs via giving them as input to that interpreter.

The Turing-complete language that we're compiling into unbounded BF is The Waterfall Model, which is one of the simplest known computational models. For people who don't know it already, it consists of a number of counters (and initial values for them), and a function $f$ from pairs of counters to integers; program execution consists of repeatedly subtracting 1 from every counter, then if any counter $x$ is 0, adding $f(x,y)$ to each counter $y$ (the program is written in such a way that this never happens to multiple counters simultaneously). There's a Turing-completeness proof for this language behind my link. Without loss of generality, we'll assume that all counters have the same self-reset value (i.e. $f(x,x)$ is the same for all $x$); this is a safe assumption because for any specific $x$, adding the same constant to each $f(x,y)$ will not change the behaviour of the program.

Let $p$ be the number of counters; without loss of generality (assuming Artin's conjecture), assume that $p$ has a primitive root 2. Let $q$ be $p(1+s+s^2)$, where $s$ is the lowest power of 2 greater than $p$. Without loss of generality, $2q$ will be less than $2^p$ ($2q$ is bounded polynomially, $2^p$ grows exponentially, so any sufficiently large $p$ will work).

The tape arrangement is as follows: we number each counter with an integer $0 leq i < p$ (and without loss of generality, we assume that there's a single halt counter and number it $2$). The value of most counters is stored on tape cell $2^i$, with the exception of counter 0, which is stored on tape cell $2q$. For each odd-numbered tape cell from cell -1 up to and including $2^{p+1}+2p+1$, that tape cell always holds 1, unless it's immediately to the left of a counter, in which case it always holds 0. Even-numbered tape cells that aren't being used as counters have irrelevant values (which might or might not be 0); and odd-numbered tape cells outside the stated range also have irrelevant values. Note that setting the tape into an appropriate initial state requires initialising only finitely many tape elements to constant values, meaning that we can do it with a sequence of <>+- instructions (in fact, only >+ are needed), thus no brackets. At the end of this initialisation, we move the tape pointer to cell -1.

The general shape of our program will look like this:

initialisation [>>>[ >$times(2^p-1)$ [ <$times(2p)$ ]>-] adjustment <<<]

The initialisation puts the tape into the expected shape and the pointer on cell -1. This is not the cell to the left of a counter (0 is not a power of 2), so it has value 1, and we enter the loop. The loop invariant for this outermost loop is that the tape pointer is (at the start and end of each loop iteration) three cells to the left of a counter; it can be seen that the loop will thus only exit if we're three cells to the left of counter 2 (each other counter has a 1 three cells to its left, as to have a 0 there would imply that two counters' tape positions were 2 cells apart; the only two powers of 2 that differ by 2 are $2^1$ and $2^2$, and $q$'s binary representation changes from strings of $0$s to strings of $1$s or vice versa at least four times and thus cannot be 1 away from a power of 2).

The second loop repeatedly loops over the counters, decrementing them. The loop invariant is that the tape pointer is always pointing to a counter; thus the loop will exit when some counter becomes 0. The decrement is just -; the way we get from one counter to the next is more complex. The basic idea is that moving $2^p-1$ spaces to the right from $2^x$ will place us on an odd-numbered cell $2^p+2^x-1$, which is to the right of any counter ($2^p$ is the last counter, $2^x-1$ is positive because $x$ is positive); modulo $2p$, this value is congruent to (by Fermat's Little Theorem) $2^x+1$. The innermost loop repeatedly moves left by $2p$ spaces, also not changing the index of the tape cell modulo $2p$, and must eventually find the cell congruent to $2^x+1$ modulo $2p$ that has the value (which will be the cell to the left of some counter); because of our primitive root requirement there's exactly one such cell ($2q-1$ is congruent to $-1$ modulo $2p$, and $2^{log_{2,p}(r)+1}-1$ is congruent to $2r-1$ for any other $r$, where $log_{2,p}$ is the discrete logarithm to base 2 modulo $p$). Additionally, it can be seen that the position of the tape pointer modulo $2p$ increases by $2$ each time round the middle loop. Thus, the tape pointer must cycle between all $p$ counters (in order of their values modulo $2p$). Thus, every $p$ iterations, we decrease every counter (as required). If the loop breaks partway through an iteration, we'll resume the decrease when we re-enter the loop (because the rest of the outermost loop makes no net change to the tape pointer position).

When a counter does hit 0, the middle loop breaks, taking us to the "adjustment" code. This is basically just an encoding of $f$; for every pair $(x,y)$, it adds $f(x,y)$ to the tape element which is the same distance left/right of the current tape pointer as counter $y$'s tape location is left/right of counter $x$'s tape location (and then removes the tape pointer back to where it started). Whenever $xneq y$, this distance turns out to be unique:

• The difference between two powers of 2 is a binary number consisting of a string of 1 or more $1$s followed by a string of 0 or more $0$s (with the place values of the start of the number, and the start of the $0$ string, depending on the larger and smaller respectively of $x$ and $y$); thus all those differences are distinct. * As for the difference of a power of 2 and $q$, it must contain at least two transitions between strings of $1$s and $0$s ($q$ contains at least four such transitions, the subtraction can only remove 2), thus is distinct from all differences of two powers of two, and these differences are obviously also distinct from each other.

For $x=y$, we obviously find that the distance moved is 0. But because all $f(x,y)$ are equal, we can just use this as the adjustment for the current cell. And it can be seen that the adjustment code thus implements the "when a counter hits 0" effect for every counter; all the cells that actually represent counters will be adjusted by the correct amount, and all the other adjustments will affect non-counter even-numbered cells (the difference between two even numbers is even), which have no effect on the program's behaviour.

Thus, we now have a working compilation of any program in The Waterfall Model to BF (including halt behaviour, but not including I/O, which isn't needed for Turing-completeness) using only three pairs of brackets, and thus three pairs of brackets are enough for Turing-completeness.