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· 2 claims· 2 episodes

Polya recurrence theorem

The theorem that a random walk on a one-dimensional (or two-dimensional) lattice returns to its starting point with probability one.

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


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

Most important claims · 2 of 2Search all claims for “Polya recurrence theorem” →
  • Although the halting problem is undecidable, it has a 'black hole': there is a computable procedure that correctly decides almost every instance, because the asymptotic density of programs whose head falls off the tape (via random-walk behavior, by Pólya's recurrence theorem) before repeating a state goes to 100% as the number of states grows.Joel David Hamkins
  • 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