# 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*n*th variable is incremented, and if it's a negative integer*-n*, the*n*th 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.