What fraction of Turing machines implement computable functions?
4
143
415
2200
25%
[0%, 10%)
7%
[10%, 20%)
7%
[20%, 30%)
7%
[30%, 40%)
7%
[40%, 50%)
7%
[50%, 60%)
7%
[60%, 70%)
7%
[70%, 80%)
7%
[80%, 90%)
7%
[90%, 100%]
11%
Doesn't converge

I'll specify an implementation if necessary, but I'd expect they all have similar asymptotic behavior.

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. If it doesn't converge at all, resolves N/A.

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-f038c705880f

Get Ṁ200 play money
Sort by:

I suspect it depends on the implementation but it would help to know what you mean by that. E.g. is it an efficient UTM that outputs a distinct TM on all input strings, or is it something more lenient?

@gregrosent It's a traditional Turing machine, tape starts with all 0s.

@IsaacKing I meant how are you encoding the description of a Turing machine as a string.

More related questions