How many pairs of brackets in BF be sufficient enough to make it Turing Complete?












4














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










share|cite|improve this question









New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • "how many pairs of these brackets have to be used?" Can you clarify "have to be used". For example, what if I ask BrainF to count to $2^{1000000}$?
    – Apass.Jack
    2 hours ago












  • @Apass.Jack the minimum number of brackets
    – MilkyWay90
    2 hours ago












  • Oh, do you meant the minimum number of brackets to simulate an $n$-state Turing machine as a function of $n$? Anyway, can you give a nontrivial example that is as simple as possible?
    – Apass.Jack
    2 hours ago








  • 1




    @Apass.Jack Okay, I'm coming up with a buggy BF program which works for a one-state Turing Machine
    – MilkyWay90
    2 hours ago










  • @Apass.Jack Nevermind, it is way too hard for me. Basically make a BF interpreter for my programming language, Turing Machine But Way Worse, when it uses only two possible symbols (0 and 1) and remove the I/O and halting aspect completely
    – MilkyWay90
    1 hour ago
















4














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










share|cite|improve this question









New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • "how many pairs of these brackets have to be used?" Can you clarify "have to be used". For example, what if I ask BrainF to count to $2^{1000000}$?
    – Apass.Jack
    2 hours ago












  • @Apass.Jack the minimum number of brackets
    – MilkyWay90
    2 hours ago












  • Oh, do you meant the minimum number of brackets to simulate an $n$-state Turing machine as a function of $n$? Anyway, can you give a nontrivial example that is as simple as possible?
    – Apass.Jack
    2 hours ago








  • 1




    @Apass.Jack Okay, I'm coming up with a buggy BF program which works for a one-state Turing Machine
    – MilkyWay90
    2 hours ago










  • @Apass.Jack Nevermind, it is way too hard for me. Basically make a BF interpreter for my programming language, Turing Machine But Way Worse, when it uses only two possible symbols (0 and 1) and remove the I/O and halting aspect completely
    – MilkyWay90
    1 hour ago














4












4








4







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










share|cite|improve this question









New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











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







turing-completeness






share|cite|improve this question









New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 3 hours ago





















New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 3 hours ago









MilkyWay90

235




235




New contributor




MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






MilkyWay90 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • "how many pairs of these brackets have to be used?" Can you clarify "have to be used". For example, what if I ask BrainF to count to $2^{1000000}$?
    – Apass.Jack
    2 hours ago












  • @Apass.Jack the minimum number of brackets
    – MilkyWay90
    2 hours ago












  • Oh, do you meant the minimum number of brackets to simulate an $n$-state Turing machine as a function of $n$? Anyway, can you give a nontrivial example that is as simple as possible?
    – Apass.Jack
    2 hours ago








  • 1




    @Apass.Jack Okay, I'm coming up with a buggy BF program which works for a one-state Turing Machine
    – MilkyWay90
    2 hours ago










  • @Apass.Jack Nevermind, it is way too hard for me. Basically make a BF interpreter for my programming language, Turing Machine But Way Worse, when it uses only two possible symbols (0 and 1) and remove the I/O and halting aspect completely
    – MilkyWay90
    1 hour ago


















  • "how many pairs of these brackets have to be used?" Can you clarify "have to be used". For example, what if I ask BrainF to count to $2^{1000000}$?
    – Apass.Jack
    2 hours ago












  • @Apass.Jack the minimum number of brackets
    – MilkyWay90
    2 hours ago












  • Oh, do you meant the minimum number of brackets to simulate an $n$-state Turing machine as a function of $n$? Anyway, can you give a nontrivial example that is as simple as possible?
    – Apass.Jack
    2 hours ago








  • 1




    @Apass.Jack Okay, I'm coming up with a buggy BF program which works for a one-state Turing Machine
    – MilkyWay90
    2 hours ago










  • @Apass.Jack Nevermind, it is way too hard for me. Basically make a BF interpreter for my programming language, Turing Machine But Way Worse, when it uses only two possible symbols (0 and 1) and remove the I/O and halting aspect completely
    – MilkyWay90
    1 hour ago
















"how many pairs of these brackets have to be used?" Can you clarify "have to be used". For example, what if I ask BrainF to count to $2^{1000000}$?
– Apass.Jack
2 hours ago






"how many pairs of these brackets have to be used?" Can you clarify "have to be used". For example, what if I ask BrainF to count to $2^{1000000}$?
– Apass.Jack
2 hours ago














@Apass.Jack the minimum number of brackets
– MilkyWay90
2 hours ago






@Apass.Jack the minimum number of brackets
– MilkyWay90
2 hours ago














Oh, do you meant the minimum number of brackets to simulate an $n$-state Turing machine as a function of $n$? Anyway, can you give a nontrivial example that is as simple as possible?
– Apass.Jack
2 hours ago






Oh, do you meant the minimum number of brackets to simulate an $n$-state Turing machine as a function of $n$? Anyway, can you give a nontrivial example that is as simple as possible?
– Apass.Jack
2 hours ago






1




1




@Apass.Jack Okay, I'm coming up with a buggy BF program which works for a one-state Turing Machine
– MilkyWay90
2 hours ago




@Apass.Jack Okay, I'm coming up with a buggy BF program which works for a one-state Turing Machine
– MilkyWay90
2 hours ago












@Apass.Jack Nevermind, it is way too hard for me. Basically make a BF interpreter for my programming language, Turing Machine But Way Worse, when it uses only two possible symbols (0 and 1) and remove the I/O and halting aspect completely
– MilkyWay90
1 hour ago




@Apass.Jack Nevermind, it is way too hard for me. Basically make a BF interpreter for my programming language, Turing Machine But Way Worse, when it uses only two possible symbols (0 and 1) and remove the I/O and halting aspect completely
– MilkyWay90
1 hour ago










1 Answer
1






active

oldest

votes


















2














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.






share|cite|improve this answer










New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • Nice job! I see you worked on this in TNB!
    – MilkyWay90
    1 hour ago











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});






MilkyWay90 is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102363%2fhow-many-pairs-of-brackets-in-bf-be-sufficient-enough-to-make-it-turing-complete%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









2














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.






share|cite|improve this answer










New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • Nice job! I see you worked on this in TNB!
    – MilkyWay90
    1 hour ago
















2














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.






share|cite|improve this answer










New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • Nice job! I see you worked on this in TNB!
    – MilkyWay90
    1 hour ago














2












2








2






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.






share|cite|improve this answer










New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









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.







share|cite|improve this answer










New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this answer



share|cite|improve this answer








edited 58 mins ago





















New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









answered 1 hour ago









ais523

1363




1363




New contributor




ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






ais523 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • Nice job! I see you worked on this in TNB!
    – MilkyWay90
    1 hour ago


















  • Nice job! I see you worked on this in TNB!
    – MilkyWay90
    1 hour ago
















Nice job! I see you worked on this in TNB!
– MilkyWay90
1 hour ago




Nice job! I see you worked on this in TNB!
– MilkyWay90
1 hour ago










MilkyWay90 is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















MilkyWay90 is a new contributor. Be nice, and check out our Code of Conduct.













MilkyWay90 is a new contributor. Be nice, and check out our Code of Conduct.












MilkyWay90 is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102363%2fhow-many-pairs-of-brackets-in-bf-be-sufficient-enough-to-make-it-turing-complete%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei