Natyre

Overview

Natyre is an infinitely branching counter machine, which is a new class of counter machines I am representing along with this language (which is the simplest of its kind I managed to think of). Essentially, an infinitely branching counter machine differs from ordinary counter machine in its way of functioning; with ordinary counter machines, branching happens under one specific circumstance - in most of them, if the counter/register contains 0 and decreasing is attempted. In infinitely branching counter machines, the counter/register is compared to numbers that appear according to a rule and of which there is an infinite supply - a potential for branching infinitely.

Program and execution

A program can have any finite number (as long as it is larger than zero) of instructions and counters. Counters are unbounded and initially 0. Each instruction has an unique identifier to it. The program execution begins in the first defined instruction.

There is only one type of instruction (simply called the instruction in this language).

<identifier> <counter> <branch1> <branch2>

There is the unique identifier for the instruction. Then there is the counter that the instruction manipulates. Then there are two branches, defining where the execution is transformed next (naturally, those identifiers must exist in the program). An instruction might look like this:

14 A 2 skip1

This would be instruction '14', which would operate on counter A. It would branch to either instruction '2' or to instruction 'skip1'.

This instruction works the following way. It first increases the given counter by one (like Minsky Machine's INC). Based on the value of the counter, after the increasing, the execution branches. If the number just became an event-number (see below), then the second branch (branch2) is taken. More commonly, the counter's value is not one of those numbers, and the first path (branch1) is taken. Done for the instruction. Then the 'next' (where the control was transferred) instruction is executed, and so forth. The system does not halt.

On branching numbers

In this language's glossary, the term event-number is used to refer to numbers that cause the other event, the rarer branching, to happen. There is an infinite amount of them, but the gaps between them will keep increasing, as well. To generate these numbers is easy: Have q and n, both initially 0. Increase n by 1, then add it (n) to q. This (q) is the first event-number. Then repeat (increase n, add n to q). The first 10 event-numbers are:

1
3
6
10
15
21
28
36
45
55

I chose this sequence because (as far as I can see) it is the simplest one that fulfills the condition (which is necessary, according to my reasoning) that the gap/distance between event-numbers is such that the gap between n and n's successor is always larger than the gap between n's predecessor and n.

To calculate nth event-number, one can use: n(n+1)/2. For example, the 4th: 4(4+1)/2 = (16+4)/2 = 20/2 = 10.

To calculate n's position in the sequence of event-numbers (assuming that n is an event-number), one can use: (squareroot[8n+1]-1)/2. For example, the position of 28: (squareroot[8*28+1]-1)/2 = (squareroot[224+1]-1)/2 = (15-1)/2 = 14/2 = 7.

Proof of Turing-completeness via Minsky Machine translation

The Turing-completeness of this language can be shown by translating Minsky Machine (which is Turing-complete, as is well known) into it. As ever, there are likely several ways to do this, but I will be using the shortest and the most comprehensible method I have managed to devise. If you find a simpler method, please let me hear. In this method, MM's INC can be simulated with 1 instruction and DEC will need 5.

Each counter of the MM program is simulated using two counters in Natyre. There is the counter and its zero-level. Decreasing a counter is done by increasing the zero-level associated with that counter. The zero-level will always be smaller than or equal to its respective counter.

The values of the counters and their zero-levels are event-numbers (and 0, initially). When inspecting the values, one must first calculate the positions of the values within the sequence of event-numbers, then (using the position numbers) subtract the zero-level from its respective counter. For example, if A were 21 and Azero were 10, (squareroot[8*21+1]-1)/2 = 6 and (squareroot[8*10+1]-1)/2 = 4, thus the simulated register's value is 6-4 = 2.

The INC instruction is translated into:

x A x next

First A (or whatever register) is increased by one. Then, if A's number is not one of the event-numbers, branch 1 goes to the very same line, and thus the addition is repeated until A's value is an event-number. Once that happens, branch 2 will take the control flow to the simulation of the 'next' instruction.

The DEC instruction is more complicated but not overtly so:

x A y z
y B x f
f A f e
e B e suc
z B z fai

Here, for the sake of readability, A's zero-level register is marked as B. A is of course whatever register.

Lines x and y (or rather, instructions x and y) form a tight-knit detection loop for values of A and B. DEC simulation's execution starts at x. A is increased. If A became event-number, one thing would be known: A and B are equal, because B can never be larger than A - if B were smaller, it would already have become event-number during this two-instruction loop, at instruction y. But in this case A became event-number, so move to line z. There, since A has already reached event-number, increase B until it reaches event-number too. Then branch to fai, as the simulated counter is not decreased. B was increased to next event-number because the difference of the counter (A) and its zero-level (B) must be maintained to keep the simulated counter's value intact - the values are now larger, but since both were increased, the difference (calculated from the positions of those numbers in the sequence of event-numbers) remains the same. The simulated counter was not decreased because A and B were equal - the simulated counter's value was (and still is) 0.

Now the other possibility. Starting again at x. A is increased but does not become event-number, so branch 1 is taken, to instruction y. There, B is increased. If B did not become event-number, it might yet be equal to A, it simply cannot be known yet, so continue looping by returning to x... But if B just became event-number, that means B is smaller than A, which means that A and B are not equal, and thus the simulated counter is larger than 0, and can be decreased. On to instruction f. There, loop until A becomes event-number, and then move to instruction e. A was risen to next event-number to preserve the distance of A and B. Since it was established that the simulated counter can be decreased, that is at last done here, by increasing B until it becomes the next event-number, thereby decreasing the distance of A and B (again, calculated from the positions of those numbers in the sequence of event-numbers), and thus the simulated counter has been decreased. Control is moved to suc, which is where the control flow goes if the simulated counter could be successfully decreased.

The HALT instruction simply becomes:

x halt x x

It simply increases counter called 'halt' and transfers control to that instruction again no matter what the counter's value becomes. Once 'halt' becomes non-zero the outer level (an interpreter, a human programmer) can know the simulation has reached the simulated halt, and can terminate the system that is running Natyre. (Remember, Natyre has no termination of its own. HALT's translation was included because it is often useful to know that a program has halted.)

Example translation and execution

Here is a Minsky Machine program that simply increases and decreases counters A and B rather mindlessly until eventually halting with A = 6 and B = 0.
1 inc A 2
2 inc A 3
3 inc A 4
4 dec A 4 5
5 inc B 6
6 inc B 7
7 inc A 8
8 inc A 9
9 dec B 7 10
10 halt

Translation to Natyre using the method above (note: there is a translator tool available):

1 regA 1 2
2 regA 2 3
3 regA 3 4
4 regA 5 8
5 zeroA 4 6
6 regA 6 7
7 zeroA 7 4
8 zeroA 8 9
9 regB 9 10
10 regB 10 11
11 regA 11 12
12 regA 12 13
13 regB 14 17
14 zeroB 13 15
15 regB 15 16
16 zeroB 16 11
17 zeroB 17 18
18 halt 18 18

Once run (simulation is over once 'halt' counter becomes non-zero), the program has the following values in counters (excluding the 'halt' counter):

regA - 91
zeroA - 28
regB - 15
zeroB - 15

regA and zeroA simulate counter A, regB and zeroB simulate counter B. The positions of the values 91 and 28 in the sequence of event-numbers are (squareroot[8*91+1]-1)/2 = 13 and (squareroot[8*28+1]-1)/2 = 7. Simulated counter A's value is thus 13-7 = 6. For B, both counters are 15, so (squareroot[8*15+1]-1)/2 = 5. Simulated counter B's value is 5-5 = 0. (Of course, if counter and its zero-level are equal, it can be known without calculating that the simulated counter is 0.)

Interpreter and translator

A Natyre interpreter written in Python can be found here. Since the language has no output, the interpreter prints the state of all the counters in the program after each Natyre instruction, along with 'next' telling where control was transferred.

A Minsky Machine to Natyre translator, also in Python, can be found here. Give a Minsky Machine program file as argument, receive Natyre program as output.

Authorship

This language is the very result of my quest to simplify my favourite computational system, Minsky Machine. In some respect I feel I might have succeeded; while there is more complexity behind the scenes, so to speak, what the user faces is a very simple, clean language with only one kind of instruction. Whereas the language came together quickly, the process leading to the spark of the idea took years of practically using (mainly in context of Turing-completeness proofs via MM to target language translation) and pondering on Minsky Machines. Without the existence of Minsky Machine, I doubt this would exist either. (I doubt I would, given time, invent the actual Minsky Machine.) So, massive thanks to Marvin Minsky for his invention, which will never cease to amaze me.

Sadly, Minsky himself died some months before I got this idea (in 2016), so there never was a time I could have flung an e-mail to him and see what he thought. Sometimes I wonder if his mind drifted close by (yet not close enough) this idea all those decades ago (in the 1960s) or whether it was ever even near it. In any case, I feel like an INC of progress has again been made on counter machines (whether anybody cares or not). The publication of this language was delayed till 2017, for more than half a year, because I could not decide on a name for it.

-- Keymaker, 8th March 2017