Warning: This post is an incomplete research project.
Lets go hunting! This is a hunt for cool numbers, and by cool I mean serious William Gibson cyberspace Neo-Maas black ice. We’re talking uncomputable numbers. Numbers like Chaitin’s Omega.
Uncomputable sequences are fascinating. After seeing a lot of number hunters hit paydirt doing “busy beaver” calculations for different kinds of simple Turing machines, we’re going to go on beyond zebra, keeping busy like beavers, and we’re going to start from scratch with our own Turing machine variant to keep things interesting.
The bitsorter (TM)(R) is a theoretical computer that operates on a tape or input stream of random bits, selecting some to write to the output, and leaving some aside, until it eventually stops with a final output (the answer) or doesn’t stop and goes on forever.
The idea came from reading Chaitin, and from a method a close friend uses to sort mail into two piles, one which might still be important, and one ready to throw away now. Repeat as necessary, and you will never have to open the mail. And from briefly working on a project suggested by Ohad from IDNI, using Binary Decision Diagrams as fundamental units of computation. Further motivation comes from the indispensable randomness or entropy that some algorithms (monte carlo simulation, digital signatures, key generation) require, and so instead of a classic initial condition Turing machine with a blank tape, we begin with a source of random bits.
A state in the bitsorter is a configuration of the sorter with a specific action defined for the two possible cases: either the next bit is a zero, or the next bit is a one. A given state will always do the same thing if it encounters the same bit.
Switch (next bit on tape)
Case 0: [0 or 1] (0 = discard bit, 1=append bit (0) to output) then go to state X
Case 1: [0 or 1] (0 = discard bit, 1=append bit (1) to output) then go to state Y
(This fully defines a state of a bitsorter computer)
A “program” for this computer is a collection of some number of defined states, with one designated to be the starting state.
There is one “do nothing” state called the stopped state, and if a program gets there, it is stopped. If a program needs a “1” for the output, it must wait for a “1” to arrive in the input stream so it can sort it to the output.
Single State Bitsorter Programs
Lets tabulate all the possible single state bitsorter computer programs.
Of course, the stopped state is one single state computer – it is also the only one state computer program that halts. The number of possible states that one could use to make a one state bitsorter computer is therefore five:
- Stopped (do nothing)
- 00 – Continue processing input forever, never produce any output.
- 01 – Collect all the ones into the output and never stop
- 10 – Collect all the zeros into the output and never stop
- 11 – Copy the entire input to the output and never stop
Two State Bitsorter Programs
With two states, it is now possible for another state to point to the stopped state, enabling programs that both produce an output and halt.
An example possible state:
Case: 0 (0 or 1) keep or discard the bit. Go to state (a or b)
Case: 1 (0 or 1) keep or discard the bit, Go to state (a or b)
We can see there are now 16 possible non stopping states to choose from, so if we include the stop state we have 17*17 = 289 sets of two states, so choosing which to start from is one more factor of two and we have 678 possible two state sorter programs, many of which are identical because of the symmetry. Before breaking that down however, we can narrow our goalposts by insisting that one of the two states is the stopped state, which isn’t the initial state. In this case we have 16 possible programs, which we can enumerate as follows, using a to represent the stopped state and b to represent the other state:
(0,0) (a,a) stop, no output
(0,1) (a,a) if first input is a one, output it, then stop
(1,0) (a.a) if first input is a zero, output it, then stop
(1,1) (a,a) output first digit, then stop
(0,0) (a,b) stop on first zero, no output
(0,1) (a,b) output the ones until a zero appears
(1,0) (a.b) output first zero and stop
(1,1) (a,b) output all digits then first zero and stop
(0,0) (b,a) stop on first one, no output
(0,1) (b,a) output first one then stop
(1,0) (b.a) output all zeros then stop on first one
(1,1) (b,a) output all digits then first one and stop
(0,0) (b,b) never stop, no output
(0,1) (b,b) never stop, output all ones
(1,0) (b.b) never stop, output all zeros
(1,1) (b,b) never stop, output all input
We can see that the last four of these 16 programs are identical to our four non-halting one state programs, so we really have 12 new programs amongst these two-state-one-of-which-is-the-stop-state programs.
Stop state plus two other state bitsorter programs
The possible non-stopped states in a three state program will look like:
(0 or 1 , 0 or 1) (a b or c , a b or c) (keep or save zero, keep or save one, where to go on zero, where to go on one)
2*2*3*3 = 36 possible such states, of which we are choosing two non-stopped states for our program so there are 2*36^2 = 2592 possible such programs, as choosing which one will be the starting state is another factor of two.
Stop state plus N other state bitsorter programs
The possible non-stopped states in an N state program will look like:
(0 or 1, 0 or 1) (S0, S1, … or SN , S0, S1, lll or SN) (keep or save zero, keep or save one, where to go on zero, where to go on one)
2*2*N*N=4N^2, of which we are choosing N-1 non-stopped states for our program so there are (N-1)* (4N^2)^(N-1) programs, as choosing which one will be the starting state is another factor of (N-1).
Number of possible programs of an N state bitsorter computer with one state being the stopped state, and beginning with a non-stopped state.
| 1 | 0 |
| 2 | 16 |
| 3 | 2592 |
| 4 | 786432 |
| 5 | 400000000 |
| 6 | 309586821120 |
| 7 | 340163474251776 |
| 8 | 5.04403158265496E+017 |
| 9 | 9.71516248772754E+020 |
| 10 | 2.359296E+024 |
Wow, four hundred million possible programs exactly for a five state computer. interesting. Well maybe it’s only interesting because I have ten fingers. The number possible programs of a given state gets big quickly, but not as quickly as some Turing machines which have additional degrees of freedom go change direction on the tape.
Comments on the Method (COMING SOON?)
The questions of course are how many programs of N states halt, which is the busy bitsorter problem: BB(N), and what is the largest output possible with N states: L(N). At this point it’s not exactly clear how the randomness factor might influence these
I don’t have the punchline for you yet but here’s the results of some simulations of all four state machines:
max output is 1000110111
total programs stopped: 945
I think the simplicity of this computing model is desirable for some further excursions into fundamental computer science, however there isn’t enough room in the margin at the moment to go further.