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.
Dan Turetsky
- 3.1k
- 16
- 27