Mhm!/Turing-completeness proof

← Back to Mhm!

This proves Mhm!'s Turing-completeness by implementing Bitwise Cyclic Tag.

^( safeguard

building the program
) move to program
^) skip first cell to prevent killing the program
^^^( ^^) ^^^( ^^( left boundary
^) ^^^( ^^) ^^^^( ^^^) ^^^) ^^^^( ^^^( ^^^( ^^) ^^^( ^^( 0
^) ^^^( ^^) ^^^^( ^^^) ^^^) ^^^^( ^^^( ^^^( ^^) ^^^( ^^( 0
^) ^^^( ^^) ^^^^( ^^^) ^^^) ^^^^( ^^^(      ^^) ^^^( ^^( 1
^) ^^^( ^^) ^^^^( ^^^) ^^^) ^^^^( ^^^(      ^^) ^^^( ^^( 1
^) ^^^( ^^) ^^^^( ^^^) ^^^) ^^^^( ^^^(      ^^) ^^^( ^^( 1
^) ^^^( ^^) ^^^( right boundary
^( ^^[^(]

builing the queue history
) move to queue history
^^( boundary
^) move to first queue
nested an extra level deeper to allow left move
^^^^( left boundary of queue
^^^) ^^^^^( ^^^^) ^^^^) ^^^^^( ^^^^(       1
^^^) ^^^^^( ^^^^) ^^^^) ^^^^^( ^^^^( ^^^^( 0
^^^) ^^^^^( ^^^^) ^^^^) ^^^^^( ^^^^(       1
^^^) ^^^^( right boundary of queue
^^^( ^^^[^^^(] ^^^) move to start of queue
^) move to next queue
^^^^( preemptive
^( back to first queue

running the program
^^^[ check if current queue is empty
  [(] ) back to program
  
  cycle program once
  ^)
  ^^) ^^[
    ^^(
    ^( ^^[^(]
    ^^)
  ]
  ^^(

  ^^^) shift for 0 check
  ^^^[ if bit == 0
    ) go to queue
    ^^^) skip first bit
    ^^^[ copy queue
      ^) ^^^) ^^^^^( ^^^^) ^^^^) ^^^^^( ^^^^( ^^^^( build next bit in queue
      ^( ^^^^[ set bit to 1 if necessary
        ^) ^^^^) ^(
        [(] exit
      ]
      [(] sync
      ) )
      ^^^) advance to next bit
    ]
    ^) ^^^) ^^^^( add right boundary of new queue
    ^^^( ^^^[^^^(] ^^^) move to start of new queue
    ^) ^^^^( ^( next preemptive
    [(] go to safeguard to exit
  ]
  [(] sync
  ) ^^^( reset for 1 check
  ^^^[ if bit == 1
    ) go to queue
    ^^^[ copy queue
      ^) ^^^) ^^^^^( ^^^^) ^^^^) ^^^^^( ^^^^( ^^^^( build next bit in queue
      ^( ^^^^[ set bit to 1 if necessary
        ^) ^^^^) ^(
        [(] exit
      ]
      [(] sync
      ) )
      ^^^) advance to next bit
    ]
    
    [(] ) go back to program
    cycle program once more
    ^)
    ^^) ^^[
      ^^(
      ^( ^^[^(]
      ^)
      ^^)
      [(]
    ]
    [(] )
    ^^(
    
    ) ^^^( ^^^[^^^(] ^^^) move to start of current queue
    ^^^^[ if first bit == 1
      ^) ^^^) ^^^^^( ^^^^) ^^^^) ^^^^^( ^^^^( ^^^^( build next bit in queue
      [(] ) go back to program
      ^^^[ set bit to 1 if necessary
        ) ^^^^)
        [(] exit
      ]
      [(] sync
      ) ) ^( sync
      [(] exit
    ]
    [(] sync
    ) ) move back to queue
    ^) ^^^) ^^^^( add right boundary of new queue
    ^^^( ^^^[^^^(] ^^^) move to start of new queue
    ^) ^^^^( ^( next preemptive
    [(] go to safeguard to exit
  ]
  [(] sync
  ) ) move to current queue for check
]