Insercle

Insercle is an esoteric programming language that User:ais523 accidentally created by attempting to do an esolang-related proof in their head, misremembering the language they were dealing with during one step of the proof, and ending up with a language that was actually unrelated to the original language or the problem they were working on, but interesting enough to write about anyway.

Semantics

An Insercle program is specified, like a finite-state automaton as a set of states, each of which transitions to an other state upon reading a particular symbol (from a particular alphabet specified by the program). When performing a transition, the Insercle program produces output, making a finite-state transducer; however, the output is restricted to always consist of two symbols, the first of which is a copy of the symbol being read, and the second of which is specified by the transition. One state is specified to be a halt state and causes the program to halt when that state is reached.

These reads and writes are attached to a queue, so that the program reads its own output.

Oddly, Insercle is easily capable of input (via specifying the input initially provided to the program, before it starts reading its output), but not of output, making it a rare case of an "input-only" language.

Syntax

Each symbol and state in an Insercle program is named using a single non-whitespace Unicode character. The program consists of a list of specifications for transitions, separated by whitespace; each transition consists of five characters in the sequence input, old state, new state, first output, second output (where the input and first output are always the same). For example, 0AB01 means "when popping 0 in state A, change to state B and push 01".

Computational class

Insercle is Turing-complete. The basic idea behind a proof of this is to observe that the program can (by counting the number of symbols it has seen, via switching between a different set of states for symbols in odd positions and in even positions) choose to ignore all the symbols that were just a copy of the popped symbol (via specifying a transition that's the same regardless of what symbol is there). This effectively allows the creation of an arbitrary finite-state transducer in which each symbol of input transduces to exactly two symbols of output (via ignoring every second symbol in both the input and the output). By dedicating one symbol to mean "ignore this symbol", it is then possible to produce an arbitrary finite-state transducer in which each symbol of input transduces to at most two symbols of output; and such a system can almost directly implement Ignorant 2C (via adding one symbol as an "end of string" marker, which expands to 0 followed by the "end of string" marker).

The above proof can be trivially modified to prove Insercle complete even with only two Insercle symbols – the idea is to choose a string length n, and for every block of n Insercle symbols to represent one of the following: a 2C symbol, the "ignore this symbol" symbol, or the "end of string" symbol. Because Ignorant 2C produces an output symbol only after entirely reading all input symbols it depends on, the fact that the symbols are read a bit at a time does not matter.

See also

• Genera Tag, which has a similar "fixed expansion ratio" behaviour to Insercle (and to which Insercle can be trivially compiled)