Smooth transition to a second term
|Major implementations||Not implemented yet|
Smooth transition to a second term is an esoteric programming language.
In this language, there are terminals, non-terminals and transitions.
A terminal (abbreviated term) is a number or an identifier. A number is always a non-negative integer. Identifiers consist of alphanumerics and cannot start with a digit.
A non-terminal (abbreviated nterm) is a transition invocation and it contains one or more arguments.
A transition is a transformation that can be applied to the memory. There are two types of transitions: smooth and rough transitions. They are explained in the next paragraphs.
Input and output are strings of bits.
Source code consists of two or more terms and zero or more nterms. Each transition is associated with at least one term in any given point in time during program execution. Each term is represented either as a literal number (for example
123) if it appears in an expression, or as
(term 123) if it appears as a top-level term. Each term that is not a top-level term must be bound to a nterm argument of at least one nterm. Each pair of nterms that contain at least one term with the same value contains paired nterms. Non-paired nterms must be encapsulated into a single smooth transition, or either multiple or none rough transitions (will be explained later).
Nterms can be either native or derived. Native nterms are represented as
(nterm name (arg1 arg2) result) where
name is the name of the nterm and
arg2 are formal arguments. The
result is an expression containing a transition and a function that transforms the arguments into a transition parameters. Transition reference must be bound to at least one rough transition invocation inside the same nterm or there must be at least two different terms (with different value) that can transform the arguments for the same transition invocation parameters. Parameters can be mapped back to arguments by applying the inverted function if it belongs to at least one native nterm. Native nterms cannot be represented (they are provided by the interpreter).
A function consists of keyword
func, then function name and arguments-result pairs. Example:
(func f ((arg1 arg2) result1) ((arg3 arg4) result2) )
Memory consists of a 4D grid and each grid cell contains a bit. Initially, starting from the cell with coordinates
(0 0 0 0) and applying the Miorovichov's algorithm fill the entire grid by adding bit 1 in each cell that corresponds to the Miorovichov's ordinal number that is a prime number in , otherwise add bit 0.
Each transition can be invoked via a non-terminal. Smooth transition can invert (flip) at most one bit at a time and transfer the control to a term (terms map to nterm indices in the source code). Rough transitions can transform the entire grid by adding a grid cell and shifting Miorovichov's indices by any number of cells to any direction (interpreter should keep track of the shifting index in order to be able to generate the rest of the grid at runtime).
The language is Turing-complete if there will be smooth transition to a second term for any program whose second term can be derived. If there will be no smooth transition, or no second term, then it must be rough by definition and the language is not Turing-complete.
Not implemented yet.