Undecidable Problem - The Undecidable Problem in Computability Theory

The Undecidable Problem in Computability Theory

In computability theory, the halting problem is a decision problem which can be stated as follows:

Given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.

Alan Turing proved in 1936 that a general algorithm running on a Turing machine that solves the halting problem for all possible program-input pairs necessarily cannot exist. Hence, the halting problem is undecidable for Turing machines.

Read more about this topic:  Undecidable Problem

Famous quotes containing the words problem and/or theory:

    “War is not a life: it is a situation,
    One which may neither be ignored nor accepted,
    A problem to be met with ambush and stratagem,
    Enveloped or scattered.”
    —T.S. (Thomas Stearns)

    “Psychotherapy—The theory that the patient will probably get well anyway, and is certainly a damned ijjit.”
    —H.L. (Henry Lewis)