But conversely, I don't understand turing machines well enough to understand how inspecting one won't result in answering whether it halts or not.
Or put in another way: How does a simple Python program, that one cannot determine whether it halts or not, look?
You could write quite a short program to search for a counterexample - for each even number, check to see if it's the sum of two prime numbers. If it's not, then print it and halt, if it is then go on to the next number.
Looking at this program, you could easily understand how it works, but to know if it halts you need to solve one of the most famous open problems in mathematics.
That's not exactly the right way to look at it. The better way to think of it is to say: for every potential solution to the halting problem, there is a program for which that solution doesn't work. So what the counterexample looks like will depend on your proposed halting problem decider.
Let's imagine your wrote a function "halts(program)" that takes a program as input and returns whether that program halts or not. Let's also for simplicity assume that the program input is just the string representation of the source code in e.g. Python. And let's ignore programs that depend on arguments for now.
Now write the following program, let's call it X:
if halts(X):
while true:
pass
now, what is the response of "halts(X)"? (remember: X is just the source code of the program above)
Well, let's first assume that X is a program that halts. Then, wenn we run X, it checks whether it itself halts. Since it does, it then goes into an infinite loop... wait, but then halts can't be right, since it told us X would halt, but it doesn't.
If we assume that X doesn't halt, then conversely, X checks itself, finds out it doesn't halt and then... halts. Another contradiction.
This proves that the function "halts" cannot actually be written, for if it could, it would immediately give the wrong answer for this program X.
The central argument is, in principle, not more complex than what I've shown. The actual complexity of the proof comes from the whole self-referentiality argument, namely that we can actually embed X within itself. This is quite non-trivial, since we have to prove it in the general case.
When I first read about it years ago, I mistakenly assumed it was ‘deeper’ or more profound.
But, at the end of the day, it is just a variant in the old “This Sentence Is False” riddle you’d encounter as a kid.
Papers on the topic are frequently spruced up with complicated gibberish... but, unless we are both missing something fundamental, it’s really as simple as set forth in your post.
The halting problem is actually theoretically decidable for real world programming languages such as Python. That's because in the real world, computers have finite memory, and the halting problem actually decidable for machines with finite memory (linear bounded automata).
Not practically decidable – if a program consumes 1MB of RAM, then (in the general case) solving the halting problem for it will take approximately 2^1048576 steps, which is much longer than the age of the universe.
For example, you can easily prove that your hello world program will halt. In fact, any program which does not have any flow control can be proven to halt. Even if the program has flow control, you can still prove that it halts by proving that iteration is bounded by some number that is strictly decreasing.
So yes, for each program given some specific input, the program either halts or it doesn't halt. And there is always a way in which you can determine if that is the case: You simply run it until either the program halts or it goes back to an earlier state. The halting program says that there is no general solution that allows you to look at a program to determine this property.
I find this answer on quora to the question of why Turing machines are a good model to be insightful: https://qr.ae/pGGCmq
If we could decide the halting problem, we can write a program P that receives another program x as input, such that P(x) halts if x(P) doesn't halt, and otherwise loops forever. What is the value of P(P)?