Universal Turing-completness Proof

From Esolang
Jump to navigation Jump to search

It is a Turing-completness Proof for various langugaes via translation of 3-cell BF(ALWCIDFEC) in this languages.

What needs to be in this languages

  • At least 3 variables with unbounded numbers that can be incremented and decremented
  • If statements
  • Labels and possibility to goto to that labels back and forward

Instead of if statements and labels you can use while if it is exist I will use Batch in this Proof

Declaraton of variables

Declare 3 variables:a, b, c with value zero(0). It will simulate tape with 3 unbounded cells

In Batch:

set a=0
set b=0
set c=0

It will mean that instruction will always apply on same cell and instead of instructions < and > you simply change cell which you will use.

Incrementing and Decrementing

Instruction are translated is simple: you use instructions to increment and decrement cell

Increment cell a in Batch:

set /a a=%a%+1

Decrement cell a in Batch:

set /a a=%a%-1

Increment cell b in Batch:

set /a b=%b%+1

Decrement cell b in Batch:

set /a b=%b%-1

Increment cell c in Batch:

set /a c=%c%+1

Decrement cell c in Batch:

set /a c=%c%-1

Loops(Using Labels and If statements)

Translating [

For translating [ you make if statement which will goto label which marks where loop is over if variable is zero. Then you declare label which marks where loop is starting

In Batch(variable a):

if %a% == 0 goto end
:start

] if language has Less and Greater

If language has Less and Greater, then you can translate ] like that: First, make an If Greater statement that will goto back to start of a loop if variable is zero, Second, declare a label which marks end of a loop

In Batch(variable a):

if %a% GTR 0 goto loop
:end

] if language has not Less and Greater

If language has not Less and Greater, then you can translate ] like that: First, make an If statement that will goto to end of a loop if variable is zero, Second, make goto that will goto back to the start of a loop, Third, declare label which marks end of a loop

In Batch(variable a):

if %a% == 0 goto end
goto start
:end

If language has while loops

You simply make a while loop that runs until variable is zero