User:Orby/Stochastic

Let x be a real number in [0, 1]. Let y be a random variable which is equal to 1 with probability x and 0 otherwise. I have been considering a language that performs computation by sampling y and manipulating the value. This would fall under the category of stochastic computing.

Encoding a tape

Suppose we have a right unbounded binary tape. Let n_i be the value of the i-th cell. We can let x represent the tape if we set x := Σ n_i * 2^-i.

Let z be equal to 1 with probability 0.5 and be equal to 0 otherwise. We can sample y w.r.t. the right unbounded binary tape in the following way

1. i := 0
2. i := i + 1
3. if (z == 1) goto (2)
4. y := n_i

Decoding a tape

By sampling y m-times and computing the mean, we get a value that converges on x as m approaches infinity. To compute n_i

1. i := 1
2. m := m ÷ 2
3. n_i := j ÷ m
4. j := j % m
5. i := i + 1
6. goto (2)

where m is initialized to the number of samples taken and j is initialized to the number of ones sampled.

Decoding the output of a program

Running the program n times. Each output will be a zero or a one. Computing the mean and call it x_n. As n goes to infinity, x_n goes to the output value of the program. Note with this particular encoding of the tape, we get back earlier cells with greater accuracy than the later cells for a given n.

Sample programs

Cat

y

Flip every bit on the tape

~y