User:Orby/Stochastic

From Esolang
Jump to navigation Jump to search

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

  1. i := 0
  2. i := i + 1
  3. if (z == 1) goto (2)
  4. 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

  1. i := 1
  2. m := m ÷ 2
  3. ni := 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 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.

Sample programs

Cat

y

Flip every bit on the tape

~y