21
3
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
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.
Can we limit the bit string length (that is: may I use 32 bit numbers and bit operations)? – edc65 – 2015-06-16T09:58:46.463
1@edc65 No, the length of the strings can get arbitrarily high. – Zgarb – 2015-06-16T10:08:33.520
@Zgarb well, your challenge your rules, but the length grows approximately with
log2(#strings)
, so by the time you hit 32 you will be using 128 GB RAM – DenDenDo – 2015-06-16T13:23:33.7803@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 – 2015-06-16T18:53:15.660
Do we have to preserve leading zeroes? (Since the universe starts with leading 1s, and bits are never prepended or elements removed, the length of any element could always be inferred.) – Martin Ender – 2015-06-16T23:37:08.287
@MartinBüttner Leading zeroes should be preserved. – Zgarb – 2015-06-17T06:32:06.137
5Is 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 – 2015-06-17T07:26:46.790
Also, your "equation of motion" seems different from the one in the paper, We start from a universe of bit-strings of the same length which grow in length by a random bit, randomly chosen for each string whenever XOR between two strings gives the null string; else the resulting non-null string is adjoined to the universe. Is that intentional? – xebtl – 2015-06-17T07:33:14.983
1@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 – 2015-06-17T18:11:02.010
@Zgarb I read whenever XOR between two strings gives the null string as "there is a pair of strings that are equal" rather than "two randomly chosen strings are equal". Of course, it does not matter much for the challenge. – xebtl – 2015-06-18T09:59:50.987