Picofuck
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.
Contents
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)
- Prove or disprove the existence of PF languages.
- If PF languages are found to exist, discover an example.
- Determine the minimum length of a PF language and enumerate all PF languages of that length.
- Write an interpreter for a PF language.
- 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 a_{1}, a_{2}, ..., a_{n} and language B with commands b_{1}, b_{2}, ..., b_{m}. A translation table from language A to language B might look like
A | B equivalent |
---|---|
a_{1} | b_{1}b_{2} |
a_{2} | b_{2}b_{1} |
... | ... |
a_{n} | b_{m-1}b_{m} |
A translation table from language B to language A might look like
B | A equivalent |
---|---|
b_{1} | a_{1}a_{2} |
b_{2} | a_{2}a_{1} |
... | ... |
b_{m} | a_{n-1}a_{n} |
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.