Smallfuck

Smallfuck is an esoteric programming language invented by Nikita Ayzikovsky around March 2002 for the purpose of compiling it to SMETANA. It is a sized-down version of Brainfuck that operates only on bits, has limited data storage, and does not define input or output.

Command set

The Smallfuck command set is that of Brainfuck with two alterations: . and , are omitted, and + and - are replaced by * (because, when applied to bits, + and - would do the same thing anyway.) The command set is summarized as follows:

> Move pointer right
< Move pointer left
* Flip current cell
[ Jump past matching ] if cell under pointer is 0
] Jump back to matching [

If a program attempts to move the memory pointer to the left of the first cell, or to the right of the (implementation-defined) last cell, it terminates normally.

Because input and output are not defined, it is generally assumed that input is encoded in the initial state of the data storage, and that output must be decoded from the final state of the data storage.

Computational class

If we were to grant Smallfuck an unbounded tape, we could show it to be Turing-complete by a trivial reduction from Boolfuck. All that is missing are I/O commands, which are not required for Turing-completeness.

However, while the number of bits in Smallfuck's data store capacity is completely left up to each implementation, the number is defined to be finite. Thus, Smallfuck is in the computational class of bounded-storage machines with bounded input.

See also

• Boolfuck is a similar language but is equipped with input and output.
• Nanofuck an invertible minimization of Boolfuck.
• BitChanger combines two more instructions.
• BF instruction minimalization chronicles one author's attempts at a smaller Brainfuck.
• Braktif is a formulation of Smallfuck as a cellular automaton.
• Fm languages; F2 can be seen as a Turing-complete extension of Smallfuck.
• SMETANA, to which Smallfuck can be compiled.
• RCEM, to which Smallfuck can be translated. RCEM is Turing-complete.
• Smallfuck/sf2wikitable
• Smallfuck/smf.rhk implements a memory-unbounded version of Smallfuck in Rhokell as a proof of its turing-completeness.

External resources

• sf2tab is a Smallfuck-to-lookup-table compiler.
• Possible Smallfuck interpreter
• sf2wikitable - smallfuck to wiki table compiler