12

I'm currently teaching a class on computability and recently covered the proof that the halting problem is undecidable. I know of three major proof avenues that can be used here:

  1. Diagonalization - show that if the halting problem were decidable, we could build a machine that, if run on itself, is forced to do the opposite of what it says it will do.
  2. Recursion theorem - show that if the halting problem were decidable, then we could build a machine that obtains its own description, determines whether it halts on its input, then does the opposite.
  3. Reduction - show that some other undecidable problem reduces to the halting problem.

While I completely understand these proofs and think that they're mathematically beautiful, many of my students are having trouble with them because none of the proofs directly address why you can't tell if a program will halt. Nothing in the above proceeds along the line of "computations can evolve in a way that is so complicated that we can't predict what will happen when we start them up" or "machines can't introspective on themselves at that level of detail." I often give these intuitions to my students when they ask why the result holds, but I'm not aware of any formal proofs of that form.

Are there any proofs of the undecidability of the halting problem that directly explore why it's impossible for a program to decide what another program will do?

Thanks!

templatetypedef
  • 10,206
  • 2
    I would venture the claim that diagonalization and recursion are fundamental aspects of the undecidability of the halting problem and that this is a bad idea. I sympathize with the urge to make things easier for students, but sometimes you can't just rely on what students already know; sometimes they have to absorb a genuinely new and important concept. Perhaps other examples of similar proofs might be valuable: http://terrytao.wordpress.com/2009/11/05/the-no-self-defeating-object-argument/ – Qiaochu Yuan May 27 '12 at 02:19
  • 3
    Some programs can decide what another program will do. Depends very much on how restricted the notion of "another program" is. – André Nicolas May 27 '12 at 02:22
  • 1
    @Qiaochu Yuan- I absolutely agree that these are fundamental concepts; I heavily stress diagonalization throughout the course. My intent with a proof of this sort would be to offer it in addition to and not as a replacement for the existing proofs. – templatetypedef May 27 '12 at 02:29
  • Perhaps something that has a more concrete feel, like Goodstein's Theorem, would be a useful thing to talk about. – André Nicolas May 27 '12 at 05:13
  • 3
    These proofs show that the Halting problem for turing machines isnt solvable by turing machines. There is no proof that "directly address why you can't tell if a program will halt", because its not necessarily true. But you can argue for it with the church-turing thesis. – TROLLHUNTER May 27 '12 at 12:25
  • 5
    See this question on cstheory.SE. – Raphael May 27 '12 at 13:08

4 Answers4

16

This is not what you asked for, because it's not a proof. But it is an argument.

Consider some famous and unresolved problem of mathematics, such as the twin primes conjecture. (Or the Collatz conjecture, the Goldbach conjecture, or, until recently, the Fermat conjecture.) I am sure you recall that the conjecture is that there are arbitrarily large numbers $p$ and $p+2$ that are both prime. ("Twin primes")

It's easy to write a computer program which, given an input $N$, looks for a pair of twin primes larger than $N$, and which halts when it finds such a pair.

The twin primes conjecture is true if, and only if, this program halts on all inputs.

Therefore, if there were a reliable way to tell if a program halts on all inputs, the twin primes conjecture would be easy to resolve, and we could conclude from the fact that it is not resolved that mathematicians are all a bunch of dummies.

Now maybe your students don't care about the twin primes conjecture and perhaps they are not sure that mathematicians are not all a bunch of dummies. But they are familiar with problems and puzzles in general, and they are probably familiar with the idea that it is sometimes not only hard to find solutions, but it can even be hard to see ahead of time if if there is a solution. They can probably be persuaded that you can get a computer to search exhaustively for the solution to some problem, and halt and print it out if it finds one.

A solution to the halting problem would mean that a very large class of problems could be easily solved. You would write a program to search for a solution, and then, instead of running it, you would analyze the program to see if it would halt. If the answer was yes, you would know there was a solution, and all you had to do to find it was to run the program. On the other hand if the program would not halt, you wouldn't have to bother to run it because you would know there was no solution.

That would be a very different world from the one we actually live in, and it may be possible to persuade the students of that.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 4
    Well, not all problems would be immediately solvable, but all $\Sigma^0_1$ problems, or maybe all arithmetical problem. The decidability of the halting problem would not immediately imply the decidablity of strictly $\Pi^1_1$ problems, for example. – Carl Mummert May 27 '12 at 04:13
  • 1
    Thanks for the correction. I have edited the answer to moderate my excitement about the world in which the halting problem is decidable. – MJD May 27 '12 at 11:55
  • 3
    I think this is a better argument for $\text{P} \ne \text{NP}$ and related conjectures in complexity theory. After all, just because there is a way to do something doesn't mean there is a way to do it quickly. For instance, there is a very simple program that will break RSA keys... – Zhen Lin May 27 '12 at 12:01
  • If this is a theory of computation course this sort of argument would definitely undermine the material on computational complexity. – Tim kinsella May 27 '12 at 12:11
4

I agree that the usual proofs are not very "informative", in the sense that they don't usually satisfy a student's desire to know why this is the case. A "fully informative" proof would presumably construct the object in question -- but obviously you can't construct an object to show that it doesn't exist! I wouldn't exclude the possibility of finding a "somewhat informative" proof, but I think such a proof, if it exists, might be complicated enough that a persuasive but non-mathematical argument might be better.

Appealing to the idea you mentioned, that "computations can evolve in a way that is so complicated that we can't predict what will happen when we start them up", seems to be a good approach (possibly using the Collatz sequence as an example of a computation that, clearly, evolves in ways we don't yet understand very well.)

A complementary approach might be to ask the student to consider program analyzers. These are programs that take a program as input, and output "yes" if they can prove it has some property (like halting), "no" if they can prove it doesn't, and "don't know" if they can't prove either. There are real-world examples of these programs, and it can be shown some are more sophisticated than others, and tying the argument to real software may help some students get a better conceptual grip on it.

Now ask: what happens if we run one of these program analyzers on, say, the standard Python interpreter? The program analyzer can't truthfully say "yes" or "no", because it doesn't know what Python program the interpreter will be asked to run.

Even if we stipulate that the script that the Python interpreter will be running on be provided to the analyzer, the script itself could be an interpreter for some other programming language (ad infinitum).

Even if we stipulate that the program being analyzed take no input, it might be a Python interpreter with an arbitrary Python script hardcoded in it. (I believe there are actual tools available for Python to do just this.)

Now, this reasoning is not absolutely watertight, but the idea is to emphasize that you can make programs arbitrarily convoluted, and to try to get across, "oh, no matter how sophisticated my program analyzer is, there will always be some program that is so convoluted that it is out of its reach."

Chris Pressey
  • 376
  • 1
  • 13
  • I should note that when I say the reasoning is not absolutely watertight, I mainly mean that I don't see a way to work this into an proper proof; but at the same time, I can't say that it's impossible to do so. It does seem likely that such a proof would be somewhat more "informative" than one based outright on diagonalization. – Chris Pressey Dec 08 '12 at 15:56
1

I realize this isn't exactly what you are asking for, because it still uses diagonalization, but I think it is a fresh approach to the halting problem.

I like to start with the paradoxical statement:

The smallest natural number that cannot be described uniquely in fourteen words or less.

This paradox is, obviously, not a precise statement, so it is not really a mathematical paradox. In particular, what does it mean to be "described?"

But in recursion theory, we can define what we mean by "described" and the size of a statement.

If we could solve the halting problem, we could write a program that computes, for any $N$ the smallest natural number that is not equal to $\phi_n(m)$ for $n,m\leq 2^{N}$. Essentially, we would, for each $n,m<2^N$, ask the halting program whether $\phi_n(m)$ halts, and, if so, compute the value and exclude it.

Say this program computes $\rho(N)$. Assuming the halting problem has a solution, then $\rho$ is recursive, so there is an $n_0$ such that $\rho=\phi_{n_0}$. But then $\rho(n_0)=\phi_{n_0}(n_0)$. This yields your contradiction. $\rho(n_0)$ cannot be the output of any $\phi_n(m)$ with $m,n<2^{n_0}$. But $\rho(n_0)=\phi_{n}(m)$ with $m=n=n_0<2^{n_0}$.

For some reason, I like starting with this informal paradox, and then working from there to try to formalize it, and seeing that, in formalizing it, we've gotten to showing that the halting problem has no solution.

As others have noted, I doubt you can avoid diagonalization at some point. In particular, you are talking about programs that analyze programs, so the "I am lying" paradox is always a risk in such a system.

You might, however, be able to talk about other unsolvable problems. Hilbert's 10th problem, seeking a program that takes a diophantine equation and returns whether it has a solution, would be easy to solve with a really limited subset of the halting problem.

You might also try to find limited subsets of the recursive functions for which you can solve the halting problem.

Thomas Andrews
  • 177,126
0

Are there any proofs of the undecidability of the halting problem that directly explore why it's impossible for a program to decide what another program will do?

I think this may be based on a misconception about the "umbrella" of contradiction extended by the halting problem.

The contradiction is resolved by the statement "there is no universal algorithm," but consider absurdly that this would imply that there could exist an algorithm which decides halting for all but a single problem. We all know this is not the case, as is it clear from the problem that it extends further, but I haven't seen this precisely characterized anywhere, so I'll do it here.

Stronger Conclusion for Halting Problem

For any proposed halting decider $ H $, there exists a pathological subset $P_H $ of Turing machine and input combinations such that $H $ cannot correctly decide the halting problem for any $ (M, x)$ in $ P_H $. Specifically, within this subset, the machine $ M $ simulates $ H $, ensuring a contradiction or negation of $ H $'s decision.

In symbolic terms: $$ \forall H \exists P_H \subseteq \{(M, x)\} : \forall (M, x) \in P_H, H(M, x) \neq M(x) $$

Where $ P_H$ is defined as: $$ P_H = \{ (M, x) \mid (M \text{ simulates } H) \land (H(M, x) \neq M(x)) \} $$

This is the full extent of the contradiction: it doesn't actually say anything about the algorithm's "understanding," only the limitations of what the understanding can accomplish and, counterintuitively, there would be no contradiction in the algorithm being "smart enough" to recognize such an unsolvable problem, as it doesn't actually afford it a solution.

When viewed in this way, it should be clear that extending the problem to include a "broader" idea of why these are unsolvable is not supported by the conclusion itself, since the why is plainly stated, and limited in scope: there is a pathological subset for any given solver.

If you want an example that may characterize this well for class:

Assume you are deterministic. AI has taken over the world, but has offered you a challenge by which you can save humanity: you must beat it at a guessing game.

The premise is simple, you may place either a 1 or a 0 into a sealed envelope. The computer will do the same. If they do not match, the computer wins (you decide the problem incorrectly), if you do not answer, the computer wins (since no decision is made), and if you answer correctly, you win (you solve the halting problem).

Now, you are given access to the full source code of the supercomputer before the game by a human hacker. Looking into the code, you immediately realize your own mind, which is deterministic, is entirely represented there, not as it is right now, but as it will be upon your guess. You see, the supercomputer has actually predicted all local events as everything is deterministic, and knows exactly what you will do, including looking at the source code. As you read it, you can literally observe the logic that the machine will use regarding your reading it, but of course, there is logic based upon you knowing it knows, and so on and so forth.

Now, you might think "aha, now I can solve the problem! I can change what I would do!" but if you look carefully, you'll see this is not the case. This is the halting problem, in essence: you can be inside of it, understand it entirely, be an extraordinarily adaptable algorithm. However, if you are "captured" by another machine, it doesn't matter, since any change you make is represented by definition in the pathological machine's reasoning, and ties go to the pathological machine.

Daniel Stilman
  • 1