Halting problem

related topics
{math, number, function}
{style, bgcolor, rowspan}
{system, computer, user}
{math, energy, light}
{god, call, give}

In computability theory, the halting problem is a decision problem which can be stated as follows: Given a description of a program, decide whether the program finishes running or continues to run, and will thereby run forever. This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines.

B. Jack Copeland (2004) attributes the actual term halting problem to Martin Davis.[1]

Contents

Formal statement

The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations of memory or time on the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input.

For example, in pseudocode, the program

does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program

halts very soon.

The halting problem is famous because it was one of the first problems proven algorithmically undecidable. This means there is no algorithm which can be applied to any arbitrary program and input to decide whether the program stops when run with that input.

Full article ▸

related documents
Fermat number
Lp space
Ackermann function
BCH code
Subset sum problem
Basis (linear algebra)
Fundamental theorem of algebra
Truth table
Dual space
Permutation
Euler's formula
Primitive recursive function
Uniform space
Continuous function
Convolution
Bessel function
Taylor series
Support vector machine
Probability theory
Multiplication algorithm
Hyperreal number
Fundamental group
Computable number
Multivariate normal distribution
Monte Carlo method
Dynamic programming
Stochastic process
Prime number theorem
Abelian group
Group action