Free Faster access than browser!

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

67 relations: Abstract machine, Alan Turing, Algorithm, Algorithmic information theory, Axiom of choice, Axiomatic system, Berry paradox, Collatz conjecture, Complex plane, Computability theory, Computable function, Computational complexity theory, Computer program, Consistency, Continuum hypothesis, Countable set, Decidability (logic), Decision problem, Diophantine equation, Entscheidungsproblem, Fermat's Last Theorem, First-order logic, Formal language, Formal system, Gödel numbering, Gödel's incompleteness theorems, Goodstein's theorem, Gregory Chaitin, Group (mathematics), Group theory, Halting problem, Hilbert's tenth problem, Independence (mathematical logic), Integer, Iteration, John Horton Conway, Kolmogorov complexity, Kruskal's tree theorem, Liar paradox, Logic, Mathematical proof, Max Dehn, Natural number, Paris–Harrington theorem, Paul Cohen, Philosophy of mathematics, Polynomial, Proceedings of the USSR Academy of Sciences, Proof of impossibility, Ramsey theory, ... Expand index (17 more) »

## Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.

## Alan Turing

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

## Algorithm

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

## Algorithmic information theory

Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information.

## Axiom of choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that the Cartesian product of a collection of non-empty sets is non-empty.

## Axiomatic system

In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems.

The Berry paradox is a self-referential paradox arising from an expression like "The smallest positive integer not definable in under sixty letters" (note that this defining phrase has fifty-seven letters).

## Collatz conjecture

The Collatz conjecture is a conjecture in mathematics that concerns a sequence defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term.

## Complex plane

In mathematics, the complex plane or z-plane is a geometric representation of the complex numbers established by the real axis and the perpendicular imaginary axis.

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

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

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

## Consistency

In classical deductive logic, a consistent theory is one that does not contain a contradiction.

## Continuum hypothesis

In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets.

## Countable set

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

## Decidability (logic)

In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas, or, more precisely, an algorithm that can and will return a boolean true or false value that is correct (instead of looping indefinitely, crashing, returning "don't know" or returning a wrong answer).

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

## Diophantine equation

In mathematics, a Diophantine equation is a polynomial equation, usually in two or more unknowns, such that only the integer solutions are sought or studied (an integer solution is a solution such that all the unknowns take integer values).

## Entscheidungsproblem

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

## Fermat's Last Theorem

In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers,, and satisfy the equation for any integer value of greater than 2.

## First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

## Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

## Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

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

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

## Goodstein's theorem

In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0.

## Gregory Chaitin

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

## Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set of elements equipped with an operation that combines any two elements to form a third element and that satisfies four conditions called the group axioms, namely closure, associativity, identity and invertibility.

## Group theory

In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.

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

## Hilbert's tenth problem

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900.

## Independence (mathematical logic)

In mathematical logic, independence refers to the unprovability of a sentence from other sentences.

## Integer

An integer (from the Latin ''integer'' meaning "whole")Integer&#x2009;'s first literal meaning in Latin is "untouched", from in ("not") plus tangere ("to touch").

## Iteration

Iteration is the act of repeating a process, to generate a (possibly unbounded) sequence of outcomes, with the aim of approaching a desired goal, target or result.

## John Horton Conway

John Horton Conway FRS (born 26 December 1937) is an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory.

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

## Kruskal's tree theorem

In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.

In philosophy and logic, the classical liar paradox or liar's paradox is the statement of a liar who states that he or she is lying: for instance, declaring that "I am lying" or "everything I say is false".

## Logic

Logic (from the logikḗ), originally meaning "the word" or "what is spoken", but coming to mean "thought" or "reason", is a subject concerned with the most general laws of truth, and is now generally held to consist of the systematic study of the form of valid inference.

## Mathematical proof

In mathematics, a proof is an inferential argument for a mathematical statement.

## Max Dehn

Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German-born American mathematician and student of David Hilbert.

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

## Paris–Harrington theorem

In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic.

## Paul Cohen

Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician.

## Philosophy of mathematics

The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics, and purports to provide a viewpoint of the nature and methodology of mathematics, and to understand the place of mathematics in people's lives.

## Polynomial

In mathematics, a polynomial is an expression consisting of variables (also called indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables.

## Proceedings of the USSR Academy of Sciences

The Proceedings of the USSR Academy of Sciences (Доклады Академии Наук СССР, Doklady Akademii Nauk SSSR (DAN SSSR), Comptes Rendus de l'Académie des Sciences de l'URSS) was a Soviet journal that was dedicated to publishing original, academic research papers in physics, mathematics, chemistry, geology, and biology.

## Proof of impossibility

A proof of impossibility, also known as negative proof, proof of an impossibility theorem, or negative result, is a proof demonstrating that a particular problem cannot be solved, or cannot be solved in general.

## Ramsey theory

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear.

## Ramsey's theorem

In combinatorial mathematics, Ramsey's theorem states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph.

## Recursive set

In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set.

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

## Rice's theorem

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

## Second-order arithmetic

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.

## Set theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.

## Soundness

In mathematical logic, a logical system has the soundness property if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system.

## String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

## Topology

In mathematics, topology (from the Greek τόπος, place, and λόγος, study) is concerned with the properties of space that are preserved under continuous deformations, such as stretching, crumpling and bending, but not tearing or gluing.

## Truth value

In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.

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

## Uncountable set

In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable.

In group theory, a branch of abstract algebra, the Whitehead problem is the following question: Shelah (1974) proved that Whitehead's problem is undecidable within standard ZFC set theory.

## Wicked problem

A wicked problem is a problem that is difficult or impossible to solve because of incomplete, contradictory, and changing requirements that are often difficult to recognize.

## Word problem for groups

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element.

## Yuri Matiyasevich

Yuri Vladimirovich Matiyasevich, (Ю́рий Влади́мирович Матиясе́вич; born March 2, 1947, in Leningrad) is a Russian mathematician and computer scientist.

## Zermelo–Fraenkel set theory

In mathematics, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox.

## References

Hey! We are on Facebook now! »