Alan Turing: halting problem

Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

Alan Turing (1912-1954) developed the ideas that proved the limits of computing before the first programmable digital computer was built. Claude Shannon (1939) showed that one could built such a computer.
The halting problem (Turing, Turing machine, 1936) result: It is impossible to write a computer program that looks at another computer program (and its data) and determines whether that other computer program eventually halts.

The possible answers for a computation of an undecidable problem are yes (true), no (false), or maybe (wait forever). One may be able to go "outside the system" to determine a better answer.

An abstract (or physical) computer can be called a Turing Machine. A Turing complete programming language can compute any computable function.

[waiting for a program to stop, secure form submission, virus detection]

A consequence of this theorem is that there are undecidable problems. Here are some examples:

Viruses cannot be identified with certainty.
Operating systems need user approval to shut down processes that might be important.
A browser cannot determine of a submission will be done securely.

Possible answers for a computation of an undecidable problem are yes (true), no (false), or maybe (wait forever).