I think this is one of the things that makes the undecidability of the halting problem hard to grok. You want to say “there are certain machines so complicated

I think this is one of the things that makes the undecidability of the halting problem hard to grok. You want to say “there are certain machines so complicated that it’s impossible for a machine to tell whether they halt or not.” But between the trivial programs “return true” and “return false”, one of them gives the correct answer for any machine and input you throw at them. You want to object “but those programs don’t know anything about Turing machines. They don’t count!” But that’s not what decidability is about. You might want to think something like “ok, but figuring out which of those programs gives the right answer is undecidable,” but again, no, that has a defined true or false answer too. The problem can only become undecidable once it’s extended to an infinite set of machine/input combinations.