Skip to main content
2 of 4
added 416 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Generic Turing machine programs are unreasonable: the computation head will fall off the tape.

Basically, the situation is that on the usual one-way infinite tape model, a random program causes a random walk type behavior for the head position, and consequently by Polya's recurrence theorem, it follows that almost all Turing machine programs lead eventually to the situation where the head attempts to move left from the left-most cell (before they repeat a state), causing the head to fall off the tape.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k