Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS
 create new user name: pass: forget your password?
 sections EncyclopædiaPapersBooksExpositionsmeta Requests (170)Orphanage Unclass'd Unproven (415)Corrections (64)Classificationtalkback PollsForumsFeedbackBug Reportsdownloads SnapshotsPM Bookinformation NewsDocsWikiChangeLogTODO ListLegaleseAbout
 halting problem (Theorem)
 The halting problem is to determine, given a particular input to a particular computer program, whether the program will terminate after a finite number of steps. The consequences of a solution to the halting problem are far-reaching. Consider some predicate regarding natural numbers; suppose we conjecture that holds for all . (Goldbach's conjecture, for example, takes this form.) We can write a program that will count up through the natural numbers and terminate upon finding some such that is false; if the conjecture holds in general, then our program will never terminate. Then, without running the program, we could pass it along to a halting program to prove or disprove the conjecture. In 1936, Alan Turing proved that the halting problem is undecideable; the argument is presented here informally. Consider a hypothetical program that decides the halting the problem: Algorithm HALT(P, I) Input: A computer program and some input for Output: True if halts on and false otherwise The implementation of the algorithm, as it turns out, is irrelevant. Now consider another program: Algorithm BREAK(x) Input: Code Output: begin end If our halting solution determines that Break(Break) halts, then it will immediately enter an infinite loop; otherwise, Break will return immediately. We must conclude that the Halt program does not decide the halting problem. So for any attempted solution to the halting problem, we can find some input which breaks that solution.

"halting problem" is owned by rspuzio. [ full author list (3) | owner history (2) ]
(view preamble)

 View style: HTML with imagespage imagesTeX source

Cross-references: infinite, decides, argument, running, Goldbach's conjecture, conjecture, natural numbers, solution, finite

This is version 8 of halting problem, born on 2002-01-30, modified 2006-04-28.
Object id is 1622, canonical name is HaltingProblem.
Accessed 3853 times total.

Classification:
 AMS MSC: 03D75 (Mathematical logic and foundations :: Computability and recursion theory :: Abstract and axiomatic computability and recursion theory)

 Pending Errata and Addenda
 None.[ View all 5 ]
 Discussion
 Style: FlatThreaded Expand: allnone123456789 Order: Oldest FirstNewest first forum policy
 Self reference by AxelBoldt on 2002-04-01 22:54:34
 I think the proof glosses over the crucial part: How can Break refer to itself within Break's definition?You need to use Goedel's trick somehow: first construct an algorithm B that stops if and only if its argument, interpreted as an algorithm, won't stop on its own description, and then feed the description of B to B itself.Akin to the barber (B) who shaves everybody who doesn't shave himself. Ask whether B shaves B and it blows up.
[ reply | up ]
 Decidability by Logan on 2002-02-28 00:26:45
 I love decidability proofs. This sentence is false.
[ reply | up ]

 Interact rate | post | correct | update request | prove | add result | add corollary | add example | add (any)