What fraction of Turing machines implement computable functions?

Basic

Ṁ320

2200

25%

[0%, 10%)

[10%, 20%)

[20%, 30%)

[30%, 40%)

[40%, 50%)

[50%, 60%)

[60%, 70%)

[70%, 80%)

[80%, 90%)

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

This question is managed and resolved by Manifold.

#Math

#Computational Complexity Theory

#Computing

#Mathematics

#Computer Science

Get

1,000

and

3.00

3 Comments

2 Holders

19 Trades

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.

Related questions

Related questions