1.1

1.1 is a Turing-complete esoteric programming language based on string replacement in a string data buffer, arbitrary control flow among states, but without self-modifying code.

1.1 is given as an example that Donald Knuth gives for how one could define computability in a precise mathematical way in the bible The Art of Computer Programming, chapter 1.1. The book says that the language is essentially equivalent to the one given in the book A. A. Markov, The Theory of Algorithms (Trudy Mat. Inst. Akad. Nauk. 42 (1954), 1–376), later revised and enlarged by N. M. Nagorny (Moscow: Nauka (1984); English edition: Dordrecht: Kluwer, 1988). The example is present in both the second edition (1973) and the third edition (1997) of vol. 1. of the bible. The bible does not seem to refer to this example anywhere later, instead programs are presented in other languages, such as MIX (Knuth).

An 1.1 program is has a finite sequence of states, numbered consecutively, the first state being the initial state, and the last state a halt state. The program consists of a specification of four pieces of data for each of the states: a needle string, a replacement string, the next state in case of successful replacement, and the next state in case of failure. The input for running a program is a string, which becomes the initial value of the data buffer. In each execution step, the execution searches for the first occurrence of the needle string of the current state in the data buffer, and if found, replaces it with the replacement string. After that, the state is changed to one of the two next states given in the program for the current state, depending on whether the needle string was found or not found. If the execution enters the halt state, the program halts and the data buffer becomes the final output.

Implementations

• Interpreter in Perl by User:Sxakalo
• Interpreter in Node.js by User:Hakerh400