Skip to main content
Post Made Community Wiki by Asaf Karagila
Source Link
Dan Turetsky
  • 3.1k
  • 16
  • 27

Hamiltonian Path is NP-complete; an infinite analog would have us looking for an infinite or bi-infinite such path through a computably given graph. It's easy enough to see that you can encode any $\Sigma^0_1$ question into either version of this problem, and so it's undecidable.