- 8,337

- 2,510

Yes, there are certainly cases where you can prove that a program definitely does halt on certain inputs, and there are cases where you can prove that a program definitely does not halt on certain inputs. But to get a listing of all computable programs, you need to be able to tell, for an arbitrary program, whether it halts on all possible inputs.Yes. My mistake.

The crux of my objection was here. Consider the busy beaver function, (##BB(n)## = the maximum number of steps that an ##n##-state Turing machine takes before it halts, excluding non-halting TM's) which is by definition non-computable (equivalent to the halting problem). However, given an ##n##, we can find (andhave found)at least a few specific values of ##BB(n)##, for instance ##BB(4)=107##. The whole reason we can do that is because we can enumerate all 4-state Turing machines and exhaustively show that any of these TM's that runs for more than 107 steps eventually enters a loop (and therefore never halts). So even though the busy beaver function isn't computable, we can still find ##BB(n)## for specific values of ##n##.