Probablyfuck

From Esolang
Jump to navigation Jump to search

Probablyfuck is a variant of brainfuck based on the principles of stochastic computing. Cell values are probabilistic bit streams (also known as Bernoulli processes), which you can operate on with brainfuck-like instructions.

Imagine that the program runs an unbounded number of times, each time with the next bit from each bit stream just like a boolfuck program. At the end of all the runs, each cell has a probability of being 0 or 1 based on how each run changes it, and the resulting tape of probabilities is the result of the probablyfuck program.

This has unusual implications for control flow. If you only consider the whole result of the probablyfuck program, it may seem that while loops can run in a "fuzzy" way, some of its iterations only partially affecting the output of the program. In reality, the loop simply "runs" a different number of times based on what each random bit happens to be during each individual run.

Implementation details and computational class

An implementation of probablyfuck on a regular computer probably would not need to run the program this many times, however. Manipulating the actual values of the probabilities internally and only forking when required would probably suffice.

Probablyfuck is Turing-complete by reduction to boolfuck without I/O. Any boolfuck program without interactivity can trivially be converted to a probablyfuck program. However, probablyfuck programs can be made more efficient by taking advantage of its probabilistic features.

Instructions

Instruction Behavior
% Introduces a random bit with a probability of 0.5, and ORs the current stream with it.
! Inverts the current bit.
# Delays the current bit stream to the next bit.
<> Moves the cell pointer left and right.
[...] Runs the code within while the current bit is 1.

Examples

Multiplication

[>[>!>]]

If the tape is initialized with two independent streams with probabilities of p and q, and a third and fourth stream are both left as 0, this will give the third stream a probability of pq.

Despite only having access to basic control flow, and the ability to conditionally flip a bit, feeding two random streams of bits to this program will result in another random stream of bits, whose probability is the product of the probabilities of the original streams.

At the end of the program, the cell pointer has a pq probability of being on the fourth cell, and a 1 - pq probability of remaining at the first cell.

Here is an alternate method, which guarantees that the cell pointer returns to the first cell, but destroys the operands in the process.

[!>[!>!<]<]

Squaring

A naive implementation of squaring might look like this.

[[>!>]]

This is the same as multiplication, but it checks the first bit stream twice instead of checking two different bit streams. The problem with this is that, because the same bit is checked twice regardless of whether it's 0 or 1, the output will simply be the input bit stream, instead of actually multiplying the probabilities together.

This can be solved with the # operator, which can be used to delay the bit stream after the first check, decorrelating the two values to give the correct result.

[#[>!>]]