2L Turing-completeness proof

From Esolang
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 command2L blockNote
+
 _ 
 _ 
 _ 
 * 
-
 __________ 
 __+__+____ 
 ___++___+_ 
 ______+___ 
 _+__*__+__ 
 _+___+____ 
 +________+ 
 __+____+__ 
 ________+_ 
>
 _______ 
 __+____ 
 _+___+_ 
 ___+___ 
 _+__+*_ 
 +_____+ 
 __+_+__ 
 _____+_ 
<
 _______ 
 __+____ 
 _+___+_ 
 ___+___ 
 _+*_+__ 
 +_____+ 
 __+_+__ 
 _____+_ 
[
 _____+___ 
 _+_______ 
 _+_____+_ 
 ______+__ 
 ____+____ 
 ___+____+ 
 _____++__ 
 ___+___+_ 
 _________ 
 _________ 
 __+_+____ 
 +________ 
 _______+_ 
 _+_______ 
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:
_____+
__++__
___++_
_+____