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:

GeneralHaltingProblem GeneralHaltingProblemProblem GeneralHaltingProblemProblemProblem HaltingEquivalent HaltingTheorem PatternHaltingProblem WhatDoesHaltingMean PatternHaltingProblem PenroseCannotConsistentlyAssert UnsolvableSoftwareDevelopmentProblems

This page is being reconstructed. Refactoring of a dozen or so pages in process -- DonaldNoyes

FixYourWiki: HaltingProblemDiscussions