User:I am islptng/TCP1
This is an esolang with a register.
Syntax
please allow this 'not c or python or basic' comment!
nvar stands for a number or a variable.
<nvar reg = nvar
>var var = reg
/var reg = -reg + var
{var while var>0 do
} end while : print(chr(reg)) ? reg = getchar()
Computational class
This language is Turing-complete, because it's quite easy to implement 3-cell BF in it.
User:Cycwin's proof
Initialise: Say we have three variables:
>a>b>c
To increment the variable v:
<0>z<1/z/v>v
Decrement:
<1/v<v
We do have while loops, so this thing is TC!
Another proof
Minsky machine has three instructions: INC, DEC and JZ (which can be understood in this way). We have written the addition and subtraction of a variable above, so INC and DEC can be easily simulated. So, what we need now is:
- the judgment that a variable is equal to 0, and
- the conversion from JUMP instruction to code block format.
Let's solve the first problem first. We can judge by the following code. Here, the counter C1 is used as an example. If C1 is greater than 0, the variable I will be 0, otherwise the variable I will be 1. Tip: Because the logic of adding, subtracting and defining variables has been mentioned above, I will abbreviate them in the following code.
{C1
C1-＝1
T1＋＝1
T2＋＝1
}
I＝1
{T2
I＋＝1
T2-＝1
{I
I-＝1
}
}
{T1
T1-＝1
C1＋＝1
}
Then, we can use {I ...} to realize the loop when it is equal to 0.
Then we just need to realize the transformation of the labeled loop into this form.
Through observation, we can draw the following conclusion: each anaphora jump (i.e. : label ... JZ A, label ) can be transformed into {I A}.
For example:
:loopA block A :loopB block B jp R,loopB block C jp S,loopA
can be transformed into blockA blockB{S blockA {R blockB} blockC};
jp M,loopA block A :loopA :loopB block B jp N,loopB
can be{M blockA}block B{N blockB}.
To sum up, we have successfully found a way to convert TCP1 instructions into Minsky machine. Because minsky machine is Turing complete, TCP1 is Turing complete. Proved by User:Cycwin.