Strelnokoff
Strelnokoff is an esoteric programming language devised by Chris Pressey in 2001. It is a non-deterministic imperative programming language; each instruction updates the global state of the program, but there is no guarantee as to the order in which instructions are executed.
Although the above description makes it sound unusable, it is "usable for computation" if one adopts a rigorous programming style, sometimes used in other non-deterministic languages (such as Thue, from which Strelnokoff took inspiration) where every instruction is gated with as many guards as is needed to prevent that instruction from being executed at the wrong time.
Etymology
The name Strelnokoff comes from the name of a fictional brand of vodka that appeared in an SCTV skit.
History
Strelnokoff was originally released in 2001 in the form of an incomplete interpreter written in Perl, a single example program, and no explicit specification. This was christened "version 1.0".
At the end of 2023 the author started putting together a "version 1.1" of the language, a conservative update mainly intending to clarify the points of the language that the lack of a specification left open.
Syntax and semantics
Syntactically, Strelnokoff resembles BASIC. No line numbers are needed, however, as there is no guarantee as to the order that the program will be executed in anyway.
Each line contains an update statement of the form <variable-name> = <expression>.
The expression can consist of the common arithmetic expressions (addition, subtraction, multiplication, and division.) Division is integer divsion, with the exception that division by zero evaluates to zero. This exception leads to the idiom X / X which evaluates to zero if X is zero, and one otherwise.
Two relational operations are available as well, = and >. These evaluate to one if the relation is true, and zero if it is not.
Primitive values are integers and can be specified either in decimal or as symbols in single quotes, which equate to ASCII values.
Mulitplication is short-circuiting: if the left operand of a multiplication evaluates to zero, the right operand is not evaluated, thereby guarding against any side effects.
There is also a unary operator, PRINT CHAR, which acts as an identity function, except that it also produces output as a side-effect.
The ability to store arrays (possibly unbounded) in variables somehow was part of the original concept, but it was not implemented in the original implementation. Version 1.1 clarifies that arrays are not part of the language.
Example program
The following is a "Hello, world!" program implemented in Strelnokoff.
REM HELLO WORLD IN STRELNOKOFF REM CHRIS PRESSEY MARCH 24 2001 X = (X / X) * X + (X = 0) * (T = 0) * (PRINT CHAR 'H' - 'H' + 1) X = (X / X) * X + (X = 0) * (T = 1) * (PRINT CHAR 'e' - 'e' + 2) X = (X / X) * X + (X = 0) * (T = 2) * (PRINT CHAR 'l' - 'l' + 3) X = (X / X) * X + (X = 0) * (T = 3) * (PRINT CHAR 'l' - 'l' + 4) X = (X / X) * X + (X = 0) * (T = 4) * (PRINT CHAR 'o' - 'o' + 5) X = (X / X) * X + (X = 0) * (T = 5) * (PRINT CHAR ',' - ',' + 6) X = (X / X) * X + (X = 0) * (T = 6) * (PRINT CHAR ' ' - ' ' + 7) X = (X / X) * X + (X = 0) * (T = 7) * (PRINT CHAR 'w' - 'w' + 8) X = (X / X) * X + (X = 0) * (T = 8) * (PRINT CHAR 'o' - 'o' + 9) X = (X / X) * X + (X = 0) * (T = 9) * (PRINT CHAR 'r' - 'r' + 10) X = (X / X) * X + (X = 0) * (T = 10) * (PRINT CHAR 'l' - 'l' + 11) X = (X / X) * X + (X = 0) * (T = 11) * (PRINT CHAR 'd' - 'd' + 12) X = (X / X) * X + (X = 0) * (T = 12) * (PRINT CHAR '!' - '!' + 13) X = (T = X) * 0 + (X > T) * X REM RESET FLAG T = (X / X) * X + (X = 0) * T REM INCREMENT TICK
Computational class
Strelnokoff has long been thought to be "probably Turing-complete, or at least would be if it had unbounded arrays, because it's similar to Thue and arbitrary Turing machines can be translated to Thue", but there seems to have been nothing further than that conjecture for more than two decades since the language's inception.
Strelnokoff defines no limit on the integer values that its variables can take on. Also, the Perl implementation suggests there is no limit on the length of variable names, nor the number of variables that may be used in a program. Also, it seems reasonable to assume that if the program reaches a state where none of the instructions would have any effect if executed, we can consider the program to have halted. (Version 1.1 explicitly confirms these assumptions).
Under all these assumptions, one approach to proving that Strelnokoff is Turing-complete that seems promising would be to simulate a Minsky machine with two of the variables as integer counters, using as many other variables as needed to properly guard all the assignments. However, there is a complication: a counter machine needs to update both the counter and the "step index" in a single instruction, but in Strelnokoff, an assignment can only update a single variable. So if the counter and the "step index" are in different variables, there is a hazard that the counter will be updated zero times, or multiple times, before the step index is changed to refer to the next step.
So the trick to get around this is to store more than one piece of information in a single Strelnokoff variable. Under the assumption that variables can take on negative values, a single bit and a natural number, independent of each other, can be combined and stored in a single Strelnokoff variable. This bit can then be used as an "interlock" to prevent the step index from being updated during an instruction execution, before the counters have finished being updated.
Chris Pressey used this technique to show how arbitrary Alternating 1-based Minsky machines can be translated to Strelnokoff programs, showing that Strelnokoff is Turing-complete. For the details of the proof, see Strelnokoff Turing-completeness proof.
Even without making a negative values assumption, it may be possible to encode one or more bits of information as prime factors in the variable's value. X MOD Y can be implemented in Strelnokoff as X - (X / Y) * Y (due to integer division), and this can be used to detect the presence or absence of a prime factor such as 2. A translation using this technique has not yet been developed however.