Halting Problem

One of the most interesting theoretical parts of ComputerScience is the study of what can (and cannot) be computed. For instance, take the question, "does this program complete?" I.e., will it not go into an infinite loop. How would you answer this question, given an arbitrary piece of code? You could try running it. But what if it takes a long time? How long are you willing to wait?

http://www.cprogramming.com/tutorial/computersciencetheory/halting.html

The HaltingProblem asks the question: "Given a program and its input, determine whether the program will complete or run forever."

AlanTuring proved in 1936 that there cannot exist a general algorithm for answering this question for any arbitrary program and input. Turing introduced the TuringMachine in this proof. The first link below relates this result to GoedelsIncompletenessTheorem for mathematical formal systems.

Links:

http://en.wikipedia.org/wiki/Halting_problem

The halting problem is no longer an interesting question. No one actually using computers asks whether a program is going to halt, because nowadays they have the Ctrl-C and other measures to stop the machine if there seems to be a problem. Otherwise, I challenge you to come up with anything other than a ToyProblem where there is a real issue. Please, don't delete my comment again, until you can cite a real issue in the field. See also the BusyBeaverProgram.

The halting problem isn't a question, even though it's phrased that way above. It actually leads to an important proof that certain types of algorithm cannot be implemented. These are not just ToyProblems, but real issues. For example, when your boss asks you to write a program to determine if anyone in the development team has written code that will get caught in an endless loop, the proof allows you to provide a reason why it can't be done. As for pressing Ctrl-C, sure, you can do that if you're at a console and have made a decision that a long-running program should be stopped. However, what if it's a background process? How does a monitoring program know whether the process is simply busy and will finish eventually, or actually caught in a loop? Based on the source code and input data, it can't know. In short, the HaltingProblem tells us that a certain category of what otherwise might be very useful, pragmatic monitoring programs or compile-time code checkers -- those that look at source code and input and determine whether they'll eventually produce output or not -- can't exist.

The proof does not tell you that the existence of an endless loop cannot be determined; rather, it tells you that there is no single Turing machine which can determine the existence of the endless loop for any arbitrary program. In fact, for any arbitrary program, there is a Turing machine which can determine whether it halts; such a machine need only be large enough to contain a directed graph of all possible states (a finite set, assuming your computer is a Turing machine, which I imagine it is, and your input is finite (or at least, it gets its input from one or more Turing machines)) of the system and check that graph for cycles. Granted, such a machine would be impossibly large for all but the simplest of programs, but the point is that for any one program, the halting question is answerable given sufficient resources. At any rate, the semantics of whatever programming language you use typically allow you to take a few shortcuts.

[No, its not always possible to construct a specific machine for another specific machine to determine if its halts. If it was possible, your proof program could be constructed automatically just by brute force. Such a brute force prover could verify your program as you write it. What if I write a program to compute pi and search for a certain string of digits somewhere within. Can I write a program to tell me if the first will halt? What if I have a program that accepts a stream of 'a' and halts when it receives a 'b' (failing on any other input). What if my pi search program generates an 'a' every time it computes a new digit and outputs a 'b' when it finds the sub string. It's output is fed into my a-or-b program. Can I write a program that tells me if my a-or-b program halts?]

Thank you, and furthermore, to the original commentor, your example is ridiculous, no boss ever asks "write a program to determine if code will get caught in an endless loop", they ask instead "write code without any bugs". See, we programmers, monkeys that we are, actually learned to write code so we can see progress. This is how programming culture evolved: to refine the ability to prevent the need to abort drastically or dump core.
It's entirely realistic for a boss to ask for a program that will predict how long another program will take to finish, for example, and it's the same problem. There are undoubtably an infinite number of equivalent, and realistic, problems that are essentially variations on the HaltingProblem.

Many problems can be shown to equivalent to the halting problem

http://www.cs.bris.ac.uk/history/teaching/algorithms/chapter5.html

I like the Security Problem "Given a security scheme for an operating system, test whether it can be broken, just by using normal commands"

-- NickKeighley

Sorry your comment was deleted. GrammarVandal spoofed your UserName cookie and thereby merged his edits with yours, so the SharkBot reverted the lot.

FixYourWiki: HaltingProblemDiscussions