Techno

Techno is a minimal esolanguage by Keymaker, mostly designed in 2019, completed and released in 2020.

Language description

Techno is essentially a one-instruction language where the instruction sets a value to a memory location; the location and the value are yielded by the two expressions, which are defined by the given program. After that, the value at memory location 0 is increased by one (called the pulse in this language's terminology). A step is done.

The memory is an unbounded array (beginning at index 0) consisting of unbounded non-negative cells, all initially 0, aside from the values in the beginning of the memory that are initialized by the program (although any cell may be initialized to 0 just as well).

Once the program data is read, first the comments (beginning with ~ and lasting until the end of line) are removed. Then all new-lines and spaces are removed, and if there is a character that is not one of the recognized characters (0123456789,()[]<>+-*/%) the program is rejected. The program has three parts: initial memory, expression for location, expression for value. Initial memory describes a finite part of the memory array from its beginning. The shortest possible initial memory is [0]. Each expression is placed between a single < and >.

An expression is evaluated from left to right, the inner-most parentheses first. There is no operator precedence, so 1+3*2 evaluates to 8, not 7. To get 7, use parentheses: 1+(3*2). Parentheses must be matching, and different types of parentheses may not mismatch (for example, ([2)] is not valid). The expression inside [] parentheses is evaluated until it is an integer, and then the [int] is replaced by the value currently stored at that location in memory. [100] evaluates to the value of location 100 in memory. [[2]+1] evaluates to the value of location 2 in memory plus 1, which then evaluates to that number's location's value. Every two units - a value or a value currently in parentheses - must have one operator (+-*/%) between them, and there may not be an operator before or after all units. 1+-2 is not valid because there are two operators, 3[4] is not valid because there is no operator between the units, and [[123*]] is not valid because there is an operator without a unit on its other side.

Once the expressions have been evaluated, into the memory location yielded by the first expression is set the value yielded by the second expression. Then the pulse: location 0 is increased by one. During the execution (and initialization) location 0 can be altered like any other location, but at the end of a step it will always be increased by one (for example, if set to 3, the value will be 4 once the step is completed).

The program has three ways of halting (successfully), and it does not matter which of them is used to halt the program if halting is wanted. The halting happens immediately once the part of expression that causes it is being evaluated; the current step is abandoned and execution ends, the state of the memory remains as it was at the end of the previous step. The causes of halting are:

• The result of x-y yielding a value less than 0.
• Attempting to divide by zero, x/0.
• Attempting to modulo by zero, x%0.

Example program

[0]<[0]+1><[0]*[0]>

The initialization part is the simplest possible; the first cell is set to 0, all others are initially 0 by default. The program sets the value of [0]*[0] to location [0]+1 repeatedly, never halting. Here is the state of the memory for each of the first five steps (remember that the pulse happens on each step after the expressions are evaluated and the memory is set):

1 0 0 0 0 0 0 ... ; left=[0]+1=0+1=1, right=[0]*[0]=0*0=0; m[1]=0, m[0]++
2 0 1 0 0 0 0 ... ; left=[0]+1=1+1=2, right=[0]*[0]=1*1=1; m[2]=1, m[0]++
3 0 1 4 0 0 0 ... ; left=[0]+1=2+1=3, right=[0]*[0]=2*2=4; m[3]=4, m[0]++
4 0 1 4 9 0 0 ... ; left=[0]+1=3+1=4, right=[0]*[0]=3*3=9; m[4]=9, m[0]++
5 0 1 4 9 16 0 ... ; left=[0]+1=4+1=5, right=[0]*[0]=4*4=16; m[5]=16, m[0]++

Computational class

Techno is Turing-complete. A simple way to prove it is to translate I/D machine (which is Turing-complete) into Techno (a translator can be found at the bottom of the page). Translating a simple program IID creates the following Techno program:

[0,0,1,0,0,0,1,0,0,0,1]<(([[0]%3*3+0+2])*([1]+11))+(([[0]%3*3+1+2])*([1]+11))+(([[0]%3*3+2+2])*(1))><(([[0]%3*3+0+2])*([[1]+11]+1))+(([[0]%3*3+1+2])*([[1]+11]+1))+(([[0]%3*3+2+2])*([[1]+11]))>

Here is the program in more readable form with new-lines, spaces, and minimal comments (the coloring not part of the actual source code, obviously):

[0,0,1,0,0,0,1,0,0,0,1]
<
  (([[0]%3*3+0+2]) * ([1]+11)) ~I

               +

  (([[0]%3*3+1+2]) * ([1]+11)) ~I

               +

  (([[0]%3*3+2+2]) * (1)) ~D
>
<
  (([[0]%3*3+0+2]) * ([[1]+11]+1)) ~I

               +

  (([[0]%3*3+1+2]) * ([[1]+11]+1)) ~I

               +

  (([[0]%3*3+2+2]) * ([[1]+11]))> ~D
>

I/D machine has an unbounded array of unbounded non-negative cells, and a data pointer that points to a value in the memory array. There is a finite program, consisting of two types of commands. A program never halts, and after the last instruction the flow returns to the first instruction. The two commands are I which increases by one the value of the cell the data pointer is pointing at, D that sets to the data pointer's value the value of the cell it points at.

In this translation, Techno's pulse in location 0 is used to simulate the instruction pointer. The data pointer is stored in location 1. A truth table begins at location 2. The I/D machine memory array begins at (n*n)+2 and continues unbounded.

Since there is no control flow in Techno, the expression (both of them, using the same method) calculates every I/D command's effect, and only selects the correct value based on what is the current command (location 0 value moduloed by the number of commands in the I/D program). The truth table is used to get 0s for the unintended results and 1 for the intended result. It is a simple lookup table; it has n binary strings (split into individual 0/1 values) of size n, where n is the number of commands in the I/D program. For every command, the digit corresponding its ordinality is 1, the others are 0. (In this example case with 3 commands, the data is 100 010 001. For a case with 4 commands it would be 1000 0100 0010 0001.) Each command accesses the table at location [0]%3*3+x+2 ([0] gets location 0's value, %3 moduloes it by the number of I/D commands (3 here), *3 multiplies it by 3 (again the number of I/D commands), +x adds the command's ordinal (0, 1, 2), and +2 adds 2 because the truth table begins at location 2). The value acquired from the truth table (0 or 1) is used to multiply the value yielded by the simulated I/D command. The effects of all commands are calculated on each cycle, but only the results for the command that is being executed are kept (multiplied by 1), whereas those not relevant are discarded (multiplied by 0). All of the results are summed together and the 0 values vanish in the process.

Fortunately, to keep things simple, simulating either of the I/D machine's two commands can be done with only one Techno step per I/D command. A single I/D command manipulates one memory location at a time - I increases a value in memory, D alters an internal register (the data pointer). Then the next command is chosen, which can be simulated with the pulse.

Tracing the program in this example, the first step (executing instruction I) should yield 11:1, which means that the first cell of the array (the simulated I/D machine's memory begins at location 11, and currenly the data pointer points at cell 0 - that very cell). As all the I/D cells are initially 0, the current cell's value increased by one is 1. First instruction done. The next step (instruction I) yields 11:2, which means that the same first cell has been increased by one again, its new value now 2. The next step (instruction D) yields 1:2, meaning that the data pointer's value, stored at location 1, is set to value 2 - the value of the cell the data pointer points at (right before it is changed). After the last instruction the program begins at the first instruction (I) again, and the step yields 13:1, which means that cell 2 (11+2=13) is increased by one (its value going from 0 to 1). And so forth...

Ambient Techno

As soon as I was done with proving Techno Turing-complete, I began to think of the obvious question: Can it be Turing-complete without the mechanism that essentially drives it (the pulse)? It can be; Ambient Techno is a variant of the language that is exactly like Techno but without the pulse - that is, location 0 is not automatically increased at the end of a step. Here is a method for translating Minsky Machine into such variant (a translator at the bottom of the page).

s1 inc A s2
s2 inc A s3
s3 dec A s3 s4
s4 inc B s1

The programs created using this method use prime factorization extensively. The value kept in location 1 is used to store the current values of the registers and the current state of the program (that is, which instruction is currently being executed or will be executed next). The program only ever manipulates location 1 (it could have used location 0 because Ambient Techno does not have the pulse that would automatically increase it, but by not using that specific location this method also allows translating MM to native Techno). To keep this text more readable I use phrases like "to see if x is in the data" - which simply means moduloeing the value in location 1 by x and seeing if the result is 0; if it is, the data contains at least one instance of x amongst its factors, if not, the data has no x in its factors. To add an instance of x, multiply the value by x, to remove an instance of x, divide the value by x.

As the first step in the translation, assign unique primes for all registers and instructions. In this example case there are two registers, A and B, which are associated with primes 2 and 3. Then, associate a prime number for each instruction/state; in this case there are four (s1, s2, s3, and s4) and the primes associated with them are 5, 7, 11, and 13.

The initial memory is [0,5,1]. Location 0 is never used, location 1 contains the current state of memory registers (1 signifies that both A and B are 0) and the initially chosen instruction/state (s1, associated with 5); 1*5=5. Location 2 is 1, a constant used by a truth table. The rest of the memory is 0s.

The first expression is <1>. The target of the operation is always location 1.

The second expression is considerably more complex. It is the sum of the values yielded by each instruction's simulation. Whatever this expression yields is a value that contains the values of all the registers and the new current state. Each instruction yields either a 0 or a non-zero that contains all the new data. On each step only one of the parts will return a non-zero value, all others return 0, and as they they are summed the 0s vanish.

A commonly used code snippet is [2+([1]%x)] where x is a prime number that is searched from the data (location 1). First the data value is moduloed with x. If x is found in the value, the result of this operation is 0, otherwise some other non-zero value. The memory begins with 0 a 1 (where a is the data cell) followed by an infinite number of 0-cells. [2+([1]%x)] yields either 1 or 0; if x is found in the value (meaning [1]%x is 0), it returns 1 (from location 2), for any other value it returns 0 (retrieving the 0 from one of the 0-cells in locations 3, 4, 5, 6, and so on, for as far as need be). Getting the inverse of this value is simple; [2+[2+([1]%x)]]. It does all previously mentioned, and after it has the 0 or 1, it gets value from location 2 or 3 - which are 1 and 0, so value 0 ([2+0]) returns 1, value 1 ([2+1]) returns 0.

There are three types of instructions; INC, DEC, and HALT. The expressions could be more optimized but they are this way for clarity and simplicity of code generation.

INC looks like this:

( ([2+([1]%5)]) * ([1]/5*2*7) )

This is INC code for this particular example's instruction s1 but the principle is similar for all. ([2+([1]%5)]) returns either 0 or 1, 1 if the current state (s1) - presented by prime 5 - is found in the data. This multiplies the result yielded by the following parentheses - thus, anything multiplied by 0 becomes 0, anything multiplied by 1 remains whatever it is. The next parentheses, ([1]/5*2*7) yields the new state of the data. First [1] is divided by 5, thus removing the current state's signifier 5 from it. Then that value is multiplied by 2, which means increasing register A, as instruction s1 does. Then the value is multiplied by 7, which is the prime associated with the instruction s2, which is what the next state is in this case. That is all. If this instruction were not the currently chosen instruction, this all yields 'nonsense', but as it is annulled by multiplying it with 0 (which the first part of the expression yields in case the instruction is not the currently chosen one), it does not matter.

DEC looks like this:

( ([2+([1]%11)]) * (([2+([1]%2)] * ([1]/11/2*11)) + ([2+[2+([1]%2)]] * ([1]/11*13))) )

This DEC code is this example's instruction s3. Similarly to INC's code, the code has a first part (that yields either 0 or 1) that multiplies the value yielded by the second part. The beginning of the expression is like INC's; ([2+([1]%11)]). This part sees if prime 11 (the one associated with instruction s3) is found in the data, similarly returning 1 if it is, 0 if not. The second part consists of two expressions that are summed - one of them will always yield 0 and the other something else. The first of these, ([2+([1]%2)] * ([1]/11/2*11)) first sees if A register's prime (2) is found in the data and returns 1 or 0 accordingly. Then ([1]/11/2*11) changes the data; the data is divided by 11 (instruction s3's prime) to remove it, then that result is divided by 2 to decrease A register by one, then that result is multiplied by 11 (instruction s3's prime) to set that instruction as the next-to-be (this is the success case, when the register is larger than 0 and is decreased). The other expression, ([2+[2+([1]%2)]] * ([1]/11*13)) works similarly, but with the difference that its first part gets the negation of the 0 or 1 that tells if the prime 2 was found in the data. Since this yields the opposite of what the code in the success-case yields, it is known that the success-part and failure-part will have different values; if the value is 1 in the success-part, it will be 0 in the failure-part, and vice versa. The correct result (as in, what is wanted in this case) will be multiplied by 1 and retained, while the wrong result will be multiplied by 0 and removed - all according to whether register A can be decreased or not. The part that changes data, ([1]/11*13) is similar to that in the success-case; first the current instruction's (s3) prime (11) is removed, then the resulting value is multiplied by 13 (the prime associated with instruction s4), thus setting that instruction as the next-to-be (as this is the failure case). Notice that the expression did not divide by 2 because in this case it is known that the data does not contain 2, and thus A register is 0 and could not be decreased. As mentioned, the sum of the two parts multiplied by the first part's result (0 or 1), and the result will either be 0 in case the instruction was not currently chosen or a non-zero value that contains the new register values and the new state, in case the instruction was meant to be executed.

HALT looks like this:

( 0/([2+[2+([1]%7)]]) )

The above example program does not contain HALT; in this example this particular instruction is associated with the prime 7. This is simpler than the other instructions. 0 is divided by an expression that yields the negation of the value that is yielded by the check that sees whether 7 (this instruction's prime) is found in the data. If it is found, 1 is returned, and its negation is 0. Attempting to divide by 0 is one of the ways to halt a Techno program, and that is what happens. If 7 was not found, 0 is yielded, its negation 1, and thus 0 is divided by 1, which is a successful operation that yields 0. Thus, whenever the instruction is not meant to be executed, it always yields 0, and when it is executed it halts the program.

The complete program, generated by the translator from the MM program above, is:

[0,5,1]<1><( ([2+([1]%5)]) * ([1]/5*2*7) ) + ( ([2+([1]%7)]) * ([1]/7*2*11) ) + ( ([2+([1]%11)]) * (([2+([1]%2)] * ([1]/11/2*11)) + ([2+[2+([1]%2)]] * ([1]/11*13))) ) + ( ([2+([1]%13)]) * ([1]/13*3*5) )>

If tracing the program, the first step should yield values 1:14 (14=2*7, 2 being A's value 1 and 7 marking the instruction s2 as the new state). Then 1:44 (44=4*11, 4 being A's value 2, 11 marking the instruction s3 as the new state). Then 1:22 (22=2*11, 2 being A's value 1, 11 the instruction s3). And so on. Following the execution is easy because every completed Techno step means that a MM instruction has been simulated - the registers have been altered and the new state chosen.

Software

techno.py - Techno interpreter written in Python. Near the bottom of the program there is a line marked with a comment that, when commented out, makes the interpreter an Ambient Techno interpreter.

idtotechno.py - I/D Machine to Techno translator. The I/D program is a string in the program code, change that to translate a different program.

mmtotechno.py - Minsky Machine to Ambient Techno (and normal Techno) translator.

-- Keymaker, 7th July 2020