Undecidable

Last updated

Undecidable may refer to:

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. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.

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

See also

Related Research Articles

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. An example of a decision problem is deciding whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable.

In mathematics and computer science, the Entscheidungsproblem is a challenge posed by David Hilbert in 1928. The problem asks for an algorithm that takes as input a statement of a first-order logic and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

Theory of computation subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory and languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

The word decidable may refer to:

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

Wang tile class of formal systems. They are modelled visually by equal-sized squares with a color on each edge which can be arranged side by side

Wang tiles, first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.

Emil Leon Post American logician

Emil Leon Post was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.

Reduction (complexity) the transformation of one computational problem to another, used to show that the second problem is as difficult as the first

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively determined. A theory in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership can exist for them.

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. Often proofs of impossibility have put to rest decades or centuries of work attempting to find a solution. To prove that something is impossible is usually much harder than the opposite task; it is necessary to develop a theory. Impossibility theorems are usually expressible as universal propositions in logic.

In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set. The problem is commonly encountered in abstract algebra, where given a presentation of an algebraic structure by generators and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups. Less formally, the word problem in an algebra is: given a set of identities E, and two expressions x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions? While answering this question may not seem hard, the remarkable result that emerges, in many important cases, is that the problem is undecidable.

Jarkko J. Kari is a Finnish mathematician and computer scientist, known for his contributions to the theory of Wang tiles and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku.

In mathematics, Richardson's theorem establishes a limit on the extent to which an algorithm can decide whether certain mathematical expressions are equal. It states that for a certain fairly natural class of expressions, it is undecidable whether a particular expression E satisfies the equation E = 0, and similarly undecidable whether the functions defined by expressions E and F are everywhere equal. It was proved in 1968 by computer scientist Daniel Richardson of the University of Bath.

In mathematics, the constant problem is the problem of deciding if a given expression is equal to zero.

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 or continue to run forever.

In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A formula is valid if all interpretations make the formula true. The opposites of these concepts are unsatisfiability and invalidity, that is, a formula is unsatisfiable if none of the interpretations make the formula true, and invalid if some such interpretation makes the formula false. These four concepts are related to each other in a manner exactly analogous to Aristotle's square of opposition.

Aperiodic set of prototiles

A set of prototiles is aperiodic if copies of the prototiles can be assembled to create tilings, such that all possible tessellation patterns are non-periodic. The aperiodicity referred to is a property of the particular set of prototiles; the various resulting tilings themselves are just non-periodic.

A first-order language of the real numbers is the set of all well-formed sentences of first-order logic that involve universal and existential quantifiers and logical combinations of equalities and inequalities of expressions over real variables. The corresponding first-order theory is the set of sentences that are actually true of the real numbers. There are several different such theories, with different expressive power, depending on the primitive operations that are allowed to be used in the expression. A fundamental question in the study of these theories is whether they are decidable: that is, is there an algorithm that can take a sentence as input and produce as output an answer "yes" or "no" to the question of whether the sentence is true in the theory.