No, it’s completely different. The representation of integers as bit strings doesn’t even have to be computable. There will always be an infinite string of bits of which no prefix represents any integer. This can be derived from König’s Lemma, which says that if a finitely branching tree has paths of all finite lengths, it has an infinite path. Consider the infinite binary tree with the out-edges of each node labelled 0 and 1. Chop off all the descendants of every node that represents an integer and consider the tree that remains. Since there are infinitely many integers, there must be such nodes of arbitrarily large depth. Therefore the tree contains an infinite path.
There are certainly connections. König’s Lemma isn’t constructively true, for example. That is, given a computable description of an infinite tree, the problem of finding an infinite path may not be computable. Imagine walking down the tree node by node—how can you tell whether you have stepped into a merely finite but enormously large subtree and have missed the infinite branch? Obviously, an oracle for the halting problem will solve that problem. I don’t know off-hand, or from thinking about it for five minutes, whether the reverse is the case, i.e. if the halting problem can be encoded as the problem of finding an infinite branch in some computable infinite tree.
No, it’s completely different. The representation of integers as bit strings doesn’t even have to be computable. There will always be an infinite string of bits of which no prefix represents any integer. This can be derived from König’s Lemma, which says that if a finitely branching tree has paths of all finite lengths, it has an infinite path. Consider the infinite binary tree with the out-edges of each node labelled 0 and 1. Chop off all the descendants of every node that represents an integer and consider the tree that remains. Since there are infinitely many integers, there must be such nodes of arbitrarily large depth. Therefore the tree contains an infinite path.
Interesting, however it is my understanding that Konig’s lemma is related to the halting problem and the Wiki article agrees with me:
“Any such tree has a path computable from 0′, the canonical Turing complete set that can decide the halting problem.”
There are certainly connections. König’s Lemma isn’t constructively true, for example. That is, given a computable description of an infinite tree, the problem of finding an infinite path may not be computable. Imagine walking down the tree node by node—how can you tell whether you have stepped into a merely finite but enormously large subtree and have missed the infinite branch? Obviously, an oracle for the halting problem will solve that problem. I don’t know off-hand, or from thinking about it for five minutes, whether the reverse is the case, i.e. if the halting problem can be encoded as the problem of finding an infinite branch in some computable infinite tree.