Background

Yes, bitstring physics is a real thing. The idea is to construct a new theory of physics using only strings of bits that evolve under a probabilistic rule... or something. Despite reading a couple of papers about it, I'm still pretty confused. However, the bitstring universe makes for a nice little code golf.

Program Universe

Bitstring physics takes place in a so-called program universe. At each step of the evolution of the universe, there is a finite list L of bitstrings of some length k, starting with the two-element list [10,11] where k = 2. One timestep is processed as follows (in Python-like pseudocode).

A := random element of L
B := random element of L
if A == B:
for each C in L:
append a random bit to C
else:
append the bitwise XOR of A and B to L

All random choices are uniformly random and independent of each other.

Example

An example evolution of 4 steps might look like the following. Start with the initial list L:

10
11

We randomly choose A := 10 and B := 10, which are the same row, which means we need to extend each string in L with a random bit:

101
110

Next, we choose A := 101 and B := 110, and since they are not equal, we add their XOR to L:

101
110
011

Then, we choose A := 011 and B := 110, and again append their XOR:

101
110
011
101

Finally, we choose A := 101 (last row) and B := 101 (first row), which are equal, so we extend with random bits:

1010
1100
0111
1010

Your task is to take a nonnegative integer t as input, simulate the program universe for t timesteps, and return or print the resulting list L. Note that t = 0 results in the initial list [10,11]. You can output L as a list of lists of integers, list of lists of boolean values or a list of strings; if output goes to STDOUT, you may also print the bitstrings one per line in some reasonable format. The order of the bitstrings is significant; in particular, the initial list cannot be [11,10], [01,11] or anything like that. Both functions and full programs are acceptable, standard loopholes are disallowed, and the lowest byte count wins.

• Can we limit the bit string length (that is: may I use 32 bit numbers and bit operations)? – edc65 Jun 16 '15 at 9:58
• @edc65 No, the length of the strings can get arbitrarily high. – Zgarb Jun 16 '15 at 10:08
• @edc65 The expected time and memory requirements for getting over 32 bits are astronomical, but that's just fitting since we're simulating a universe. ;) – Zgarb Jun 16 '15 at 18:53
• Is this Bit-string Physics a crackpot idea? I haven't read the whole paper, but the phrase We have used bit-string physics to provide a theory in which the approximation hbar c/e2 = 22 - 1 + 23 - 1 + 27 - 1 = 137 makes sense in terms of a computer algorithm and information theory strikes me as a bit ... numerological. – xebtl Jun 17 '15 at 7:26
• @xebtl It does seem crazy to me too. I remember reading a justification for the algorithm somewhere, and it sounded more like bad pseudo-philosophy than physics. Also, your description of the algorithm seems to match my version, maybe I'm misunderstanding you in some way. – Zgarb Jun 17 '15 at 18:11

Pyth, 27 26 bytes

u?+RO2GqFKmOG2aGxVFKQ*]1U2

Try it online: Demonstration

Explanation:

implicit: Q = input number
*]1U2    the initial list [[1,0], [1,1]]
u                   Q         reduce, apply the following expression Q times to G = ^
mOG2                  take two random elements of G
K                      store in K
qF                       check if they are equal
?                              if they are equal:
+RO2G                           append randomly a 0 or 1 to each element of G
else:
aG                  append to G
xVFK              the xor of the elements in K
• xVFK is equivalent to xMK. – isaacg Jun 16 '15 at 0:19
• @isaacg No, xVFK is equivalent to xMCK, same byte count. – Jakube Jun 16 '15 at 7:09

CJam, 424038 37 bytes

1 byte saved by Sp3000.

B2b2/q~{:L_]:mR_~#L@~.^a+L{2mr+}%?}*p

Explanation

Create the initial state as a base-2 number:

B2b e# Push the the binary representation of 11: [1 0 1 1]
2/  e# Split into chunks of 2 to get [[1 0] [1 1]]

And then perform the main loop and pretty-print the result at the end:

q~       e# Read and eval input t.
{        e# Run this block t times.
:L     e#   Store the current universe in L.
_]     e#   Copy it and wrap both copies in an array.
:mR    e#   Pick a random element from each copy.
_~     e#   Duplicate those two elements, and unwrap them.
#      e#   Find the second element in the first. If they are equal, it will be found at
e#   index 0, being falsy. If they are unequal, it will not be found, giving
e#   -1, which is truthy.

e#   We'll now compute both possible universes for the next step and then select
e#   the right one based on this index. First, we'll build the one where they were
e#   not equal.

L@~    e#   Push L, pull up the other copy of the selected elements and unwrap it.
.^     e#   Take the bitwise XOR.
a+     e#   Append this element to L.

L      e#   Push L again.
{      e#   Map this block onto the elements in L.
2mr+ e#     Append 0 or 1 at random.
}%
?      e#   Select the correct follow-up universe.
}*
p        e# Pretty-print the final universe.

Test it here.

Julia, 141 129 bytes

t->(L=Any[[1,0],[1,1]];for i=1:t r=1:length(L);A=L[rand(r)];B=L[rand(r)];A==B?for j=r L[j]=[L[j],rand(0:1)]end:push!(L,A$B)end;L) Nothing clever. Creates an unnamed function that accepts an integer as input and returns an array of arrays. To call it, give it a name, e.g. f=t->.... Ungolfed + explanation: function f(t) # Start with L0 L = Any[[1,0], [1,1]] # Repeat for t steps for i = 1:t # Store the range of the indices of L r = 1:length(L) # Select 2 random elements A = L[rand(r)] B = L[rand(r)] if A == B # Append a random bit to each element of L for j = r L[j] = [L[j], rand(0:1)] end else # Append the XOR of A and B to L push!(L, A$ B)
end
end

# Return the updated list
L
end

Examples:

julia> f(4)
4-element Array{Any,1}:
[1,0,1,0]
[1,1,1,1]
[0,1,1,0]
[0,1,0,0]

julia> f(3)
3-element Array{Any,1}:
[1,0,1,1]
[1,1,1,0]
[0,1,0,1]

Saved 12 bytes thanks to M L!

Try me.

R, 186

L=list(0:1,c(1,1))
if(t>0)for(t in 1:t){A=sample(L,1)[]
B=sample(L,1)[]
if(all(A==B)){L=lapply(L,append,sample(0:1, 1))}else{L=c(L,list(as.numeric(xor(A,B))))}}
L

Nothing magical here. Enter the value for t in the R console and run the script. It's hard to "golf" R code but here's a more readable version:

L <- list(0:1, c(1, 1))
if(t > 0) {
for(t in 1:t) {
A <- sample(L, 1)[]
B <- sample(L, 1)[]
if (all(A == B)) {
L <- lapply(L, append, sample(0:1, 1))
} else {
L <- c(L,list(as.numeric(xor(A, B))))
}
}
}
L
• You can save a number of characters by assigning sample to a variable. eg s=sample, then use s rather than sample. Unfortunately I think your method of appending a random bit in the lapply will end up with one random sample being added to all items in the list. lapply(L,function(x)append(x,sample(0:1,1))) appears to work, but at a cost. You can replace you as.numeric with 1* which should get some back. – MickyT Jun 17 '15 at 2:21
• Good catch on both points, and a nice coercion trick too – shadowtalker Jun 17 '15 at 3:56
• Also just noticed your count is out. I make it 168 using this – MickyT Jun 17 '15 at 22:44

Ruby, 82

Pretty much straight-forward. Compared with other non-golfing languages, ruby seems to do well with its large standard library.

->t{l=[2,3]
t.times{a,b=l.sample 2
a.equal?(b)?l.map!{|x|x*2+rand(2)}:l<<(a^b)}
l}

Sample output for t=101010 :

[9, 15, 6, 13, 5, 12, 10, 11, 5, 4, 15, 13, 2, 7, 11, 9, 3, 3, 8, 6, 3, 13, 13, 12, 10, 9, 2, 4, 14, 9, 9, 14, 15, 7, 10, 4, 10, 14, 13, 7, 15, 7]