I'll specify an implementation if necessary, but I'd expect they all have similar asymptotic behavior. (Irrelevant information is ignored. e.g. if the implementation gives the halt states a symbol to write onto the tape, )
Resolves once a proof is known that it's within any of these ranges, even if we don't know exactly where in that range. If it seems unlikely that we'll ever narrow it down to a single range but we've at least proven that it's not some of the other ones, I may resolve to multiple.
This is not equivalent to asking for the first digit of Chaitin's constant. Chaitin's constant gives more weight to smaller Turing machines (making the first few digits easily calculable), whereas my question gives more weight to larger machines, asking for the asymptotic behavior as their length goes to infinity.
If we're able to prove that the long-term fraction is bounded by some constant but doesn't converge within those bounds, this market resolves to that range. For example, if after a million states the fraction never leaves the [40%, 60&] range but never settles down any further, this market resolves to those two options in equal proportion. The "doesn't converge" answer is only for cases where we're unable to rule out anything at all.
See also: /IsaacKing/what-fraction-of-turing-machines-im-b4ac02325a4a
1,000
3.00For an example, I'll consider the TM format in this file without any of the redundancy eliminating mechanisms: An n-state TM is a 2 by n table, where each entry is a triple consisting of a tape write value, a direction and either a state or the "halt" symbol.
The probability of not having any halt state at all is (1-1/(n+1))^(2n), which is 1/e^2 = 0.135 in the limit. Therefore on this model, 90-100% halting should be impossible.
This could probably be refined by asking, conditional on k halting states appearing in the table, what the probability is that a backwards-analysis proves those states are impossible to reach.
On the other side, we can put an n+1 state TMs without halting symbols into a (4(n+1))^2-to-1 correspondence with n-state TMs with halting, by deleting the last state of the n+1 State no-halting TMs and turning references to it into references to the halting state. We can ask of the (n+1)-state-no-halting TMs: What fraction of states does it touch? By symmetry, this is the ~same as the probability that it touches the last state and therefore also the same as the probability that the corresponding n-state machine halts. More simply we can ask: What fraction of states does it touch before revisiting a state? It's a birthday problem, so it should be something like O(sqrt(n)), which translates to a probability of at least O(1/sqrt(n)) - this doesn't prove a lower bound on the fraction in the limit though.
You can argue that until the sqrt(n)th step, you have been doing a random walk on the tape and writing random values, which should allow you say that after you first revisit, you are likely to visit other new states again. But I'm not sure how far this can be extended, or if it can be extended to argue that you will touch a constant fraction of the states in expectation.
It seems possible to me that format is relevant. The description in this file https://github.com/bbchallenge/bbchallenge-seed indicates that each transition to a halting state comes with (irrelevant to the halting problem, but relevant to questions of computation) information about what bit is written to the tape state. It seems like this format makes halting at least ~twice as likely as erasing this information, since for every machine that halts with the information erased, there are at least two machines of approximately the same length that halt when the information is not erased.
@BoltonBailey I'll also note that it apparently has completely irrelevant information about direction traveled when halting, which has the same effect.
@happypotamus The tape is of infinite length. https://en.wikipedia.org/wiki/Turing_machine
There's an isomorphism between states and symbols, so I'd expect it to not matter. If it does matter I'll go with the traditional 2-symbol machines.
@BoltonBailey Isn't the halt state symbol a standard part of Turing machines? Where do you see an encoding that removes that information?
@IsaacKing I wouldn't say any standard TM description removes the concept of halting. But the bbchallenge website removes data about what movements or writes are made while halting. See for example the dashes in the description here. (Note how this contrasts with the table in the file I linked above from bbchallenge's GitHub.)
To put it another way, what I'm asking is, of
+---+-----+-----+
| - | 0 | 1 |
+---+-----+-----+
| A | 1RB | 1LC |
| B | 1RC | 1RB |
| C | 1RD | 0LE |
| D | 1LA | 1LD |
| E | 1RH | 0LA |
+---+-----+-----+and
+---+-----+-----+
| - | 0 | 1 |
+---+-----+-----+
| A | 1RB | 1LC |
| B | 1RC | 1RB |
| C | 1RD | 0LE |
| D | 1LA | 1LD |
| E | 1LH | 0LA |
+---+-----+-----+and
+---+-----+-----+
| - | 0 | 1 |
+---+-----+-----+
| A | 1RB | 1LC |
| B | 1RC | 1RB |
| C | 1RD | 0LE |
| D | 1LA | 1LD |
| E | 0LH | 0LA |
+---+-----+-----+Which of these are considered the same machine?
@IsaacKing Hard to say. I think some/many people would say to do the version with the least redundant information, since that makes TMs that are more compressible, so they would say that they are all the same. For my part, I duplicated this market with the rules being that all of the TMs above are different since I think that makes it easier to analyze mathematically. I think either way is fine, it's up to you.
@BoltonBailey Note that there's also the issue of "do we insist that a Turing machine is only valid if the states are sorted in some normalizing way?" I believe bbchallenge insists that as you read states from the top of the table going down, whenever you see a state you haven't seen before, it should always be the earliest-sorted such state (for example, the first transition for the A state is always either to the A state itself, to halt, or to the B state).
Another normalization seems to be that the first direction is always "right" to eliminate the symmetry of direction on the tape.