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