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.
Talk:Kak
Turing-completness
Can someone prove that it is Turing-complete or not? --ChuckEsoteric08 (talk) 12:51, 5 July 2022 (UTC)
This is Turing complete!
First of all, congratulations for inventing this.
I think I've found a way to prove that this esolang is TC. The reduction target is well... The Exasperation Machine, but not the standard TEM. This TEM uses % to toggle a bit, replacing the 1 and 0 instructions. I named this variant Alternating Exasperation Machine and it is Turing complete.
We'll use the following block layout
0 = 0 0 1 1 0 0 0 0 0 1 = 0 0 0 0 0 0 1 0 0
Let the pointer be normalized at the first bit in the current block.
For the sake of my own sanity, let's define a macro } as !<!, which is basically ! but without the bit flip.
We can map AEM instructions to Kak like this
| AEM | Kak |
|---|---|
> |
}}}}}}}}}
|
< |
<<<<<<<<<
|
/ |
}}}}}} ?!<?!} <<<?<?< }}?<?< }}?<?< }?<<
|
\ |
}}}}}} ?<}?<}?<}?<} <<<<<<< ?!?!<?!<< <?<} ?!<?!} <?! <<<<
|
% |
}!!}}!<<<<<<
|
This should hopefully prove the language TC, if we can initialize the first block and expand the tape. That might require us to change the tape layout a bit, but I think this is a pretty good for now. Rainwave (talk)