2L Turing-completeness proof
Jump to navigation
Jump to search
It can be proven that 2L is Turing-complete by making a translation table from Brainfuck (a known Turing-complete language) to 2L. This document shows how to translate any Brainfuck program (minus input and output, which are not necessary for Turing-completeness) to 2L.
None of this is even vaguely optimal; there are infinitely better ways to do anything you could do by copying in these blocks. This page only serves to prove that 2L is Turing-complete.
Simply take the 2L blocks and stack them horizontally, starting with this block:
_ _ _ _ +
Brainfuck command | 2L block | Note |
---|---|---|
+ | _ _ _ * | |
- | __________ __+__+____ ___++___+_ ______+___ _+__*__+__ _+___+____ +________+ __+____+__ ________+_ | |
> | _______ __+____ _+___+_ ___+___ _+__+*_ +_____+ __+_+__ _____+_ | |
< | _______ __+____ _+___+_ ___+___ _+*_+__ +_____+ __+_+__ _____+_ | |
[ | _____+___ _+_______ _+_____+_ ______+__ ____+____ ___+____+ _____++__ ___+___+_ _________ _________ __+_+____ +________ _______+_ _+_______ |
For sub-loops, you will need to put the bottom block down farther:
__+_+____ +________ _______+_ _+_______ |
] | ______ _+____ +___+_ __+___ ___+__ ______ ______ ______ ______ _____+ __++__ ___++_ _+____ |
For sub-loops, you will need to put the bottom block down farther:
_____+ __++__ ___++_ _+____ |