Picofuck

From Esolang
Jump to: navigation, search

Picofuck (PF) is the set of 2 command, simple translations of Reversible Bitfuck (RBF). It is not currently known if any PF languages exist. However, it is known that 3 command, simple translations of RBF exist. See the talk page for current action.

Picofuck project

The Picofuck project is a community driven effort to discover or disprove the existence of PF languages. It was initiated by User:Orby in March of 2017. The main objectives of the project are (in order of priority)

  1. Prove or disprove the existence of PF languages.
  2. If PF languages are found to exist, discover an example.
  3. Determine the minimum length of a PF language and enumerate all PF languages of that length.
  4. Write an interpreter for a PF language.
  5. Write a program that will take a PF program and produce it's inverse.

PF languages

No PF languages have been discovered at this time. When they are discovered, or proven not to exist, constructive examples or proof of non-existence will be provided here. PF languages will be titled PF0, PF1, etc. in the order in which they are discovered. See the talk page for candidate languages.

Definitions

Reversible Bitfuck

For our purposes, RBF is defined on a tape machine with 1-bit cells. The tape machine is unbounded on the right. It uses 5 commands.

Command Description
* Toggle the current bit
> Shift the tape head right
< Shift the tape head left
( If the current bit is zero, jump past matching )
) If the current bit is zero, jump to just after matching (

RBF is Turing complete by reduction to 1-bit Reversible Brainfuck which is known to be Turing complete. Simple translations:

Reversible Bitfuck 1-bit Reversible Brainfuck
* + or -
< <
> >
( +[+
) +]+
*(* [
*)* ]

Simple translation

For our purposes, we define a simple translation between two languages as a set of translation tables between those languages. For each row, a translation table contains a single symbol from the source language in the left column and a finite sequence of symbols from the destination language in the right column. If the symbols are substituted as prescribed in the translation table and the resulting program halts, then the machine state of the destination language should be equivalent to the machine state of the source language up to isomorphism. The destination program should halt if and only if the source program halts. Input and output should match accordingly as well, if such commands exist in the languages.

Suppose we have language A with commands a1, a2, ..., an and language B with commands b1, b2, ..., bm. A translation table from language A to language B might look like

A B equivalent
a1 b1b2
a2 b2b1
... ...
an bm-1bm

A translation table from language B to language A might look like

B A equivalent
b1 a1a2
b2 a2a1
... ...
bm an-1an

Notice that both tables need to be provided in order to establish that A is a simple translation of B. Naturally, if A is a simple translation of B then B is also a simple translation of A. It is also clear that simple translations preserve Turing completeness.

Length of a PF language

The length of a PF language is defined as the sum of the number of commands in RBF to which each PF command translates. For example, if the PF command [ translates to the 3 RBF commands *(> and the PF command ] translates to the 4 RBF commands )*(>) then the length of the PF language is 3 + 4 = 7.

See also