Fm

For each m >= 2, Fm is a computational model based on editing a finite unbounded string on an alphabet of m letters. It is derived from Brainfuck in the spirit of the Wang program formulation of Turing machines, by using only the five instructions '+' '<' '>' '[' ']' and by applying a cyclic ordering to the alphabet, with '+' changing a letter to the next letter in cyclic order.

Computational class

F2 has been proved Turing-complete without reference to the Turing completeness of other Brainfuck languages, by directly simulating a universal tag system in F2. All Fm languages are therefore Turing-complete, because they can easily simulate F2.

External resources

• Original pre-Geocities Fm page (from the Wayback Machine; retrieved on 28 January 2007) that is archived. The more frequently referenced Geocities page of r_e_s_01 appears lost.
• F resources (from the Wayback Machine; retrieved on 12 March 2006), with code and examples, including:
  • Interpreter in Python (from the Wayback Machine; retrieved on 17 May 2006)
  • F2 tag system TC proof (from the Wayback Machine; retrieved on 17 May 2006)

See also

• Smallfuck
• Wang program