Thanks for dropping by. Please keep general talk to the Chatter section.

Candidate languages

Languages that are candidates for PF will be provided here. They will be titled PFC0, PFC1, etc. in the order in which they are discovered. For clarity and consistency, please use the characters [ and ] to represent PFC commands (see Property II for an explanation).

PFC0

PFC0 is not PF. See talk below for the proof.

PFC0	RBF
[	(>
]	)*(<)

This one cannot work. There is no way to translate an RBF * which starts at the rightmost 1 on the tape into something that halts. --Ørjan (talk) 23:42, 28 March 2017 (UTC)

Too bad :( Do you have an easy way to see that? It's not immediately clear to me. Orby (talk) 23:50, 28 March 2017 (UTC)

Oops, scratch that, I somehow assumed the initial (> had to be followed by a )*(<). I now see that (>(>)*(<))*(<) halts just fine (unless I messed that up). Reversible languages are confusing... --Ørjan (talk) 23:59, 28 March 2017 (UTC)

I find myself in a perpetual state of confusion and awe. Orby (talk) 00:10, 29 March 2017 (UTC)

Hm, or wait. If a program starts with n copies of (> before the first )*(<), then it will not halt if it's on the first of n 1s, when those are at the end of the tape. So for every nontrivial PFC0 program, there is some initial tape it doesn't halt on. --Ørjan (talk) 00:15, 29 March 2017 (UTC)

Ah, yes I follow your argument. Therefore it is not possible to translate * because * halts on all initial tapes. Thus PFC0 cannot be PF. Orby (talk) 01:15, 29 March 2017 (UTC)

I've summarized this argument as Picofuck#Property I for future reference Orby (talk) 01:57, 29 March 2017 (UTC)

PFC1

PFC1 is not PF.

PFC1	RBF
[	*(
]	(>))<

The program [] = *(*(>)*)< = *< halts for all inputs and always modifies the tape, satisfying properties I and III. The program [[]] = *(*(*(>)*)<*(>)*)< does not halt on the empty tape, satisfying property IV. Property II is also satisfied. Orby (talk) 15:21, 29 March 2017 (UTC)

I think I was a little hasty in posting this. Any number of nested []'s will never halt for a zeroed tape and any number of sequential []'s will amount to *<*<...*<, so it's impossible to shift right on an empty tape in PFC1. Don't think this can be PF. Thoughts? Orby (talk) 15:27, 29 March 2017 (UTC)

No, this is wrong. A program just can't start with a nested loop without entering an infinite loop on a zeroed tape. We can certainly have things like

[][[]]

which results in <<*>> I think. Though I'm still not convinced that it's possible to shift right past the initial tape head position... Orby (talk) 15:31, 29 March 2017 (UTC)

Yeah the first time a program shifts right on an initially zeroed tape, it shifts into a zero and cannot possibly get out of the (>) loop. --Ørjan (talk) 16:39, 29 March 2017 (UTC)

OK, I see the problem clearly now. It's impossible to shift right on the right-most 1 without entering an infinite loop, which means it's impossible to translate >. Not PF :( Orby (talk) 16:45, 29 March 2017 (UTC)

PFC2

PFC2	RBF
[	*(>
]	(<))(<(>))

The thinking behind PFC2 is that the translation of [] to RBC results in a program that ~~always halts (thus it satisfies property I)~~ Edit: This is incorrect, see below. It satisfies property II clearly. Between [] and [][], there exists a program which modifies the tape for any initial machine state, so it satisfies property III. Moreover, [] may result in either left or right shifts depending on the state (it avoids pitfalls explored in non-existence proof #2). I think we're making slow but steady progress. The primary open question concerning PFC2 is satisfies property IV. Orby (talk) 20:27, 29 March 2017 (UTC)

Um, I get that [] doesn't halt if it starts on a 0 before a 1 with the rest of the tape to the left zero. --Ørjan (talk) 23:30, 29 March 2017 (UTC)

You're right. I really need to write an RBF interpreter and stop doing these things by hand... Orby (talk) 23:48, 29 March 2017 (UTC)

Even more seriously, the reverse of (<(>)*)* doesn't seem to halt on a zero tape, which means no PFC2 program halts in reverse on a zero tape. I think possibly a RBF program cannot halt on all tapes unless its reverse does the same, although I don't quite have a proof yet. --Ørjan (talk) 23:52, 29 March 2017 (UTC)

Do you have a counter example for conjecture 2.1? Orby (talk) 23:55, 29 March 2017 (UTC)

PFC3

PFC3	RBF
[	(>(<))*(<(>
]	)*

The first PFC with unbalanced parenthesis. An improvement over PFC2. The PFC3 program []] translates to the PFC2 program [], and as a result properties I, II, and III hold for PFC3 (Edit: property I has not been shown to hold, as it turns out that it doesn't necessarily hold for PFC2). Additionally, property IV can be seen to hold for PFC3 by examining the program [][]]] which is equivalent to the RBF code

*(>(<)*)*(<(>)**(>(<)*)*(<(>)*)*)*

which runs indefinitely if started on the left-most 1. Orby (talk) 23:24, 29 March 2017 (UTC)

Property I cannot hold, as the infinite loop on 0 before 1 for PFC2's [] requires only the *(>(<)*) part which is entirely within PFC3's [. --Ørjan (talk) 00:12, 30 March 2017 (UTC)

Properties of PF languages

There are many properties a PF language must have. Demonstrating that a candidate language violates one of these properties is the easiest way to prove it is not PF.

Property I

There exists a program such that for all machine states that program halts.

There are 3 commands in RBF that halt for all possible states: *, >, and <. Therefore, a language cannot be PF if for all programs there exists a state for which that program will not halt. See the proof that PFC0 is not PF for an example. Credited to Ørjan.

Property II

The first PF command must translate to more ('s than )'s and the second PF command must translate to more )'s than ('s.

The first PF command, which we'll call [, must be translated into more ('s than )'s otherwise we cannot produce the RBF command (. Conversely, the other PF command, which we'll call ], must be translated into more )'s than ('s otherwise we cannot produce the RBF command ). Because an RBF program may start with *, >, <, or (, the translation of each of these commands must start with [ in PF otherwise ] would translate into a ) with no match. Credited to Ørjan.

Property III

There is no machine state for which all programs do not alter the tape.

The RBF command * will alter the tape regardless of the machine state. If there exists a machine state for which all programs in a language do not alter the tape, then that language cannot be PF. This implies that [] must translate to an expression which contains a * outside of a loop (otherwise having an initial tape set to all zeros will never be modified).

Property IV

There exists a program which does not halt for some machine state.

The RBF program *(>) doesn't halt on a zeroed tape. Thus, there must be a PF program which essentially does the same.

Chatter

Hello! Orby (talk) 22:38, 28 March 2017 (UTC)

Your name "Reversible Boolfuck" is confusing since I had already used that name in the article on Reversible Brainfuck, for the 1-bit version. :( --Ørjan (talk) 23:28, 28 March 2017 (UTC)

Oops, sorry about that. I'll change it to Reversible Bitfuck. I don't see that in use anywhere on the Wiki :) Orby (talk) 23:40, 28 March 2017 (UTC)

I'm considering trying to brute-force the search computationally. Should be pretty easy to search for 2 command languages that are simple translations of Nanofuck, aside from the issue of the halting problem. --(this comment by Orby at 23:53, 28 March 2017‎ UTC; please sign your comments with ~~~~)

Observation: In order to be able to translate (, one of the two Picofuck commands (call it A) must be translated into more ('s than )'s, and vice versa for ) (call the other command B). A then has to start the program, and you need to avoid something like my n 1's argument from working for whichever commands you choose. In other words, there must be some n such that you cannot set up an initial tape that forces every program starting with AAA...AAAB (n A's) not to halt. --Ørjan (talk) 00:30, 29 March 2017 (UTC)

And because an RBF program can start with *, <, >, or (, the translation of each of these commands must start with A otherwise we get an unmatched ) (summarized as Picofuck#Property II Orby (talk) 01:59, 29 March 2017 (UTC)

More observations:

We haven't actually proved yet that the number of surplus ('s in [ must be the same as the number of surplus )'s in ]. Maybe a properly matched program is [[]]] or the like.
All RBF programs that don't contain < or > are equivalent to either a NOP or to *. Proof: (), (*) and ** are NOPs, and any other such program must contain one of them, which can be removed.

--Ørjan (talk) 03:31, 29 March 2017 (UTC)

another thing i found was: say the first command, [, opens X loops total, and the second command, ], closes Y loops total. the commands in PF that translate to RBF's *, <, and > must use [ c*LCM(X, Y)/X times, and use ] c*LCM(X,Y)/Y times (where c is a constant). not sure if this helps a lot though Otesunki (talk) 09:26, 10 January 2022 (UTC)

Non-existence proof?

Working on a non-existence proof with the hopes of either completing it or finding PF0 in the gaps. Here's what I've got so far:

Every program must contain a loop by property II. Thus, without loss of generalization, we can translate every PF program to an RBF program of the form a₀(a₁(...a_n(b)c where a₀, a₁, ..., a_n only contain the RBF commands *, >, < and b and c contain *, >, <, (, or ).

Let T denote the set of all machine states where the tape head is pointing at a 1 bit. There exists a set of initial machine states X such that for all x in X, a₀(x) is in T. That is, if the machine starts in any state in X, a₁ is guaranteed to run. (Note: I'm assuming X can never be empty...).

Now, either there exists x in X such that a₁(a₀(x)) is in T or not. If not, then the loop containing a₂ can never execute and we can assume n = 1 without loss of generality. Apply this process inductively to arrive at the execution of b.

Now, I'd like to be able to say that there is some state x in X such that a₀(a₁(...a_n(x)) will put b in an infinite loop. That would imply that for every program, there is an initial state which puts the program in an infinite loop which means we can't express *, >, or < in PF, but that means

b must result in net head movement
The execution of a₀, ..., a_n must not "filter" the bad states out which would cause b to enter an infinite loop.

Alternately, if the execution of a₀, ..., a_n always filters those bad states out, then b can never enter an infinite loop which might be a way to prove that no program in the language can halt, which also means its not PF. Hmmmm...

Orby (talk) 05:16, 29 March 2017 (UTC)

Alas, that's too simple. E.g. if a₁ is *, then a₂ is filtered out - but only on the first iteration through the a₁ loop, on any others it is run. E.g. these programs are the same up to the start of c, but the first one always halts, and the second one runs indefinitely on a zeroed tape:

*(*(>)*)
*(*(>))

Things should get even more complicated if > or < is involved in the a_is.

--Ørjan (talk) 13:41, 29 March 2017 (UTC)

Ah yes, you are right. Thanks for pointing that out. It looks like the first program will always halt. Now the question is, is it possible to divide the first program into two PF commands in such a way that it is possible to create a program that doesn't halt? Say [ = *( and ] = *(>)*) then [[]] = *(*(*(>)*)*(>)*) which is an infinite loop on a zeroed tape I think. Thus my approach for the non-existence proof is no good. But this is progress; with some modification [=*(, ]=*(>)*) might lead to PFC1. Orby (talk) 14:48, 29 March 2017 (UTC)

Thoughts: A possible method for generating a PF candidate is to construct an RBF program that halts on all inputs, then split the program into two substrings, one which we'll call [ and one which we'll call ] and find a way to construct a program out of [ and ] that runs infinitely for some initial state. That will guarantee that the PFC satisfies properties I and IV. Property II is trivial to satisfy and property III can be satisfied by making sure there is a * before the first ( in [ or after the last ) in ]. Orby (talk) 16:51, 29 March 2017 (UTC)

I'm playing with this technique to split *(*(>)*)*(*(<)*)* Clearly it needs to be split next to < or > in order to avoid the problem with PFC1. Orby (talk) 18:01, 29 March 2017 (UTC)

Hmm, that won't work because we'd need to split next to both > and <. Orby (talk) 18:13, 29 March 2017 (UTC)

Non-existence proof #2

This one is pretty simple but hinges on a conjecture I haven't proved yet.

Conjecture 2.1

Any loop that results in net tape head movement for some initial state, also runs indefinitely for some initial state.

Examples:

*(>*(<))

Runs indefinitely on

01111111...
^

Lemma 2.2

For any PF language, all programs can be translated to RBF in the form a(b)c where the and a and c consist of the RBF commands *, >, < and b is some RBF program. Notice that a and c are fixed for all programs generated by the language because [ must start with a and ] must end with c and each PF program must begin with [ and end with ].

I don't see this lemma, what about programs with more than one toplevel loop, like a(b)c(d)e ? --Ørjan (talk) 00:38, 30 March 2017 (UTC)

Proof

Let a(b₁)c denote the PF program which translates to the RBF program >. By (2.1), (b₁) must never result in net head movement, because > never runs indefinitely. Thus, the net head movement of ac must be >. Let a(b₂)c denote the PF program which translates to the RBF program <. By (2.1), (b₂) must never result in net head movement, because < never runs indefinitely. Thus the net head movement of ac must be <. The net head movement of ac cannot be both > and <, therefore no PF languages exist.

QED

Counter example for 2.1

I thought this was a counter example, but there's a mistake in it Orby (talk) 23:54, 29 March 2017 (UTC)

The RBF program

*(>(<)*)

results in net head movement if run on a zeroed tape but never enters an infinite loop as it only touches the first two cells (we'll call them cells a and b) and results in the following operations depending on the content of the cells

ab
-----------
00      *>*
01      * This is wrong. If we start one cell left of the left-most 1, we enter an infinite loop.
10      NOP
11      NOP

Verify? Edit: Wrong.

This counter-example has brought me to the interesting RBF program

*(>(<)*)*(<(>)*)*

If the tape head starts on b, the following states result in the following results

abc
------------
x00      *>*
x01      *
01x      <
11x      *

where x indicates that the result is the same for both 0 and 1. Orby (talk) 19:50, 29 March 2017 (UTC)

I've used this program to define PFC2. Looks interesting, but might not be able to produce infinite loops. Orby (talk) 20:30, 29 March 2017 (UTC)

Non-existence Proof 3

Thanks for bearing with me through my half baked proofs and cascades of edits. Here is what I was trying to say in non-existence proof #2 but failed to express clearly. Hopefully this makes a little more sense.

Let PFi be some PF language with commands [ and ].

Lemma 3.1

The command [ must translate to at least one unmatched ( and the command ] must translate to at least one unmatched ) in order to translate the RBF commands ( and ). Moreover, [ cannot contain any umatched ) otherwise we cannot start or end a program with [. Similarly, ] cannot contain any unmatched ( otherwise we can't end a program with ]. Notice this implies that every PFi program must start with [ and end with ].

Lemma 3.2

The translation of [ to RBF is of the form

A(B₁)C₁...(B_n)C_n(D

where

A and C_i consist of the commands *, >, and <
B_i are RBF programs
D consists of the commands *, >, <, (, and ) with no ) matching the open (

Similarly, the translation of [ to RBF is of the form

Z)Y₁(X₁)...Y_m(X_m)W

where

W and Y_i consist of the commands *, >, and <
X_i are RBF programs
Z consists of the commands *, >, <, (, and ) with no ( matching the open )

This follows from 3.1.

Conjecture 3.3

We define a shift loop as an RBF loop that results in net tape head movement for some initial state. Examples of shift loops include

(>)
(>(<))

etc. Conjecture: Every shift loop executes indefinitely for some initial state.

Theorem 3.4

Because any PFi program must start with [ and end with ] by 3.1 and the form provided to us by 3.2, we have that every PFi program must translate to an RBF program that looks like concatenations of units of the form

A(B₁)C₁...(B_n)C_n(U_i)Y₁(X₁)...Y_m(X_m)W

where U_i are RBF programs which we will call kernels. Let U_i denote the kernels of the PFi program which translates to > and let V_i denote the kernels of the PFi program which translates to <. Since neither > nor < execute indefinitely for any initial state, it must be true that (B_i), (X_i), (U_i), and (V_i) are not shift loops by 3.3. That means that the net tape head movement must be a result of the execution of top-level (i.e. not inside of loops)

T = AC₁...C_nY₁...Y_mW

The net tape head movement resulting from the execution of T is either always to the right or always to the left. A PFi program can execute T multiple times, but cannot change the direction of the tape head movement. We know T must result in right net tape head movement because we can express >. But it also must be true that T results in left net tape head movement because we can express <. Clearly, T cannot do both. Therefore PFi cannot exist.

Conclusions

Excluding errors in our reasoning, the only hope for constructing a PF language is finding a counter-example to 3.3 and using that to make arbitrary shifting possible.

-- Orby (talk) 03:17, 30 March 2017 (UTC)

Non-existence Proof 4

Consider instruction for `>` expanded. most inner loop can't have unbalance tape-head moving(otherwise it's a potential infinite loop) all loops can't so `>` can only appear outside

Same do `<`

But `[` and `]` have fixed ratio and all moves are unconditional so it can't do both `<` and `>`

Conjecture counterexample

Apparently it was a matter of finding the right building blocks. Here is a xor:

(>*<)

From that, we can get a swap:

(>*<)>(<*>)<(>*<)

And then we get the first counterexample to the conjecture:

((>*<)>(<*>)<(>*<)>)

This swaps the current cell with the cell to the right only if the current cell is 1. Thus the loop can run at most once, but may shift position.

We can also swap unconditionally and move right:

 ((>*<)>(<*>)<(>*<)>)*((>*<)>(<*>)<(>*<)>)*

Combining this, we get an unconditional move right where the movements outside the loops are balanced:

(>*<)>(<*>)<(>*<)((>*<)>(<*>)<(>*<)>)*((>*<)>(<*>)<(>*<)>)*

There has to be some movement outside the loops to implement a >, because skipping or passing through a loop always ends at a cell with the same value as the original value of the cell it started at - which means that if there are no movements outside loops, then the change in "value of current cell" from beginning to end is statically known.

--Ørjan (talk) 05:10, 8 April 2017 (UTC)

Brilliant! I'll be digging into using this to conjure up a new candidate. B) Orby (talk) 19:34, 12 April 2017 (UTC)

I'm not convinced that

(>*<)>(<*>)<(>*<)((>*<)>(<*>)<(>*<)>)*((>*<)>(<*>)<(>*<)>)*

results in a single unconditional move right (if I'm understanding you correctly). I get what you're going for with the A*A* pattern, which works if the loops don't shift, but in this case I think it does not. Consider

100
^

We know (>*<)>(<*>)<(>*<) transforms it to

010
^

Then ((>*<)>(<*>)<(>*<)>)* swaps it back, shifts right, and toggles the bit resulting in

110
 ^

Applying ((>*<)>(<*>)<(>*<)>)* again, swaps to the right of that, shifts, and toggles

100
  ^

Shifting right twice! I'm going to write an RBF interpreter on Friday to facilitate this stuff Orby (talk) 00:33, 13 April 2017 (UTC)

No, ((>*<)>(<*>)<(>*<)>)* doesn't swap it back. It only runs when the current cell is 1. It works because the second outer loop runs if and only if the first doesn't. --Ørjan (talk) 00:46, 13 April 2017 (UTC)

Right, right. I get it now and agree. --Orby (talk) 19:16, 13 April 2017 (UTC)

Observation

I think this is correct, let me know if you see any problems with my thinking. Consider the case where [] is a well formed program (balanced parenthesis).

[   A(A'
]   B')B

Then the translation of ( must end with [, which implies that A(A' can only contain a single open paren (i.e. A and A' must be well formed programs with no open parens). Similarly, the translation of ) must begin with ], which implies that B')B can only contain a single open paren (i.e. B' and B must be well formed programs with no open parens).

If the translation of ( ends with [, then A' must be a nop, otherwise we cannot translate (. If the translation of ) begins with ], then B' must be a nop, otherwise we cannot translate ). So we really must have the form

[ A(
] )B

where A and B are well formed RBF programs with no open parens.

Notice that the translation of ( must end with [ and it must be preceded by a well formed program. Thus the translation of ( into PF must translate back into RBF as CA( where C is some RBF program which is the inverse of A. Thus there exists a PF program which translates to the inverse of A in RBF. --(this comment by Orby at 19:17, 13 April 2017‎ UTC; please sign your comments with ~~~~)

I see two problems. First, it's not clear that the translation of ( must end with [, secondly, it is not clear that the translation of [ can only contain one (. To see that, consider the following two simple translations from RBF to itself:

(  (()
)  ())
other commands to themselves

This works because () is a NOP.

(  ((
)  ))
other commands to themselves

This works because if one of the command copies is entered or exited, then the other must be as well. --Ørjan (talk) 00:14, 14 April 2017 (UTC)

A different way of thinking about the problem

Let's think about this from a different angle:

Consider the RBF tape finite. What is right shift? The permutation (1 2 ... n). What is left shift? The permutation (n n-1 ... 1). The symmetric group Sn is generated by T = {(1 2), (2 3), (3 4), ..., (n-1 n), (n 1)}, that is, the set of all transpositions that swap right. Therefore right shift and left shift can be expressed in terms of swaps on a finite tape. Swapping the current cell with the cell to the right is simple in RBF, as we know:

   (>*<)>(<*>)<(>*<)

If the tape is infinite, then the set of all permutations that only rearrange a finite number of elements is clearly also generated by T (though clearly not the set of all permutations on the tape, which is not even computable). Is this in addition to a universal logic gate sufficient for Turing completeness? Not quite, as if 'only' adjacent swaps and some universal logic gate are possible, then every program halts, which we know does not suffice. But maybe it's close?

Let's assume it is and continue down this path. Then it might be useful to focus on constructing two commands that, in conjunction, can produce a swap of two adjacent elements and can compute a reversible universal logic gate (Fredkin or Toffoli). It won't necessarily satisfy our goal of producing a simple translation of RBF in 2 commands, but it may deepen our understanding.

Example that can produce a Toffoli gate, but I don't see an obvious way to do swaps:

[   >*(
]   )<

Initial state (all programs return the data pointer to a):

abcd
^

A few simple programs:

[] = >*()< = >*<                                             b = ~b
[[]] = >*(>*()<)< = >*(>*<)<                                 b = ~b, c = ~b ^ c
[[[]]] = >*(>*(>*()<)<)<) = >*(>*(>*<)<)<                    b = ~b, c = c ^ ~b,
                                                             d = d ^ ((c ^ ~b) & ~b)
                                                               = d ^ (~b & ~c)

Slightly more complex:

[][[]] = >*()<>*(>*()<)< = >*<>*(>*<)< = >(>*<)<             c = b ^ c
[[][[]]] = >*(>(>*<)<)<                                      b = ~b, d = d ^ (~b & c)

Toffoli gate:

[][[][[]]] = >*()<>*(>(>*<)< = >*<>*(>(>*<)<)< = >(>(>*<)<)< d = d ^ (b & c)

This seems like a possible way to gain some traction. -- Orby (talk) 17:20, 14 April 2017 (UTC)

This example has the property that

[A1][A2]...[Ai]

is equivalent to

If the cell to the right is 0
 then >A1A3...A(if i is odd then i else i-1)<
 else >A2A4...A(if i is odd then i-1 else i)<
If i is odd then >*<

In particular, you can change a cell based on any condition of cells to the left of it (except the first, which is sort of lost), but not based on any condition involving the cells to its right. So a swap is impossible. --Ørjan (talk) 01:12, 15 April 2017 (UTC)

Another example

It is also trivial to express swapping arbitrary adjacent cells. Consider the translation

[   (>*<)>(<*>)<(>*<)>
]   <

If the tape state is

abcde
^

Then the first few transpositions are

{ab} := []
{bc} := [][[]]
{cd} := [][[][[]]]

Which we can define recursively as

{0 1} := []
{i i+1} := [][{i-1 i}]

Is this just as good as > and < in terms of Turing completeness?

Certainly not, with those a program can only reach finitely many cells. --Ørjan (talk) 01:17, 15 April 2017 (UTC)

Never mind, since [ and ] don't have to match you have < and > themselves easily. --Ørjan (talk) 01:32, 15 April 2017 (UTC)

Yet another example

Say we have the translation

[ >>*(<(<*>)<(>*<)>(<*>)>)<
] <

The commands [ and ] can be summarized as (let TH denote tapehead)

[   Toggle TH+2. If TH+2, swap TH+0 and TH+1. Shift right.
]   Shift left.

If we say [] maps (a, b, c) to (a', b', c'), then we have that c' = ~c and if b = 0 then b' = a & ~c (i.e. (a -/-> c)). This means that [] is functionally complete since ~ and -\-> in combination can express any logical connective.

Furthermore,

[][]                    {ab}
[][][][                 >
]                       <

So,

[][][][[][]]            {bc}
[][][][[][][][[][]]]    {cd}

etc. So we can express any permutation that rearranges a finite number of elements on the tape with [] as well. The only thing that is missing is looping. I think a loop around the program would be sufficient for Turing completeness. It's not a simple translation of RBF, but it is interesting.

The set of PF languages is empty

Suppose a PF language exists.

One PF command must translate into no unmatched ) otherwise we have no command with which we can start the program.
One PF command must translate into no unmatched ( otherwise we have no command with which we can end the program.
One PF command must translate into at least one unmatched ( otherwise we cannot represent ( in RBF.
One PF command must translate into at least one unmatched ) otherwise we cannot represent ) in RBF.
(1) and (3) imply that there exists a PF command [ which looks like a₁a₂...a_n ( a_n+1a_n+2...a_m in RBF. The explicit ( represents the left-most unmatched parenthesis.
(2) and (4) imply that there exists a PF command ] which looks like b₁b₂...b_x ) b_x+1b_x+2...b_y in RBF. The explicit ) represents the right-most unmatched parenthesis.
Notice every PF program must start with [ and end with ].
The RBF program < must have a representation in PF which must look like a₁a₂...a_n ( ... ) b_x+1b_x+2...b_y where the explicit parentheses match.
The RBF program > must have a representation in PF which must also look like a₁a₂...a_n ( ... ) b_x+1b_x+2...b_y where the explicit parentheses match.
Conjecture: there exists a tape for which the explicit loop in both of these cases never executes.
On that tape < == a₁a₂...a_nb_x+1b_x+2...b_y == >.
But > == < is a contradiction. Therefore a PF language does not exist.

Edit: 8 & 9 are not true. This approach doesn't' work.

Notes on conjecture

Define

*' = *
>' = <
<' = >
(' = )
)' = (

Notice that the inverse of an RBF program r₁r₂...r_k is equal to r_k'...r₂'r₁'. To calculate the tape on which the explicit loop never executes, first run a_n'...a₂'a₁' on a tape initialized to all 1's. If the program halts, then we have the tape on which the explicit loop never executes (with the tape head potentially shifted some number of times left or right). If the program doesn't halt, then there must be some tape for which a₁a₂...a_n never halts?

Discussion

I don't immediately see why 8 and 9 are false (although I may be missing something). However, I believe that the proof breaks down because 10 is false. I think it's clear that the PF tape and RBF tape won't be identical to each other (there'll be a mapping between them but it won't be the identity function; this seems to be allowed by the definition of a simple translation). It's entirely possible that "between commands", the mapping between PF and RBF tapes will be such that the tape always in a state in which the unmatched loop will run (whereas tape states in which the unmatched loop wouldn't run can exist "mid-command"). --ais523 03:07, 1 May 2020 (U T C)

I'm exploring the differences between requiring equivalence of machine states in a Simple translation and requiring isomorphism. If we require isomorphism, then we need a way to map RBF to PF and back. I think this gets tricky when mapping back, because the context that needs to be stored in the PF program must go somewhere. Orby (talk) 19:22, 5 May 2020 (UTC)

PF attempt, using a hypothetical RBF self-interpreter

Hi Orby, your recent edits got me thinking on this problem, and this alternate approach occurred to me. I think a PF language has to be theoretically possible, but not quite in the direct way you are trying for.

pf language simple translation:

* : 10
> : 110
< : 1110
( : 11110
) : 111110

Edit: The zero delimiter should be at the end to allow the last command to be acted upon, I don't think it changes the concept much. Originally I thought 0 could perform any initial memory space set up required, but that could just be moved into 1 if it is needed.

which trivially solves the encoding part of the problem. The exact assignment of these codes is not important, the important part is that each unary run representing a command is delimited by one symbol.

in reverse:

0 : effectively an RBF self-interpreter which keeps track of program state and current position within any loops using some convention to manage tape storage of program and data space
1 : sets the data for self-interpreter of 0 to operate on (using a memory management convention expected by 0)

I'm struggling to think of how to reliably store arbitrary sized program pointers for managing the data and program space which need to occupy the same 1 bit unbounded-in-one-direction tape, but on further reflection it should be possible since RBF is Turing complete and a RBF self-interpreter must be possible.

The 0 self-interpreter is run anew every time a 0 is encountered, and takes the tape as its full input state. Based on the tape state it may or may not perform some number (0 to infinite) modifications to the program state, before ending and passing control to the next data command, or potentially looping forever (if a loop is encoded in the tape, and data causes it to not terminate).

A more direct command translation approach probably isn't possible since the two symbols of pf have to be balanced to properly encode valid ( and ) combinations, but unbalanced to encode one of the < / > pair. Formally coming up with a proof to show that this encoding problem meant a pf language couldn't exist was difficult, which is because such an encoding constraint isn't actually binding. The important part is the functionality of the language, which gives a whole lot of wriggle room for coming up with novel encoding solutions. Hence this "one command is a self-interpreter" idea.

I believe this still conforms to the definition of Reversible_Bitfuck#Simple_translation with the two-way translations, although I feel like I'm stretching the intended spirit quite a bit. I have an unpublished esolang idea that makes use of encoding translations like this where each instruction is encoded as a relatively large stand-alone 'program' that takes the entire program state and performs the expected modification of that one instruction, before passing the state on to the next program. This seemed like a problem that could be solved by the same approach. Salpynx (talk) 02:25, 1 May 2020 (UTC)

Details of how the `0` command / program must function

0 is an interpreter written in RBF that expects a pre-existing state containing: [data-space, data-pointer, program-space, program-execute-pointer/program-write-pointer, next-input-command, execution-state] (the blank initial state is valid). Depending on execution-state, the program will perform some combination of store / ignore / execute on next-input-command and perform some number of modifications of data-space / data-pointer based on the combination of execution-state + next-input-command + program-space. It will cease making modifications when the program-execution-pointer catches up to the program-write-pointer and it needs to read a new command to proceed. It will then set the state to one that will accept 1-5 applications of 1 to give the next next-input-command and pass control to the next command. 0 always begins and terminates with program-execute-pointer == program-write-pointer. Salpynx (talk) 04:17, 1 May 2020 (UTC)

More ideas in the Salpynx vein

Take arbitrary machine state t₀. If we take an RBF program which begins with t₀ and leaves the machine in state t₁ (assuming it halts), then the simple translation into PF of said RBF program must also leave the machine in state t₁. Since the 0 instruction needs the tape to be specifically formatted in order to keep track of the state of the self-interpreter, I think this is a problem. If we prefixed the PF program with some code that converted the tape state into an appropriate state for the self-interpreter, and suffixed the PF program with some code to convert the tape state back into it's original format, then I think this could work. (This was based on the simple translation requiring equivalence of machine states, not isomorphism. Disregard.) We could format the tape like

a₀b₀c₀d₀a₁b₁c₁d₁a₂b₂c₂d₂...

The a bits could be the "instruction counter" (next instruction to be executed), the b bits could be the data pointer, the c bits could be the nesting depth of (, ), and the d bits could be the RBF tape. 1 would increment a, and 0 would execute it. But, again, we need some way to convert t₀ to the abcd format and back. Orby (talk) 19:08, 5 May 2020 (UTC)

Thinking more about this. The original definition of Simple translation only required an isomorphism between machine states, not equivalence. I recently changed it to require equivalence. If they only need to be isomorphic, how does that change things? Orby (talk) 19:18, 5 May 2020 (UTC)

I probably need to digest your thoughts further, but I think you are on the right track with the simple translation definition. I'm pleased the definition reverted, and I'm finding the clarity of some of your formal statements help focus my thinking. I'm still getting to grips with my own ideas around encodings and equivalence. I just made an start on a picofuck simple-translator / interpreter using a one way translation from RBF to PF using the encoding I suggested above, but then a simple translation from PF to Python (because it is a high level language I can reason about faster!), once we get a functioning algorithm for that in a high level language, it should be easier to convert a working example into a lower level language like RBF. Salpynx (talk) 13:11, 7 May 2020 (UTC)

I've changed the definition of Simple translation back to the original (only requiring isomorphism, not equivalence). Let's focus on that approach. Assuming a Salpynx style PF, what would the isomorphism look like between the machine states? How would you map the interpreter state in PF back to RBF without it getting potentially overwritten by the running program? Orby (talk) 19:28, 5 May 2020 (UTC)

More thoughts on isomorphism

This much is clear: it is trivial to map the state of an RBF machine to a finite number of unbounded counters and back using the striping approach described above. The naive approach would be to use one of those unbounded counters to represent the RBF tape and use the others to represent interpreter state. But the problem is, where does the interpreter state get mapped in RBF space s.t. it doesn't get disrupted? I don't have a clear idea of how this would work yet. Orby (talk) 19:41, 5 May 2020 (UTC)

Defining machine state of RBF machine

Head position (1 unbounded non-negative register)
Tape (1 unbounded non-negative register, or right unbounded binary tape)
Instruction pointer (1 unbounded non-negative register)
Program (finite string of { (, ), *, >, < })

Am I missing anything? Each unbounded register can simulate any finite number of unbounded registers. An isomorphism to PF could map part of the tape to and from the data pointer, or to and from the instruction pointer. Simple translation only defines a restriction on how the program segments of the state map to one another.

An isomorphism?

These are brain droppings

PF machine

Head position (n)
Interpreter head position (p)
Tape (t_i)
Miscellaneous interpreter state (a)

RBF machine

Head position (m)
Tape (u_i)

The following isomorphism could be used to map between PF and RBF (LHS is RBF, RHS is PF)

m <-> p
u₁ u₂ ... <-> t₀ t₁ ... t_p n₀ a₀ t_p+1 n₁ a₁ t_p+2 n₂ a₂ ...

Where n_i is the binary encoding of n and a_i is the binary encoding of a. Each time the interpreter executes >, it would shift n_i and a_i right. Each time the interpreter executes <, it would shift n_i and a_i left. The RBF tape head would always point at t_p, which would always be one cell behind the PF state. Thus the PF interpreter state would never get overwritten. The PF command 0 would increment the instruction counter somewhere in a. The PF command 1 would execute the instruction referenced by the instruction counter and update t_i accordingly.

This prevents the PF interpreter data from being overwritten at run-time, but still doesn't appropriately map the initial state of the RBF machine to the PF machine (it only works for an RBF machine initialized to zero--- what if, say, the RBF tape is initialized to all ones?!)

Salpynx Picofuck attempt 'self-interpreter' in Python

It's been a while, but I made this experiment ages ago to explore the ideas in this discussion section, and seemingly forgot to link it from anywhere: User:Salpynx/Pico ; a 2 symbol simple-translation of a number of bf-like languages. It's in my user-space because I'm not convinced it's a 'real' picofuck, and not sure whether it qualifies as a new language, or merely a simple translation encoding experiment. Linking from here so anyone interested can play with the code or idea further. Salpynx (talk) 07:22, 4 February 2021 (UTC)

Fighting with defiition of simple translation

I've made numerous changes to the definition of simple translation recently. Please see that page for the most recent formulation.

Group formulation

I think the PF problem can be reduced to the following proposition: rank(<a,b,c|a²>) = 2 => PF is non-empty (see [1] and [2]).

It appears that rank(<a,b,c|a²>) = 3. See [3].

PF attempt using a command counter

The command counter is a cell outside the tape holding a value of 0 (for an odd-numbered command) or 1 (for an even-numbered command) to convert base 2 commands to base 4 commands.

PFC	Effect
.	If counter is 0, toggle the current bit and move the tape head one cell to the right. Then toggle the command counter.
/	If counter is 0 and the current bit is not set, jump instructions forward to the command immediately after the matching even-numbered /. If counter is 1, move the tape head one cell left, toggle it, move the tape head another cell to the left, then if the current bit is not set, jump instructions backwards to the command immediately after the matching odd-numbered /. Total jump distance is always an even number. If no jump was performed, toggle the command counter.

Translation to and from Nanofuck, which is known to be a simple translation of Reversible Bitfuck:

PFC	Nanofuck	Explanation	Reversible Bitfuck
..	.	The second . command toggles the command counter, but does not alter the tape.	+>
./	{	The . command is undone by the '/' command, which is also the loop entrance.	<(
/.	}	The '/' command is the loop exit. The . command toggles the command counter, but does not alter the tape.	)
//		Does nothing, since the first '/' command tells the computer to jump after the second '/' command

Since Nanofuck is a simple translation of this solution (and this solution is a translation of Nanofuck, albeit not a simple translation), this solution inherits Properties I (some programs will halt), III (there are no readonly tapes) and IV (some program-tape combinations will not halt). In this solution, the same PF command opens and closes loops, which violates Property II (that one command opens loops and one closes them). However, I can also prove that Property II cannot hold simultaneously with Properties I, III and IV.

Reversible Bitfuck is a language with 3 dimensions: cell value, tape head position and command position. By the law of geometry, a combination of vectors must include at least 3 unique vectors to be able to reach any point of a 3D space. Therefore, picofuck must allow a permutation of commands that change only cell value OR tape head position OR command position. Property II implies that both commands must affect command position, which forbids permutation that change only cell value OR tape head position. The three permutations that need to be supported require at least 3 unique commands unless intermediate operations are performed. My solution allows all 3 permutations to be expressed by 2 unique commands by computing a 1-bit hidden variable to perform the intermediate operations. Nanofuck does not need these intermediate operations because it already has 3 commands. The Reversible Bitfuck "length" of my solution is 5, the same as Nanofuck.

Alternatively, since any program is a large number expressed in binary, any program could be decompiled to binary commands (0s and 1s) or even to unary (1 command repeated X times), although you would need to compile the initial binary or unary tape to an intermediate Reversible Bitfuck (or Nanofuck) command tape. In other words, creating a 2-commands or 1-command programming language is possible but it cannot have Property II.

--Metanetwork (talk) 02:48, 4 January 2024 (UTC)

Talk:Picofuck