Timeline for How many pairs of brackets are sufficient to make Brainfuck Turing complete?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2019 at 23:54 | comment | added | Ørjan Johansen | I think the middle brackets can be removed. (1) Make the inner loop end at the counter cell itself, when it's 0, and a different nearly-always 0 cell (with the same position (mod p)) when it's not. That way the adjustment can behave differently in each case. (2) Absorb the decrement into the adjustment for the previous i, and some cleanup of the secondary cell into the next one. (3) Double all values and adjustments so that relevant cells are always even, then irrelevant ones can be kept odd and automatically nonzero. (Optional 4) One i can increase irrelevant cells to keep them non-negative. | |
| Jan 5, 2019 at 18:54 | comment | added | Ørjan Johansen | Oh so you did (just before I said my brain refused to be in math mode, so there's my excuse :P). I guess I found out k=0 was sufficient, then. I think Wikipedia's Erdős–Turan_construction gives a polynomially growing (and presumably O()-optimal?) one if you use just the first half of the elements (the other half repeats (mod p)). | |
| Jan 5, 2019 at 17:04 | comment | added | ais523 |
@ØrjanJohansen: Right, I think I mentioned that construction in #esoteric (some time after I wrote this post)? All you actually need is a Golomb ruler for which each element is distinct modulo the number of elements, and there are various ways to construct those (although finding optimal ones is hard; the longest I've found (via brute force) is [0, 1, 3, 7, 20, 32, 42, 53, 58] for p=9).
|
|
| Jan 5, 2019 at 4:56 | comment | added | Ørjan Johansen |
I think I found a much simpler (as in requiring no prime number theory) counter placement: 2p*2^i+2i.
|
|
| Jan 5, 2019 at 2:32 | comment | added | Ørjan Johansen | I think you need s to be at least p+2. When s=p+1, q is 1 less than a power of 2. | |
| Jan 4, 2019 at 5:34 | history | edited | ais523 | CC BY-SA 4.0 |
fix unfinished sentence
|
| Jan 4, 2019 at 5:20 | vote | accept | MilkyWay90 | ||
| Jan 8, 2019 at 0:34 | |||||
| Jan 4, 2019 at 5:20 | comment | added | MilkyWay90 | Nice job! I see you worked on this in TNB! | |
| Jan 4, 2019 at 5:20 | review | First posts | |||
| Jan 4, 2019 at 10:02 | |||||
| Jan 4, 2019 at 5:16 | history | answered | ais523 | CC BY-SA 4.0 |