What fraction of Turing machines implement computable functions?
4
415Ṁ320
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. (Enumerated in increasing number of states.)

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

Market context
Get
Ṁ1,000
to start trading!
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.

@gregrosent I'm ...not? This is a question about the set of all Turing machines, not how to transcribe them.

@IsaacKing There are ℵ_0 Turing machines, of which ℵ_0 halt (i.e. implement a computable function) and ℵ_0 don't. ℵ_0/ℵ_0 isn't a well defined fraction, so the only interpretation of the question that makes sense to me is "Let M_1, M_2, M_3, ... be an enumeration of all Turing machines. What's the limit as n goes to infinity of the fraction of {M_1, M_2, ..., M_n} that implement computable functions (if the limit exists)?" I don't remember what I was thinking when I wrote the above comments, but looking at it now, it seems I was expecting M_i to be the output of a UTM applied to the binary representation of i or something like that (which seems like the most natural way of enumerating Turing machines).

@gregrosent Oh, enumerated in increasing number of states. Guess I didn't specify that anywhere, oops.

© Manifold Markets, Inc.TermsPrivacy