[Question]
  [
# Background
Yes, bitstring physics is [a real thing](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=363694&punumber%3D2948%26filter%3DAND%28p_IS_Number%3A8339%29%26pageNumber%3D2).
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
```
# The Task
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.
  
[Answer]
# CJam, ~~42~~ ~~40~~ ~~38~~ 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.](http://cjam.aditsu.net/#code=YZ%5DYfbq~%7B%3AL_%5D%3AmR_~%23L%40~.%5Ea%2BL%7B2mr%2B%7D%25%3F%7D*p&input=4)
[Answer]
# Pyth, ~~27~~ 26 bytes
```
u?+RO2GqFKmOG2aGxVFKQ*]1U2
```
Try it online: [Demonstration](https://pyth.herokuapp.com/?code=u%3F%2BRO2GqFKmOG2aGxVFKQ*%5D1U2&input=0&debug=0)
### 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
```
[Answer]
# 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!
[Answer]
# Python 2, 141
I tried a few different methods, but the best I could get was relatively straightforward. Thanks to @Sp3000 for 15 chars or so (and for teaching me about the existence of `int.__xor__`).
```
from random import*
L=[[1,0],[1,1]];C=choice
exec"A=C(L);B=C(L);L=[L+[map(int.__xor__,A,B)],[x+[C([1,0])]for x in L]][A==B];"*input()
print L
```
[Answer]
# Pyth, 34
```
u?+RO`TGqJOGKOG+Gsm`s!dqVJKQ[`T`11
```
Uses reduce to apply each iteration. I'll explain when I'm done golfing.
[Try it here](https://pyth.herokuapp.com/?code=u%3F%2BRO%60TGqJOGKOG%2BGsm%60s!dqVJKQ%5B%60T%6011&input=4&debug=0)
[Answer]
# K, 46 53 46 bytes
```
{x{:[~/t:2?x;{x,*1?2}'x;x,,,/~=/t]}/(1 0;1 1)}
```
A good chunk of the size (about 7 bytes) of this is do to the fact that K has no `xor` operator, so I had to implement one myself. Originally, I used a list of strings, followed by realizing that was insanely stupid. So now I cut off the 7 bytes again!
Before:
```
{x{:[~/t:2?x;{x,*$1?2}'x;x,,,/$~=/(0$')'t]}/$:'10 11}
```
@JohnE pointed out in the comments that the initial state was supposed to be hardcoded, which cost 7 extra bytes. :/
[Answer]
# JavaScript (*ES6*) 152
A function, using strings (with numbers it should be shorter, but in javascript bit operations are limited to 32 bit integers). 
Test in Firefox using the snippet below.
```
F=(t,L=['10','11'],l=2,R=n=>Math.random()*n|0,a=L[R(l)],b=L[R(l)])=>
   t--?a==b
     ?F(t,L.map(x=>x+R(2)),l)
     :F(t,L,L.push([...a].map((x,p)=>x^b[p]).join('')))
  :L
  
test=_=>O.innerHTML=F(+I.value).join('\n')
```
```
#I{width:3em}
```
```
<input id=I value=10><button onclick=test()>-></button><pre id=O></pre>
```
[Answer]
# K, ~~45~~ ~~41~~ 38 bytes
```
{x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}
```
The structure of my answer is quite similar to that of @kirbyfan64sos, but instead of strings I used 1/0 vectors and I avoid the need for a conditional (`:[ ; ; ]`) by instead indexing into a list.
A few runs:
```
  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0 0
 1 1 1 1
 0 1 1 1)
  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0
 1 1 0
 0 1 0
 1 0 0)
  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0
 1 1 0
 0 1 0
 1 1 0)
```
## Edit:
Saved four bytes with a more compact way to build the initial universe:
```
1,'!2     / new
(1 0;1 1) / old
```
## Edit2:
I forgot that "choose" can take a list as its right argument:
```
  2?"abcd"
"dc"
  2?"abcd"
"cc"
  2?"abcd"
"ca"
```
So I can simplify part of this. Credit where it's due, Kirby got this trick before I did.
```
2?x    / new
x@2?#x / old
```
[Answer]
# Javascript, ~~241~~ 233 bytes
That's kind of long.
```
a=[[1,0],[1,1]];for(b=prompt();b--;)if(c=a.length,d=a[c*Math.random()|0],e=a[c*Math.random()|0],d+""==e+"")for(f=0;f<c;f++)a[f].push(2*Math.random()|0);else{g=[];for(h=0;h<d.length;h++)g.push(d[h]^e[h]);a.push(g)}alert(a.join("\n"));
```
[Answer]
# T-SQL (2012+), 1019
I'm really sorry this is nowhere near competitive, but to be honest I didn't think I could get this to work and had to post it once I did. I did try to golf it a bit :)
To handle the binary/integer conversions I had to create a couple of scalar functions (513 of the bytes). `A` goes from integer to a bit string. `B` does the reverse.
```
CREATE FUNCTION A(@ BIGINT)RETURNS VARCHAR(MAX)AS
BEGIN
DECLARE @S VARCHAR(MAX);
WITH R AS(SELECT @/2D,CAST(@%2 AS VARCHAR(MAX))M
UNION ALL
SELECT D/2,CAST(D%2 AS VARCHAR(MAX))+M
FROM R
WHERE D>0)SELECT @S=M FROM R WHERE D=0
RETURN @S
END
CREATE FUNCTION B(@ VARCHAR(MAX))RETURNS BIGINT AS
BEGIN
DECLARE @I BIGINT;
WITH R AS(SELECT CAST(RIGHT(@,1)AS BIGINT)I,1N,LEFT(@,LEN(@)-1)S
UNION ALL 
SELECT CAST(RIGHT(S,1)AS BIGINT)*POWER(2,N),N+1,LEFT(S,LEN(S)-1)
FROM R
WHERE S<>''
)SELECT @I=SUM(I)FROM R
RETURN @I
END
```
Then there is the procedure. `@C` is the number of steps
```
DECLARE @C INT=9
DECLARE @ TABLE(S VARCHAR(MAX))
DECLARE @R VARCHAR(MAX)
INSERT @ VALUES('10'),('11')
WHILE(@C>=0)
BEGIN
SET @C-=1
SELECT @R=CASE WHEN MAX(S)=MIN(S)THEN''ELSE RIGHT(REPLICATE('0',99)+dbo.A(dbo.B(MAX(S))^dbo.B(MIN(S))),LEN(MAX(S)))END
FROM(SELECT TOP 2S,ROW_NUMBER()OVER(ORDER BY(SELECT\))N FROM @,(VALUES(1),(1),(1))D(D)ORDER BY RAND(CAST(NEWID()AS VARBINARY(50))))A
IF @R=''UPDATE @ SET S=CONCAT(S,ROUND(RAND(CAST(NEWID() AS VARBINARY(50))),0))
ELSE INSERT @ VALUES(@R)
END
SELECT * FROM @
```
Ten thousand iterations took around 2 minutes and returned 9991 rows
```
1001001100110
1101001001110
0111100100101
1111100001011
1111001010011
0110101001101
...
1110101000100
1111011101100
1100001100010
0110010001001
1110100010100
```
[Answer]
# Pyth - 37 bytes
Obvious, just follows psuedocode. Probably can golf a lot.
```
KPP^,1Z2VQ=K?m+dO1KqFJ,OKOKaKxVhJeJ;K
```
[Try it here online](http://pyth.herokuapp.com/?code=KPP%5E%2C1Z2VQ%3DK%3Fm%2BdO1KqFJ%2COKOKaKxVhJeJ%3BK&input=4&debug=1).
[Answer]
# Mathematica, 106 bytes
```
Nest[If[Equal@@#,Map[#~Append~RandomInteger[]&],Append[BitXor@@#]]&[#~RandomChoice~2]@#&,{{1,0},{1,1}},#]&
```
[Answer]
# Perl, 102
```
#!perl -p
@l=qw(10 11);$_=$l[rand@l]^$l[rand@l],$_|=y//0/cr,@l=/1/?(@l,$_):map{$_.~~rand 2}@l for 1..$_;$_="@l"
```
Try [me](http://ideone.com/KAQAyx).
[Answer]
## R, 186
```
L=list(0:1,c(1,1))
if(t>0)for(t in 1:t){A=sample(L,1)[[1]]
B=sample(L,1)[[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)[[1]]
    B <- sample(L, 1)[[1]]
    if (all(A == B)) {
      L <- lapply(L, append, sample(0:1, 1))
    } else {
      L <- c(L,list(as.numeric(xor(A, B))))
    }
  }
}
L
```
[Answer]
# 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]
```
]