We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Mhm!/Turing-completeness proof
Jump to navigation
Jump to search
This proves Mhm!'s Turing-completeness by implementing Bitwise Cyclic Tag.
Program
^( 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
]
Visualized
Taken from the debugger provided by User:Aadenboy's interpreter, shown with --showloose=b,b.,c...
a[ X] b[ 2] c[14]
b vvvv
b a[0] b[0] c[1] d[1] e[1] f[1] g[1] h[1]
bb vvvvv
bb a[ X] b[ X]
bc vvvvv
bc a[ X] b[ 0] c[ X]
bd vvvvv
bd a[ X] b[ 0] c[ X]
be vvvvv
be a[ X] b[ 1] c[ X]
bf vvvvv
bf a[ X] b[ 1] c[ X]
bg vvvvv
bg a[ X] b[ 1] c[ X]
bh vvvvv
bh a[ X] b[ X] c[ 0]
cba vvvvv
cba a[ X] b[ 1] c[ 0] d[ 1] e[ X]
cca vvvvv
cca a[ X] b[ 0] c[ 1] d[ X]
cda vvvvv
cda a[ X] b[ 1] c[ X]
cea vvvvv
cea a[ X] b[ 1] c[ 1] d[ X]
cfa vvvvv
cfa a[ X] b[ 1] c[ 1] d[ 0] e[ X]
cga vvvvv
cga a[ X] b[ 1] c[ 0] d[ X]
cha vvvvv
cha a[ X] b[ 1] c[ 0] d[ 1] e[ X]
cia vvvvv
cia a[ X] b[ 1] c[ 0] d[ 1] e[ 0] f[ X]
cja vvvvv
cja a[ X] b[ 0] c[ 1] d[ 0] e[ X]
cka vvvvv
cka a[ X] b[ 0] c[ 1] d[ 0] e[ X]
cla vvvvv
cla a[ X] b[ 0] c[ 1] d[ 0] e[ X]
cma vvvvv
cma a[ X] b[ 1] c[ 0] d[ X]
cna vvvvv
cna a[ X] b[ 1] c[ 0] d[ 1] e[ X]
coa vvvvv
coa a[ X] b[ 1] c[ 0] d[ 1] e[ 0] f[ X]