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:
- Sin, cos, tan (in radians) and their inverses
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.
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.