1
$\begingroup$

If you take Brainfuck and modify '<' to move the tape head to the beginning of the tape, would this modified Brainfuck still be Turing complete?

It feels like it should be, but I can't wrap my head around how you'd emulate a Turing machine using (or proper Brainfuck for that matter). It feels like you'd need to come up with a scheme to partition the tape in a way that allows you to address certain points in the memory.

$\endgroup$
1
  • $\begingroup$ I don't think it can be since there's no way of moving one step back. $\endgroup$
    – Pål GD
    Oct 15, 2021 at 12:28

1 Answer 1

0
$\begingroup$

It is Turing complete. The details depend a bit on whether the tape and/or the numbers in the cells are unbounded. (If neither are, then even regular Brainfuck is not Turing complete.)

If the cells can hold unbounded integers, then we can easily use $k$ cells to simulate a $k$-counter machine. Those are Turing complete already for $k = 2$.

If the tape is infinite, we can simulate regular Brainfuck as follows. Partition the tape into pairs of cells, each of which simulates a single regular BF cell. The idea is that cell $2n$ contains a $1$ if the simulated pointer is at that pair and $0$ if not, and cell $2n+1$ holds the contents of the simulated cell. When we start to execute a simulated instruction, the pointer is on top of the $1$ at cell $2n$.

If we want to read or modify the current cell's value, just step right, perform the operation, return to the origin, and step 2 cells to the right until we see a $1$. If we want to take a step right, we decrement, move right twice, and increment.

The difficult part is moving the simulated pointer to the left. To do this, we return to the origin and increment. Now we have two simulated cells with a $1$ on the even part. Then we repeatedly move the leftmost $1$ one cell to the right (as if simulating a step to the right) until the next simulated cell also contains a $1$. In that case we break out of the loop, remove said $1$, return to the origin and walk to the remaining $1$ two steps at a time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.