What fraction of Turing machines implement halting functions?
6
475Ṁ266
2200
24%
[0%, 10%)
6%
[10%, 20%)
6%
[20%, 30%)
6%
[30%, 40%)
11%
[40%, 50%)
13%
[50%, 60%)
6%
[60%, 70%)
6%
[70%, 80%)
7%
[80%, 90%)
3%
[90%, 100%]
11%
Doesn't converge

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

Get
Ṁ1,000
to start trading!
© Manifold Markets, Inc.TermsPrivacy