What fraction of Turing machines implement computable functions?

Mini

Ṁ320

2200

ALL

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.

‌

#Math

#Computational Complexity Theory

#Computing

#Computer Science

#Mathematics

Get

1,000

and

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

What is this?

What is Manifold?

Manifold is the world's largest social prediction market.

Get accurate real-time odds on politics, tech, sports, and more.

Win cash prizes for your predictions on our sweepstakes markets! Always free to play. No purchase necessary.

Are our predictions accurate?

Yes! Manifold is very well calibrated, with forecasts on average within 4 percentage points of the true probability. Our probabilities are created by users buying and selling shares of a market.

In the 2022 US midterm elections, we outperformed all other prediction market platforms and were in line with FiveThirtyEight’s performance. Many people who don't like trading still use Manifold to get reliable news.

How do I win cash prizes?

Manifold offers two market types: play money and sweepstakes.

All questions include a play money market which uses mana and can't be cashed out.

Selected markets will have a sweepstakes toggle. These require sweepcash to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.

Redeem your sweepcash won from markets at 1.00
→ $1.00, minus a 5% fee.

Learn more.

What is this?

What is Manifold?

Manifold is the world's largest social prediction market.

Get accurate real-time odds on politics, tech, sports, and more.

Win cash prizes for your predictions on our sweepstakes markets! Always free to play. No purchase necessary.

Are our predictions accurate?

Yes! Manifold is very well calibrated, with forecasts on average within 4 percentage points of the true probability. Our probabilities are created by users buying and selling shares of a market.

How do I win cash prizes?

Manifold offers two market types: play money and sweepstakes.

All questions include a play money market which uses mana and can't be cashed out.

Selected markets will have a sweepstakes toggle. These require sweepcash to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.

Redeem your sweepcash won from markets at 1.00
→ $1.00, minus a 5% fee.

Learn more.

What is this?

Related questions

What is this?

Related questions