Well, obviously, the shortest program that outputs "0" is "0". And the shortest program that outputs "1" is "1". We're only interested in the general case, not

Well, obviously, the shortest program that outputs "0" is "0". And the shortest program that outputs "1" is "1". We're only interested in the general case, not specific cases. Just wanted to note that we have techniques for termination analysis that cover entire classes of programs of arbitrary length, not just specific short programs. See ranking function synthesis for an example. Hell, under some universal computational models, the halting problem is polynomial-time decidable for almost all programs: https://arxiv.org/abs/math/0504351 https://arxiv.org/abs/math/0504351.