Communication
Install
Faster access than browser!

# Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever. [1]

97 relations: "Hello, World!" program, Admissible numbering, Alan Turing, Alan Turing: The Enigma, Alfred North Whitehead, Algorithm, Alonzo Church, Alphabet, Andrew Hodges, Arithmetical hierarchy, Bertrand Russell, Busy beaver, Cantor's diagonal argument, Chaitin's constant, Character (computing), Church–Turing thesis, Computability theory, Computable function, Computable number, Computation, Computer program, Computer scientist, Constance Reid, Coq, Correctness (computer science), Data type, David Hilbert, Decision problem, Definable real number, Effective method, Emil Leon Post, Entscheidungsproblem, Enumeration, Ernest Nagel, Event loop, Formalism (philosophy of mathematics), Gödel's incompleteness theorems, Gerhard Gentzen, Gregory Chaitin, Heuristic (computer science), Hilbert's problems, Human brain, Hypercomputation, Infinite loop, International Congress of Mathematicians, Interpreter (computing), J. Barkley Rosser, Jack Copeland, James R. Newman, Jeffrey Ullman, ... Expand index (47 more) »

## "Hello, World!" program

A "Hello, World!" program is a computer program that outputs or displays "Hello, World!" to a user.

In computability theory, admissible numberings are enumerations (numberings) of the set of partial computable functions that can be converted to and from the standard numbering.

## Alan Turing

Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.

## Alan Turing: The Enigma

Alan Turing: The Enigma (1983) is a biography of the British mathematician, codebreaker, and early computer scientist, Alan Turing (1912–1954) by Andrew Hodges.

Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher.

## Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

## Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science.

## Alphabet

An alphabet is a standard set of letters (basic written symbols or graphemes) that is used to write one or more languages based upon the general principle that the letters represent phonemes (basic significant sounds) of the spoken language.

## Andrew Hodges

Andrew Hodges (born 1949) is a British mathematician and author.

## Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them.

## Bertrand Russell

Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 &ndash; 2 February 1970) was a British philosopher, logician, mathematician, historian, writer, social critic, political activist, and Nobel laureate.

## Busy beaver

The busy beaver game consists of designing a halting, binary-alphabet Turing machine which writes the most 1s on the tape, using only a limited set of states.

## Cantor's diagonal argument

In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.

## Chaitin's constant

In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt.

## Character (computing)

In computer and machine-based telecommunications terminology, a character is a unit of information that roughly corresponds to a grapheme, grapheme-like unit, or symbol, such as in an alphabet or syllabary in the written form of a natural language.

## Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions.

## Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

## Computable function

Computable functions are the basic objects of study in computability theory.

## Computable number

In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm.

## Computation

Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.

## Computer program

A computer program is a collection of instructions for performing a specific task that is designed to solve a specific class of problems.

## Computer scientist

A computer scientist is a person who has acquired the knowledge of computer science, the study of the theoretical foundations of information and computation and their application.

## Constance Reid

Constance Bowman Reid (January 3, 1918 &ndash; October 14, 2010) was the author of several biographies of mathematicians and popular books about mathematics.

## Coq

In computer science, Coq is an interactive theorem prover.

## Correctness (computer science)

In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.

## Data type

In computer science and computer programming, a data type or simply type is a classification of data which tells the compiler or interpreter how the programmer intends to use the data.

## David Hilbert

David Hilbert (23 January 1862 – 14 February 1943) was a German mathematician.

## Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

## Definable real number

Informally, a definable real number is a real number that can be uniquely specified by its description.

## Effective method

In logic, mathematics and computer science, especially metalogic and computability theory, an effective methodHunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971 or effective procedure is a procedure for solving a problem from a specific class.

## Emil Leon Post

Emil Leon Post (February 11, 1897 – April 21, 1954) was an American mathematician and logician.

## Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.

## Enumeration

An enumeration is a complete, ordered listing of all the items in a collection.

## Ernest Nagel

Ernest Nagel (November 16, 1901 – September 20, 1985) was an American philosopher of science.

## Event loop

In computer science, the event loop, message dispatcher, message loop, message pump, or run loop is a programming construct that waits for and dispatches events or messages in a program.

## Formalism (philosophy of mathematics)

In foundations of mathematics, philosophy of mathematics, and philosophy of logic, formalism is a theory that holds that statements of mathematics and logic can be considered to be statements about the consequences of certain string manipulation rules.

## Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.

## Gerhard Gentzen

Gerhard Karl Erich Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician.

## Gregory Chaitin

Gregory John Chaitin (born 15 November 1947) is an Argentine-American mathematician and computer scientist.

## Heuristic (computer science)

In computer science, artificial intelligence, and mathematical optimization, a heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution.

## Hilbert's problems

Hilbert's problems are twenty-three problems in mathematics published by German mathematician David Hilbert in 1900.

## Human brain

The human brain is the central organ of the human nervous system, and with the spinal cord makes up the central nervous system.

## Hypercomputation

Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing computable.

## Infinite loop

An infinite loop (or endless loop) is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over.

## International Congress of Mathematicians

The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics.

## Interpreter (computing)

In computer science, an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.

## J. Barkley Rosser

John Barkley Rosser Sr. (December 6, 1907 – September 5, 1989) was an American logician, a student of Alonzo Church, and known for his part in the Church–Rosser theorem, in lambda calculus.

## Jack Copeland

Brian Jack Copeland (born 1950) is Professor of Philosophy at the University of Canterbury, Christchurch, New Zealand, and author of books on the computing pioneer Alan Turing.

## James R. Newman

James Roy Newman (1907–1966) was an American mathematician and mathematical historian.

## Jeffrey Ullman

Jeffrey David "Jeff" Ullman (born November 22, 1942) is an American computer scientist and professor at Stanford University.

## John Hopcroft

John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist.

## Julia Robinson

Julia Hall Bowman Robinson (December 8, 1919 – July 30, 1985) was an American mathematician renowned for her contributions to the fields of computability theory and computational complexity theory–most notably in decision problems.

## Kolmogorov complexity

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output.

## Kurt Gödel

Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.

## Lambda calculus

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

## Linear bounded automaton

In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine.

## London Mathematical Society

The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS) and the Institute of Mathematics and its Applications (IMA)).

## Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols.

## Martin Davis

Martin David Davis (born March 8, 1928) is an American mathematician, known for his work on Hilbert's tenth problem.

## Marvin Minsky

Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, and author of several texts concerning AI and philosophy.

## MISRA C

MISRA C is a set of software development guidelines for the C programming language developed by MISRA (Motor Industry Software Reliability Association).

## Natural density

In number theory, natural density (or asymptotic density or arithmetic density) is one of the possibilities to measure how large a subset of the set of natural numbers is.

## Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

## Normal number

In mathematics, a normal number is a real number whose infinite sequence of digits in every positive integer base b is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b2 pairs of digits are equally likely with density b−2, all b3 triplets of digits equally likely with density b−3, etc.

## NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

## Numeral system

A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner.

## Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.

## Oxford University Press

Oxford University Press (OUP) is the largest university press in the world, and the second oldest after Cambridge University Press.

## P versus NP problem

The P versus NP problem is a major unsolved problem in computer science.

## Partial function

In mathematics, a partial function from X to Y (written as or) is a function, for some subset X ′ of X.

## Peano axioms

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano.

## Physical change

Physical changes are changes affecting the form of a chemical substance, but not its chemical composition.

## Post–Turing machine

A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below.

## Probability

Probability is the measure of the likelihood that an event will occur.

## Programming language

A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.

In logic, proof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition.

## Proposition

The term proposition has a broad use in contemporary analytic philosophy.

## Pseudocode

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

## Real-time computing

In computer science, real-time computing (RTC), or reactive computing describes hardware and software systems subject to a "real-time constraint", for example from event to system response.

## Recursively enumerable set

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if.

## Reduction (complexity)

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.

## Reduction (recursion theory)

In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied.

## Register machine

In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine.

## Rice's theorem

In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

## Roger Penrose

Sir Roger Penrose (born 8 August 1931) is an English mathematical physicist, mathematician and philosopher of science.

## Rule of least power

In programming, the rule of least power is a design principle that "suggests choosing the least powerful language suitable for a given purpose".

## Simon & Schuster

Simon & Schuster, Inc., a subsidiary of CBS Corporation, is an American publishing company founded in New York City in 1924 by Richard Simon and Max Schuster.

## SPARK (programming language)

SPARK is a formally defined computer programming language based on the Ada programming language, intended for the development of high integrity software used in systems where predictable and highly reliable operation is essential.

## Stephen Cole Kleene

Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.

## Taylor Booth

Taylor Lockwood Booth (September 22, 1933 &ndash; October 20, 1986) was a mathematician known for his work in automata theory.

## Termination analysis

In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate.

## Transcendental number

In mathematics, a transcendental number is a real or complex number that is not algebraic—that is, it is not a root of a nonzero polynomial equation with integer (or, equivalently, rational) coefficients.

## Turing completeness

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.

## Turing degree

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.

## Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

## Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

## Worst-case execution time

The worst-case execution time (WCET) of a computational task is the maximum length of time the task could take to execute on a specific hardware platform.

## References

Hey! We are on Facebook now! »