TypeInt

TypeInt

Designed by	User:GUAqwq
Appeared in	2023
Computational class	Turing complete
Major implementations	Implemented
File extension(s)	.ts_

TypeInt is a esolang which is created by User:GUAqwq. The program runs on an unbounded integer type array which is unbounded. It came out while User:GUAqwq was proving the turing completeness of TypeString:

"If there's only one character for this esolang, will it still Turing Complete?"

Overview

We call <some '*'s><int> value or ptr because they acts as a multilevel pointer.

Operation types:

ptr-  : set the value which ptr points to 0

ptr+  : increase the value which ptr points

value; : dynamic label, if there's the same value for more than 2 labels, first one works.

v0 v1 v2? : if v0 == v1 jump to labelv2

TC proof

Basic

Comment

pseudo code:

# blablabla
let a,b,c,d

target:

do nothing but commenting

code:

# for common comment
let for constants declaration (all of them should be replaced into exact integers when compiling)

Add Constant

pseudo code:

*A += n

known:

*A = a , n

target:

*A = a + n

code:

*A+
...(n times)

Set Constant

pseudo code:

*A = n

known:

*A , n

target:

*A = n

code:

*A-

*A+
...(n times)

Jump

pseudo code:

jp a

known:

a

target:

jump to label a.

code:

# a; in somewhere
0 0 a ?

Jump If Equal

pseudo code:

jp a if b==c

known:

a,b,c

target:

jump to label a if b == c

code:

# a; in somewhere
b c a ?

Copy

By copying, we can use side-effecting function freely. In order to avoid side-effects, we default to transfer parameters' copies instead of origins if the function is labeled by "(side-effecting)".

pseudo code:

*A = *B

known:

A,B,*B = n

target:

assign *B to *A

code:

let start,end
*A-
start;
jp end if *A==*B
*A+
jp start
end;

Counting

Increase

pseudo code:

*A++

code:

*A+

Decrease

pseudo code:

*B = *A - 1

caution:

*A have to be greater than 0, or the code won't stop.

code:

let C,start,end
*B = 0
*C = 1
start;
jp end if *A==*C
*B++
*C++
jp start
end;
*C = 0 # clear the temporary variable

Boolean Operation

Value

true := 1
false:= 0

Equal

pseudo code:

*C = (A==B)

code:

let T,end
jp T if A==B
*C = false
jp end
T;
*C = true
end;

Not

pseudo code:

*C = !A

code:

let T,end
jp T if A==true
*C = true
jp end
T;
*C = false
end;

OR

pseudo code:

*C = A | B

code:

let T,end
jp T if A==true
jp T if B==true
*C = false
jp end
T;
*C = true
end;

All Logic Gates

By combining NOT gates and OR gates, we can get all the logic gates we need. Here's my expressions:

a AND b  := a &  b
a NOR b  := a !| b
a NAND b := a !& b
a XOR b  := a ^  b

Condition

Compare

(side-effecting)

known:

*A = a, *B = b

target:

*EQ = (a==b), *GT = (a>b), *LT = (a<b), *A = *B = 0

Code:

let
loop;
jp eq if ((*A==0) & (*B==0))
jp gt if ((*A!=0) & (*B==0))
jp lt if ((*A==0) & (*B!=0))

*A--
*B--
jp loop

eq;
#EQ = true
#GT = false
#LT = false
gt;
#EQ = false
#GT = true
#LT = false
lt;
#EQ = false
#GT = false
#LT = true

if-elif-else & while

pseudo code:

if(a){A}
else if(b){B}
else (c){C}

while(d){D}
break;

code:

let A,B,C,if_end

jp A if a==true
jp B if b==true
jp C

A;
...
jp if_end
B;
...
jp if_end
C;
...
if_end;

let D,loop_end
D;
jp loop_end if d==false
...
jp D
loop_end;

To break, just jump to loop_end

Calculation

Add

(Side-effecting)

pseudo code:

*A += *B

code:

while(*B!=0)
{
    *B--
    *A++
}

Sub

(Side-effecting)

pseudo code:

*A -= *B

code:

while(*B!=0)
{
    *B--
    *A--
}

Mul

(Side-effecting)

pseudo code:

*C = *A * *B

code:

*C = 0
while(*B!=0)
{
    *B--
    *C += *A
}

Pow

(Side-effecting)

pseudo code:

*C = *A ** *B

code:

*C = 1
while(*B!=0)
{
    *B--
    *C *= *A
}

Div

(side-effecting)

pseudo code:

*C = *A / *B

code:

*C = 0
while(*A>=*B){
   *C++
   *A -= *B
}

Mod

(side-effecting)

pseudo code:

*A %= *B

code:

while(*A>=*B){
   *A -= *B
}

Turing Machine

Half-Bounded Tape

For an n-adic number, the ath digit m contributes m * n**a to the total.

For a Half-Bounded Tape, each cell correspond to a certain digit of an integer.

Let *T be a tape where data are all n-valued.

Read

pseudo expression:

*T[a]

expression:

*T/(n**a) % n

Write

pseudo code:

*T[a] = m

code:

*T -= *T[a]
*T += m * (n**a)

Registers

*I:=tape_pointer_register

*S:=state_register

Turing Machine

A Turing machine rule has the following components:

current_state read_symbol write_symbol direction next_state

or

A X Y D B

for short.

Let blank_symbol = 0, starting_state = 0, symbol_set_length = n.

state_amount can be any finite number.

Here's the code for ruleA X Y D B:

if(*S == A){
   if(*T[*I] == X){
       #break when Y:=halt
       *T[*I] = Y
       #*I-- when D:=L
       #*I++ when D:=R
       *S = B
   }
}

To assemble a Turing machine:

let n,T,I,S
while(true)
{
   ...#rule0
   ...#rule1
   ...#rule2
   ...#rule3
   
   ...
}

Congratulations! Now you've successfully proved that TypeInt is Turing complete!

Interpreters

• Interpreter written by User:Hakerh400