Goto machine

Goto machine is a computational model invented by User:TBPO, inspired by Turing machine.

Memory and syntax

The memory of the program consists of:

• A map from each symbol to a symbol;
• Position of the machine, a symbol;
• State of the machine, a symbol.

Every symbol point to 0 by default. The machine is on 0 and has state 0 by default. The program always begins with the list of symbols surrounded with parentheses. It's the list of base symbols. It must contain 0.

Symbols:

• All base symbols are symbols.
• (x,y) is a symbol, where x and y are symbols.

The rest of the program is the list of declarations in form:

ABCD

where all arguments are symbols. Names that aren't symbols are variables - they are wildcards that can be replaced by any symbol that match, althrough they must be consistent in the instruction. In CD part there can be only symbols that appeared in AB part.

# starts a comment.

Execution

During each step the program scans through declarations. If the machine meets one of requirements, state of the machine is changed and a new step begins. If nothing is found, the machine just sets the machine's position to the value under current symbol.

Generally, the declaration of form ABCD does the following:

• Is A value under current symbol and B the state of the machine?

• If yes:

• Set the state of the machine to D.
• Set the machine's position to C.
• Jump to the start of the program.

• If no, jump to next instruction.

The program halts if all of these requirements are satisfied:

• The position and state of the machine and the value under current symbol is the same as at some point in the past,
• Every symbol visited between the moment and now had the same value at the moment as has now.

Numerals and I/O Handling

Let's define Pair numeral system as $ (S,I) $, where $ S $ is any symbol and $ I $ is a set, such that:

• $ S\in I $
• $ \forall x(x\in I\to (x,S)\in I) $

Where $ (a,b) $ is ordered pair of a and b. Note that $ S $ is equivalement of 0 and $ (x,S) $ is equivalement of $ x+1 $. S-Pair numeral is a numeral which belongs to Pair numeral system $ (S,I) $.

At the start of the program, an input is taken and saved in the map so that each Unicode character from the input is saved at a 0-Pair numeral corresponding to its position in the input, starting from 1. For example, if input is \x02\x03\x01, then (0,0) is set to ((0,0),0), ((0,0),0) to (((0,0),0),0) and (((0,0),0),0) to (0,0). Input string is terminated with 0.

Output is the reverse process - when the program halts, the machine is teleported to (0,0) and does the following:

• Is the value under current symbol 0-Pair numeral bigger that 0?

• If yes:

• Convert the value under current symbol into a decimal number.
• Convert the number into a Unicode character, then print it.
• Move to (x,0), where x is the current symbol.

• If no, terminate.

Syntactic sugar

We can introduce a syntactic sugar for numbers to make programming easier. 0-Pair numerals are written in decimal notation. S-Pair numerals are written S*n, where n is a number written in decimal notation.

Examples

Cat program

(0)

Looping counter

Incrementing the machine's state:

(0) 0 x 0 (x,0)

Incrementing the machine's state and position:

(0) x y (y,0) (y,0)

Incrementing the cell under the machine: [TO REVISION]

(0,1)
x 0 (x,0) 1
x 1 0 0

NOP

(0 1 M R)
0 0 1 (M,1) #init
0 (M,y) y (M,y) #halt
x (M,y) 0 (R,0) #modify
x (R,0) (x,0) (M,(x,0)) #retrieve

It systematically cleans the input until it encounters 0, then halts and prints nothing. [TO REVISION]

Hello world

Here is the program that prints "Hello, world!":

(0 M R)
0 0 1 (M,1) #init
x (0,y) y (0,y) #halt
#modify
x (M,1) 72 (R,72) #H
x (M,2) 101 (R,101) #e
x (M,3) 108 (R,108) #l
x (M,4) 108 (R,108) #l
x (M,5) 111 (R,111) #o
x (M,6) 44 (R,44) #,
x (M,7) 32 (R,32) #space
x (M,8) 119 (R,119) #w
x (M,9) 111 (R,111) #o
x (M,10) 114 (R,114) #r
x (M,11) 108 (R,108) #l
x (M,12) 100 (R,100) #d
x (M,13) 33 (R,33) #!
x (M,14) 0 (0,0) #end
#retrieve
x (R,0) (x,0) (M,(x,0))
x (R,y) 0 (R,0)