Sheela
Sheela
Home
Add
Questions
Thinkers
Claims
People
Concepts
Jargon
Sources
Health
Predictions
Collections
Domain Landscape
Contribute
Review
Dedup
Topic requests
Settings
Help

← Jargon

Jargontechnology· 1 claim· 1 episode

black hole problem

Miasnikov's concept in decision/complexity theory of a problem that is hard overall but whose difficulty is concentrated in a tiny region, outside of which it is easy to solve.

As defined in 282 | Joel David Hamkins on Puzzles of Reality and Infinity


Where it comes up · 1
  • 282 | Joel David Hamkins on Puzzles of Reality and Infinity1 claim

Most important claims · 1 of 1Search all claims for “black hole problem” →
  • Hamkins and Miasnikov proved that although the halting problem is undecidable, for the one-way infinite tape Turing machine model it is decidable on a set of probability one: as program size grows, the proportion of programs whose halting status can be decided approaches 100%, because by Polya's recurrence theorem a random-walking head falls off the tape with probability one, though the result is fragile because it depends on the chosen computational model.282 | Joel David Hamkins on Puzzles of Reality and Infinity