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? 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:
Related:
 GeneralHaltingProblem
 GeneralHaltingProblemProblem
 GeneralHaltingProblemProblemProblem
 HaltingEquivalent
 HaltingTheorem
 PatternHaltingProblem
 WhatDoesHaltingMean
 PatternHaltingProblem 
 PenroseCannotConsistentlyAssert
 UnsolvableSoftwareDevelopmentProblems


FixYourWiki: HaltingProblemDiscussions

EditText of this page (last edited June 30, 2010)
FindPage by searching (or browse LikePages or take a VisualTour)