Formula

Formula is an esoteric programming language created by User:ais523 in 2006 as an exploration of the boundaries of the wire-crossing problem.

Syntax

A Formula program consists of a mathematical formula in one or more unknowns that evaluates to a real number; for instance, xy is a valid Formula program. Subscripts can be used on variables so there is an infinite stock available. The following mathematical operations are supported:

• Addition
• Subtraction
• Multiplication
• Division
• Exponentiation
• Sin, cos, tan (in radians) and their inverses

Semantics

Each variable in the formula corresponds to a variable in the program; all variables initially start at 0. Although the output of the formula merely has to be a real number, the variables are always integers. The formula is evaluated, and the output interpreted as follows:

• If the output is an integer + ½ exactly, a bit is read from input, and it is rounded up to the nearest integer if the bit is 1 or down to the nearest integer if the bit is 0; then one of the following actions is applied to the rounded result.
• If the output is 0 exactly, the program ends.
• If the output is in the range (-½,½), then a 0 bit is output (if the output was negative) or a 1 bit is output (if the output was positive), and the first variable name is decremented or incremented (according to the sign of the result).
• If none of the above apply, the output is rounded to the nearest integer; if the result is a positive integer n, the nth variable is incremented, and if it's a negative integer -n, the nth variable is decremented.
• It is an error if the result refers to a non-existent variable (otherwise, the program would simply go into a trivial infinite loop).

This evaluation and interpretation of the result is repeated until the program ends.

Interpretation of the language

There are two ways to interpret the language; either as a zero-dimensional language with the variables as data storage, or as a multidimensional language with each variable corresponding to a dimension. For instance, a two-variable program has no wire crossings in its state diagram, which is trivial to prove by plotting each possible state of the program at (x,y) for a program with variables x and y.

Computational class

With three variables Formula can reasonably simply simulate a Minsky machine, and so is Turing complete. The computational class with two variables is unknown. All one-variable programs cannot go into a non-infinite loop and so cannot even emulate a push-down automaton.