Smooth transition to a second term

Smooth transition to a second term

Paradigm(s)	Functional
Designed by	User:Hakerh400
Appeared in	2020
Computational class	Unknown
Major implementations	Not implemented yet
File extension(s)	.txt

Smooth transition to a second term is an esoteric programming language.

Overview

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.

I/O format

Input and output are strings of bits.

Syntax

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 arg1 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

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 $\mathbb {Z}$, otherwise add bit 0.

Transitions

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).

Computational class

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.

Examples

(TODO)

Interpreters

Not implemented yet.