Halting problem, the Glossary

Table of Contents

1. 102 relations: "Hello, World!" program, Admissible numbering, Alan Turing, Alfred North Whitehead, Algorithm, Alonzo Church, Alphabet, Arithmetical hierarchy, Bertrand Russell, Beta normal form, Brainfuck, Brouwer–Hilbert controversy, Busy beaver, Cantor's diagonal argument, Chaitin's constant, Character (computing), Christopher Strachey, Church–Turing thesis, Computability, Computability theory, Computable function, Computable number, Computably enumerable set, Computation, Computer program, Computer scientist, Coq (software), Correctness (computer science), Data type, David Hilbert, Decider (Turing machine), Definable real number, Definable set, Effective method, Emil Leon Post, Entscheidungsproblem, Enumeration, Ernest Nagel, Event loop, Formalism (philosophy of mathematics), Gödel numbering, Gödel's incompleteness theorems, General recursive function, Gerhard Gentzen, Gregory Chaitin, Heuristic (computer science), Hilbert's problems, Human brain, Hypercomputation, Infinite loop, ... Expand index (52 more) »

2. 1936 introductions
3. Undecidable problems

"Hello, World!" program

A "Hello, World!" program is generally a simple computer program which outputs (or displays) to the screen (often the console) a message similar to "Hello, World!" while ignoring any user input.

See Halting problem and "Hello, World!" program

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. Halting problem and admissible numbering are computability theory and theory of computation.

See Halting problem and Admissible numbering

Alan Turing

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

See Halting problem and Alan Turing

Alfred North Whitehead

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

See Halting problem and Alfred North Whitehead

Algorithm

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

See Halting problem and Algorithm

Alonzo Church

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

See Halting problem and Alonzo Church

Alphabet

An alphabet is a standard set of letters written to represent particular sounds in a spoken language.

See Halting problem and Alphabet

Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define them. Halting problem and arithmetical hierarchy are computability theory.

See Halting problem and Arithmetical hierarchy

Bertrand Russell

Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, logician, philosopher, and public intellectual.

See Halting problem and Bertrand Russell

Beta normal form

In the lambda calculus, a term is in beta normal form if no beta reduction is possible.

See Halting problem and Beta normal form

Brainfuck

Brainfuck is an esoteric programming language created in 1993 by Swiss physics student Urban Müller.

See Halting problem and Brainfuck

Brouwer–Hilbert controversy

The Brouwer–Hilbert controversy was a debate in twentieth-century mathematics over fundamental questions about the consistency of axioms and the role of semantics and syntax in mathematics.

See Halting problem and Brouwer–Hilbert controversy

Busy beaver

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps. Halting problem and busy beaver are computability theory and theory of computation.

See Halting problem and Busy beaver

Cantor's diagonal argument

Cantor's diagonal argument (among various similar namesthe diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof) is a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbersinformally, that there are sets which in some sense contain more elements than there are positive integers.

See Halting problem and Cantor's diagonal argument

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. Halting problem and Chaitin's constant are theory of computation.

See Halting problem and Chaitin's constant

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.

See Halting problem and Character (computing)

Christopher Strachey

Christopher S. Strachey (16 November 1916 – 18 May 1975) was a British computer scientist.

See Halting problem and Christopher Strachey

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 thesis about the nature of computable functions. Halting problem and Church–Turing thesis are computability theory and theory of computation.

See Halting problem and Church–Turing thesis

Computability

Computability is the ability to solve a problem in an effective manner. Halting problem and Computability are computability theory and theory of computation.

See Halting problem and Computability

Computability theory

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

See Halting problem and Computability theory

Computable function

Computable functions are the basic objects of study in computability theory. Halting problem and Computable function are computability theory and theory of computation.

See Halting problem and Computable function

Computable number

In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. Halting problem and computable number are computability theory and theory of computation.

See Halting problem and Computable number

Computably enumerable set

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if. Halting problem and computably enumerable set are computability theory and theory of computation.

See Halting problem and Computably enumerable set

Computation

A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Halting problem and computation are computability theory.

See Halting problem and Computation

Computer program

A computer program is a sequence or set of instructions in a programming language for a computer to execute.

See Halting problem and Computer program

Computer scientist

A computer scientist is a scholar who specializes in the academic study of computer science.

See Halting problem and Computer scientist

Coq (software)

Coq is an interactive theorem prover first released in 1989.

See Halting problem and Coq (software)

Correctness (computer science)

In theoretical computer science, an algorithm is correct with respect to a specification if it behaves as specified.

See Halting problem and Correctness (computer science)

Data type

In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these values as machine types.

See Halting problem and Data type

David Hilbert

David Hilbert (23 January 1862 – 14 February 1943) was a German mathematician and one of the most influential mathematicians of his time.

See Halting problem and David Hilbert

Decider (Turing machine)

In computability theory, a decider is a Turing machine that halts for every input.

See Halting problem and Decider (Turing machine)

Definable real number

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

See Halting problem and Definable real number

Definable set

In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements satisfy some formula in the first-order language of that structure.

See Halting problem and Definable set

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 by any intuitively 'effective' means from a specific class. Halting problem and effective method are computability theory and theory of computation.

See Halting problem and Effective method

Emil Leon Post

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

See Halting problem and Emil Leon Post

Entscheidungsproblem

In mathematics and computer science, the paren) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. It asks for an algorithm that considers an inputted statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in every structure. Halting problem and Entscheidungsproblem are computability theory, theory of computation and undecidable problems.

See Halting problem and Entscheidungsproblem

Enumeration

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

See Halting problem and Enumeration

Ernest Nagel

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

See Halting problem and Ernest Nagel

Event loop

In computer science, the event loop (also known as message dispatcher, message loop, message pump, or run loop) is a programming construct or design pattern that waits for and dispatches events or messages in a program.

See Halting problem and Event loop

Formalism (philosophy of mathematics)

In the philosophy of mathematics, formalism is the view that holds that statements of mathematics and logic can be considered to be statements about the consequences of the manipulation of strings (alphanumeric sequences of symbols, usually as equations) using established manipulation rules.

See Halting problem and Formalism (philosophy of mathematics)

Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. Halting problem and Gödel numbering are theory of computation.

See Halting problem and Gödel numbering

Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of in formal axiomatic theories.

See Halting problem and Gödel's incompleteness theorems

General recursive function

In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. Halting problem and general recursive function are computability theory and theory of computation.

See Halting problem and General recursive function

Gerhard Gentzen

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

See Halting problem and Gerhard Gentzen

Gregory Chaitin

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

See Halting problem and Gregory Chaitin

Heuristic (computer science)

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

See Halting problem and Heuristic (computer science)

Hilbert's problems

Hilbert's problems are 23 problems in mathematics published by German mathematician David Hilbert in 1900. Halting problem and Hilbert's problems are mathematical problems.

See Halting problem and Hilbert's problems

Human brain

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

See Halting problem and Human brain

Hypercomputation

Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. Halting problem and Hypercomputation are computability theory and theory of computation.

See Halting problem and Hypercomputation

Infinite loop

In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs, such as turning off power via a switch or pulling a plug.

See Halting problem and Infinite loop

International Congress of Mathematicians

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

See Halting problem and International Congress of Mathematicians

Interpreter (computing)

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

See Halting problem and Interpreter (computing)

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.

See Halting problem and J. Barkley Rosser

James R. Newman

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

See Halting problem and James R. Newman

Julia Robinson

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

See Halting problem and Julia Robinson

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 a shortest computer program (in a predetermined programming language) that produces the object as output. Halting problem and Kolmogorov complexity are computability theory.

See Halting problem and Kolmogorov complexity

Kurt Gödel

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

See Halting problem and Kurt Gödel

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. Halting problem and Lambda calculus are computability theory.

See Halting problem and Lambda calculus

Linear bounded automaton

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

See Halting problem and Linear bounded automaton

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. Halting problem and Markov algorithm are theory of computation.

See Halting problem and Markov algorithm

Martin Davis (mathematician)

Martin David Davis (March 8, 1928 – January 1, 2023) was an American mathematician and computer scientist who contributed to the fields of computability theory and mathematical logic.

See Halting problem and Martin Davis (mathematician)

Marvin Minsky

Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI).

See Halting problem and Marvin Minsky

MISRA C

MISRA C is a set of software development guidelines for the C programming language developed by The MISRA Consortium.

See Halting problem and MISRA C

Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. Halting problem and model of computation are computability theory.

See Halting problem and Model of computation

Natural density

In number theory, natural density, also referred to as asymptotic density or arithmetic density, is one method to measure how "large" a subset of the set of natural numbers is.

See Halting problem and Natural density

Natural number

In mathematics, the natural numbers are the numbers 0, 1, 2, 3, etc., possibly excluding 0.

See Halting problem and Natural number

Normal number

In mathematics, a real number is said to be simply normal in an integer base b if its infinite sequence of digits is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b.

See Halting problem and Normal number

Numeral system

A numeral system 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.

See Halting problem and Numeral system

Oracle machine

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

See Halting problem and Oracle machine

P versus NP problem

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

See Halting problem and P versus NP problem

Partial function

In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to.

See Halting problem and Partial function

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.

See Halting problem and Peano axioms

Physical change

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

See Halting problem and Physical change

Post–Turing machine

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

See Halting problem and Post–Turing machine

Primitive recursive function

In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed before entering the loop). Halting problem and primitive recursive function are computability theory and theory of computation.

See Halting problem and Primitive recursive function

Probability

Probability is the branch of mathematics concerning events and numerical descriptions of how likely they are to occur.

See Halting problem and Probability

Programming language

A programming language is a system of notation for writing computer programs.

See Halting problem and Programming language

Proof by contradiction

In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction.

See Halting problem and Proof by contradiction

Proposition

A proposition is a central concept in the philosophy of language, semantics, logic, and related fields, often characterized as the primary bearer of truth or falsity.

See Halting problem and Proposition

Pseudocode

In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actions and conditions.

See Halting problem and Pseudocode

RE (complexity)

In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Halting problem and RE (complexity) are undecidable problems.

See Halting problem and RE (complexity)

Real-time computing

Real-time computing (RTC) is the computer science term for hardware and software systems subject to a "real-time constraint", for example from event to system response.

See Halting problem and Real-time computing

Reduction (complexity)

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

See Halting problem and Reduction (complexity)

Reduction (computability theory)

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

See Halting problem and Reduction (computability theory)

Register machine

In mathematical logic and theoretical computer science, a register machine is a generic class of abstract machines, analogous to a Turing machine and thus Turing complete.

See Halting problem and Register machine

Rice's theorem

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

See Halting problem and Rice's theorem

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

See Halting problem and Rule of least power

Self-reference

Self-reference is a concept that involves referring to oneself or one's own attributes, characteristics, or actions. Halting problem and Self-reference are theory of computation.

See Halting problem and Self-reference

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.

See Halting problem and SPARK (programming language)

Stephen Cole Kleene

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

See Halting problem and Stephen Cole Kleene

Tag system

In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 1943 as a simple form of a Post canonical system.

See Halting problem and Tag system

Taylor Booth (mathematician)

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

See Halting problem and Taylor Booth (mathematician)

Termination analysis

In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for each input.

See Halting problem and Termination analysis

Transcendental number

In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial with integer (or, equivalently, rational) coefficients.

See Halting problem and Transcendental number

Turing completeness

In computability theory, a system of data-manipulation rules (such as a model of computation, 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 (devised by English mathematician and computer scientist Alan Turing). Halting problem and Turing completeness are theory of computation.

See Halting problem and Turing completeness

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. Halting problem and Turing degree are computability theory and theory of computation.

See Halting problem and Turing degree

Turing machine

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Halting problem and Turing machine are computability theory.

See Halting problem and Turing machine

Turing reduction

In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987).

See Halting problem and Turing reduction

Turing's proof

Turing's proof is a proof by Alan Turing, first published in November 1936 with the title "On Computable Numbers, with an Application to the Entscheidungsproblem". Halting problem and Turing's proof are theory of computation.

See Halting problem and Turing's proof

Undecidable problem

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

See Halting problem and Undecidable problem

Universal Turing machine

In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence, as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem".

See Halting problem and Universal Turing machine

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.

See Halting problem and Worst-case execution time

See also

1936 introductions

• Dvorak keyboard layout
• Fifth column
• Halting problem
• Hildebrand solubility parameter
• Merton thesis
• SSh-36
• Three seconds rule
• Universal Air Travel Plan

Undecidable problems

• ALL (complexity)
• Adian–Rabin theorem
• Constant problem
• Emptiness problem
• Entscheidungsproblem
• Group isomorphism problem
• Halting problem
• Hilbert's tenth problem
• List of undecidable problems
• Matrix mortality problem
• Mortality (computability theory)
• Post correspondence problem
• RE (complexity)
• Rice's theorem
• Richardson's theorem
• Scott–Curry theorem
• Simplicial complex recognition problem
• Spectral gap (physics)
• Trakhtenbrot's theorem
• Undecidable problem
• Wang tile
• Word problem for groups

References

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

Also known as Determining whether a program is going to run forever, Halt problem, Halting Theorem, Halting predicate, Halting set, Lossy Turing machine, The Halting Problem, Turing's halting problem, Turing's halting theorem.

, International Congress of Mathematicians, Interpreter (computing), J. Barkley Rosser, James R. Newman, Julia Robinson, Kolmogorov complexity, Kurt Gödel, Lambda calculus, Linear bounded automaton, Markov algorithm, Martin Davis (mathematician), Marvin Minsky, MISRA C, Model of computation, Natural density, Natural number, Normal number, Numeral system, Oracle machine, P versus NP problem, Partial function, Peano axioms, Physical change, Post–Turing machine, Primitive recursive function, Probability, Programming language, Proof by contradiction, Proposition, Pseudocode, RE (complexity), Real-time computing, Reduction (complexity), Reduction (computability theory), Register machine, Rice's theorem, Rule of least power, Self-reference, SPARK (programming language), Stephen Cole Kleene, Tag system, Taylor Booth (mathematician), Termination analysis, Transcendental number, Turing completeness, Turing degree, Turing machine, Turing reduction, Turing's proof, Undecidable problem, Universal Turing machine, Worst-case execution time.