Escape from the tarpit (Robbers)

Question

This is a cops-and-robbers challenge based around defining languages and proving they are Turing complete.

This is the robbers' thread. The cops' thread is here.

Robbers

The cops will post definitions of Turing-complete languages. Your task is to crack them by proving that they are indeed Turing complete. See the cops' challenge for more details and formal specifications.

Answer 1

ais523's answer - Blindfolded Arithmetic

(I hope my proof is understandable. I can't check my own proof e.g. with a Try it online! link so I'm not sure)

All code in this post will be Python pseudocode, with rep n: repeat n times. All conditionals must be either 0 or 1.

It's provable that the value of i is always >0 in the program execution, so i/i always give 1.

Define some building blocks:

if c: a = a + b is equivalent to d = b * c; a = a + d; assuming d is unused.
So, let (statement) be if c: statement where c can be some condition.

b = b * 2**N (where N is a compile-time constant) is equivalent to

rep N: b = b + b

b = a / 2**N is equivalent to

b = i / i
b = b * 2**N
b = a / b

b = a % 2**N is equivalent to

b = a / 2**N
b = b * 2**N
b = a - b

---

Any 2-symbol Turing machine with N states can be written like this:

while True:
    if state == 0:
        # process state 0
    if state == 1:
        # process state 1
    .
    .
    .
    if state == HALTING_STATE:
        0 / 0
    .
    .
    .
    if state == N-1:
        # process state N-1
    state = newstate

where each # process state block looks like this

# optional (not all states need this)
tape.move_left()

# optional
tape.move_right()

# optional
tape.flip()

new_state = a if tape.value() else b

This needs to be translated to BFA compatible code.

---

Two variables i and a will be used to represent the tape and state (and tape as well)

The content of i at each wraparound:

• N least significant bits are equal to 2**state (i.e., the state'th significant bit is on, all other bits are off)
• The rest of bits form the right half of the tape.

The content of a at each wraparound:

• The left half of the tape.

The tape pointer is on the least significant bit of a.

---

At the beginning of each loop, N bits are inserted between the tape part and the state part in i:

d = i / 2**N
d = d * 2**N
i = i - d
d = d * 2**N
i = i + d

At each # process state i block, the structure of i is:

• M-N least significant bits: the remaining part of the old value of state (state >> i). (where M = 2*N - i)
• N next LSB: (partial) value of new_state (or 0 if it's not defined yet in that loop)
• Rest: Tape.

Of course M is a compile time constant.

(as an exception, the "process halting state" block can be implemented as

if i%2: b = b - b; b = b / b;

or equivalently (assume c isn't used)

c = i % 2; b = i / i; if c: b = b - b; b = b / b;

)

---

More rewriting:

• (tape.move_left()) (the outer () stands for conditional, as always)

  # allocate a free bit on (i)
  b = i / 2**M
  (i = i + b)
  # copy that bit from (a) to (i)
  b = a % 2
  b = b * 2**M
  (i = i + b)
  # remove a byte from (a)
  b = i/i
  (b = b + b)
  a = a / b
  

• (tape.move_right())

  # allocate (M+1) bits at the end of (a)
  (a = a * 2**(M+1))
  
  # copy that from (i) to (a)
  b = i % 2**(M+1)
  (a = a + b)
  
  # remove the (M) bits from (a) that is over-copied from (i)
  b = i/i # now b==1
  rep M: (b = b + b)
  a = a / b # if the conditional fails a = a / 1 is a no-op.
  
  # clear that bit on (i)
  b = a % 2
  b = b * 2**M
  (i = i - b)
  
  # remove the bit from (i)
  b = i / 2**(M+1)
  b = b * 2**M
  (i = i - b)
  

• (tape.flip())

  b = a % 2
  b = b * 2
  (a = a - b)
  b = i/i
  (a = a + b)
  

• (new_state = a if tape.value() else b)

TODO

---

There are 2 remaining issues:

• Only the bits to the left of the pointer is outputted, and
• if not tape_value(): tape.move_left() (and the equivalent move_right) is not directly supported.

To solve those problems,

• A TM with only a half of the tape is still TC.

You can interlace the positive-index cells with the negative-index ones, and replace every movement with a double-movement (doubling the number of states). You'll also need to mark two cells at the left with special symbols so you know to shift by one and turn around (1 extra symbol; 1 extra state), and you'll need to have a reversed copy of every state for when you're in negative-land and every movement is backwards (again doubling the number of states).

(source)

So, it's possible to:

1. Make the tape from 2 interleaving infinite tapes.
2. One of them only have one 1 denoting the right end of the tape. The other is used to store data.
3. At program halt, instead of immediately exiting, move right until hit the end of the tape.

So the whole tape are stored in the right half (i.e., i) and readable at program termination.

---

Am I still missing something?