Evolutionary code and the probabilistic lambda calculus

Anyone who considers arithmetical methods of producing
random digits is, of course, in a state of sin.
— John von Neumann

A probabilistic lambda calculus (p-lambda calculus) is defined as follows:

Given

variables: v₁ v₂ ...
abstraction symbols: λ . ⊕    ["lambda", "dot", "oplus"]
parentheses: ( )    ["left paren", "right paren"]

the set of probabilistic lambda expressions, Λ_p, is defined inductively:

1. If x is a variable, then x ∈ Λ_p
2. If x is a variable and M ∈ Λ_p, then (λx.M) ∈ Λ_p
3. If M ∈ Λ_p, N ∈ Λ_p, then (M N) ∈ Λ_p
4. If M ∈ Λ_p, N ∈ Λ_p, then (M ⊕ N) ∈ Λ_p;

Instances of rule 2 are known as abstractions, instances of rule 3 are known as applications, and instances of rule 4 are known as choices. The choice symbol ⊕ is a symbol added to the standard lambda calculus: M ⊕ N reduces to M or N with equal probability (0.5). (Along with the standard α, β, and η reduction of the lambda calculus, this reduction will be called φ reduction.)

(Note: The choice symbol enters the Church programming language via the flip function.)

A Tutorial Introduction to the Lambda Calculus provides lambda-expression definitions of natural numbers and arithmetic operators. From there the lambda calculus can be shown to be the basis for all (deterministic) programming code. The probabilistic lambda calculus is the basis for all probabilistic code.

The presentations of what is called by various names — digital physics, the computational universe, ... — appear to assume non-randomness. But this assumption of a deterministic machine "running" the code of the universe is a dogmatic^* assumption. Ockham's razor should apply: Pure randomness is simpler than any deterministic pseudo-random number generator.

HotBits (from @Fourmilab) gives random numbers (quantum, or q-random numbers) from a quantum process via a hardware device. A program can obtain (jQuery.get()) an XML document with 128 (max size 2048) random numbers by

https://www.fourmilab.ch/cgi-bin/Hotbits?nbytes=128&fmt=xml

returning

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE hotbits SYSTEM
       "http://www.fourmilab.ch/hotbits/hotbits.dtd">
<hotbits version="1.0">
<status version="1.0" result="200">OK</status>
<request-information version="1.0">
    <server-version>Release 3.2, June 2008</server-version>
    <generation-time>2013-05-02T09:00:51Z</generation-time>
    <bytes-requested>128</bytes-requested>
    <bytes-returned>128</bytes-returned>
    <quota-requests-remaining>116</quota-requests-remaining>
    <quota-bytes-remaining>11776</quota-bytes-remaining>
</request-information>
<random-data version="1.0">
    B6 FD 92 5A 59 26 51 9C 28 FF B7 26 F8 2D ED 55
    0C 9D D5 79 FF E9 BE FF 1B A2 E0 D2 D4 2B 4B 7A
    56 39 81 C0 97 AA 75 98 C3 4D E9 BF 8E 14 C7 7B
    6D 07 6F 55 C1 28 B4 3B 2E 6A E8 C6 CF 86 B2 76
    52 53 4D 68 84 DD C9 35 05 0C 83 E4 56 9F 7A 33
    9B A5 DB 8D 81 84 46 C8 7A 13 50 0C 6E 0B 01 E0
    27 0F 06 4E 5F E7 12 8B 05 10 D8 24 9A BC CD F7
    33 8B 0B 4F B1 5D 29 77 5A 08 26 13 7A B1 B3 F9
</random-data>
</hotbits>

Another call to this device will give a different set of q-random numbers (unless a really freak event has occurred!).

So random numbers do not have to come from a deterministic pseudo-random generator. They can come right from the quantum world itself, and we can escape from the sin of John von Neumann! And if we assume ⊕ is based on quantum (pure) randomness, we can create evolutionary code (in the sense of genetic programming and evolutionary computation, evolving everything from The Big Bang to The Big Bopper) that is not bound inside a deterministic framework of what is generally referred to as the computational model of the universe. We can now have genetic programming with the p-lambda calculus in a truly stochastic computational universe.


* (I've never understood the "computational universe" advocates' dogmatic adherence to determinism. There is no justification I've seen for sticking to that belief.)