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 ni be the value of the i-th cell. We can let x represent the tape if we set x := Σ ni * 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
- i := 0
- i := i + 1
- if (z == 1) goto (2)
- y := ni
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 ni
- i := 1
- m := m ÷ 2
- ni := j ÷ m
- j := j % m
- i := i + 1
- 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 xn. As n goes to infinity, xn 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.
Flip every bit on the tape