Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Halting problem

Index 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, ..., John Hopcroft, Julia Robinson, Kolmogorov complexity, Kurt Gödel, Lambda calculus, Linear bounded automaton, London Mathematical Society, Markov algorithm, Martin Davis, Marvin Minsky, MISRA C, Natural density, Natural number, Normal number, NP-completeness, Numeral system, Oracle machine, Oxford University Press, P versus NP problem, Partial function, Peano axioms, Physical change, Post–Turing machine, Probability, Programming language, Proof by contradiction, Proposition, Pseudocode, Real-time computing, Recursively enumerable set, Reduction (complexity), Reduction (recursion theory), Register machine, Rice's theorem, Roger Penrose, Rule of least power, Simon & Schuster, SPARK (programming language), Stephen Cole Kleene, Taylor Booth, Termination analysis, Transcendental number, Turing completeness, Turing degree, Turing machine, Undecidable problem, Worst-case execution time. Expand index (47 more) »

"Hello, World!" program

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

New!!: Halting problem and "Hello, World!" program · See more »

Admissible numbering

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.

New!!: Halting problem and Admissible numbering · See more »

Alan Turing

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

New!!: Halting problem and Alan Turing · See more »

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.

New!!: Halting problem and Alan Turing: The Enigma · See more »

Alfred North Whitehead

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

New!!: Halting problem and Alfred North Whitehead · See more »


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

New!!: Halting problem and Algorithm · See more »

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.

New!!: Halting problem and Alonzo Church · See more »


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.

New!!: Halting problem and Alphabet · See more »

Andrew Hodges

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

New!!: Halting problem and Andrew Hodges · See more »

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.

New!!: Halting problem and Arithmetical hierarchy · See more »

Bertrand Russell

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

New!!: Halting problem and Bertrand Russell · See more »

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.

New!!: Halting problem and Busy beaver · See more »

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.

New!!: Halting problem and Cantor's diagonal argument · See more »

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.

New!!: Halting problem and Chaitin's constant · See more »

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.

New!!: Halting problem and Character (computing) · See more »

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.

New!!: Halting problem and Church–Turing thesis · See more »

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.

New!!: Halting problem and Computability theory · See more »

Computable function

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

New!!: Halting problem and Computable function · See more »

Computable number

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

New!!: Halting problem and Computable number · See more »


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

New!!: Halting problem and Computation · See more »

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.

New!!: Halting problem and Computer program · See more »

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.

New!!: Halting problem and Computer scientist · See more »

Constance Reid

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

New!!: Halting problem and Constance Reid · See more »


In computer science, Coq is an interactive theorem prover.

New!!: Halting problem and Coq · See more »

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.

New!!: Halting problem and Correctness (computer science) · See more »

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.

New!!: Halting problem and Data type · See more »

David Hilbert

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

New!!: Halting problem and David Hilbert · See more »

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.

New!!: Halting problem and Decision problem · See more »

Definable real number

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

New!!: Halting problem and Definable real number · See more »

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.

New!!: Halting problem and Effective method · See more »

Emil Leon Post

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

New!!: Halting problem and Emil Leon Post · See more »


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

New!!: Halting problem and Entscheidungsproblem · See more »


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

New!!: Halting problem and Enumeration · See more »

Ernest Nagel

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

New!!: Halting problem and Ernest Nagel · See more »

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.

New!!: Halting problem and Event loop · See more »

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.

New!!: Halting problem and Formalism (philosophy of mathematics) · See more »

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.

New!!: Halting problem and Gödel's incompleteness theorems · See more »

Gerhard Gentzen

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

New!!: Halting problem and Gerhard Gentzen · See more »

Gregory Chaitin

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

New!!: Halting problem and Gregory Chaitin · See more »

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.

New!!: Halting problem and Heuristic (computer science) · See more »

Hilbert's problems

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

New!!: Halting problem and Hilbert's problems · See more »

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.

New!!: Halting problem and Human brain · See more »


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

New!!: Halting problem and Hypercomputation · See more »

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.

New!!: Halting problem and Infinite loop · See more »

International Congress of Mathematicians

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

New!!: Halting problem and International Congress of Mathematicians · See more »

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.

New!!: Halting problem and Interpreter (computing) · See more »

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.

New!!: Halting problem and J. Barkley Rosser · See more »

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.

New!!: Halting problem and Jack Copeland · See more »

James R. Newman

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

New!!: Halting problem and James R. Newman · See more »

Jeffrey Ullman

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

New!!: Halting problem and Jeffrey Ullman · See more »

John Hopcroft

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

New!!: Halting problem and John Hopcroft · See more »

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.

New!!: Halting problem and Julia Robinson · See more »

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.

New!!: Halting problem and Kolmogorov complexity · See more »

Kurt Gödel

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

New!!: Halting problem and Kurt Gödel · See more »

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.

New!!: Halting problem and Lambda calculus · See more »

Linear bounded automaton

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

New!!: Halting problem and Linear bounded automaton · See more »

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)).

New!!: Halting problem and London Mathematical Society · See more »

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.

New!!: Halting problem and Markov algorithm · See more »

Martin Davis

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

New!!: Halting problem and Martin Davis · See more »

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.

New!!: Halting problem and Marvin Minsky · See more »


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

New!!: Halting problem and MISRA C · See more »

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.

New!!: Halting problem and Natural density · See more »

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").

New!!: Halting problem and Natural number · See more »

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.

New!!: Halting problem and Normal number · See more »


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

New!!: Halting problem and NP-completeness · See more »

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.

New!!: Halting problem and Numeral system · See more »

Oracle machine

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

New!!: Halting problem and Oracle machine · See more »

Oxford University Press

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

New!!: Halting problem and Oxford University Press · See more »

P versus NP problem

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

New!!: Halting problem and P versus NP problem · See more »

Partial function

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

New!!: Halting problem and Partial function · See more »

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.

New!!: Halting problem and Peano axioms · See more »

Physical change

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

New!!: Halting problem and Physical change · See more »

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.

New!!: Halting problem and Post–Turing machine · See more »


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

New!!: Halting problem and Probability · See more »

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.

New!!: Halting problem and Programming language · See more »

Proof by contradiction

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.

New!!: Halting problem and Proof by contradiction · See more »


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

New!!: Halting problem and Proposition · See more »


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

New!!: Halting problem and Pseudocode · See more »

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.

New!!: Halting problem and Real-time computing · See more »

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.

New!!: Halting problem and Recursively enumerable set · See more »

Reduction (complexity)

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

New!!: Halting problem and Reduction (complexity) · See more »

Reduction (recursion theory)

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

New!!: Halting problem and Reduction (recursion theory) · See more »

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.

New!!: Halting problem and Register machine · See more »

Rice's theorem

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

New!!: Halting problem and Rice's theorem · See more »

Roger Penrose

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

New!!: Halting problem and Roger Penrose · See more »

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".

New!!: Halting problem and Rule of least power · See more »

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.

New!!: Halting problem and Simon & Schuster · See more »

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.

New!!: Halting problem and SPARK (programming language) · See more »

Stephen Cole Kleene

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

New!!: Halting problem and Stephen Cole Kleene · See more »

Taylor Booth

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

New!!: Halting problem and Taylor Booth · See more »

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.

New!!: Halting problem and Termination analysis · See more »

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.

New!!: Halting problem and Transcendental number · See more »

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.

New!!: Halting problem and Turing completeness · See more »

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.

New!!: Halting problem and Turing degree · See more »

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.

New!!: Halting problem and Turing machine · See more »

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.

New!!: Halting problem and Undecidable problem · See more »

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.

New!!: Halting problem and Worst-case execution time · See more »

Redirects here:

Determining whether a program is going to run forever, Halt problem, Halting Problem, Halting Theorem, Halting predicate, The halting problem, Turing's halting problem, Turing's halting theorem.


[1] https://en.wikipedia.org/wiki/Halting_problem

Hey! We are on Facebook now! »