UNDECIDABILITY

Posted by Jennifer G. Santiago

1. A LANGUAGE THAT IS NOT RECURSIVE ENUMERABLE

In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-recognizable. It is known as a type-0 language in the Chomsky hierarchy of formal languages. The class of all recursively enumerable languages is called RE.

To prove this we will consider a language consisting a pair (M, w) where:

1. M, a Turing Machine with inputs set {0,1}

2. W a binary string consisting of 0’s and 1’s.

3. M accepts w.

We will make use of three things in this proof and those are

· Enumerated binary strings

· Coded Turing Machine

· Diagonal language

All regular, context-free, context-sensitive and recursive languages are recursively enumerable.

Recursively undecidable problems give examples of recursively enumerable sets that are not recursive. For example, convergence of phi_x(x) is known to be recursively undecidable, where phi_x denotes the Turing machine with Gödel number x. Hence the set of all x for which phi_x(x) is convergent is not recursive. However, this set is recursively enumerable because it is the range of f defined as follows:

 f(x)={x   if phi_x(x) is convergent; divergent   if phi_x(x) is divergent.
(1)

A set A is recursive iff both A and its complement are recursively enumerable. This provides an approach to constructing additional sets that are not recursively enumerable. In particular, the set of all Gödel numbers of total Turing machines is an example of a set which is not recursively enumerable.

The complements of recursively enumerable but not recursive sets are all not recursively enumerable, although complements of sets that are not recursively enumerable are not necessarily recursively enumerable. For instance, the complement of the set of all Gödel numbers of total Turing machines is not recursively enumerable.

One of fundamental properties of recursively enumerable sets is that they could be alternatively defined by domains as opposed to ranges. In particular, a set A is recursively enumerable iff A is the domain of a recursive function.

*a. Enumerating by binary string

We need to assign integers to all binary strings in order to make a relation of binary input with corresponding integer value. For example ε means integer 1, Binary 0 means integer 2, binary 1 means integer 3, binary 00 means integer 4 and binary 01 means integer 5 and so on. The strings should be enumerated, in the sense that these strings should be ordered by length and strings of equal length should be lexicographically ordered. We can refer ith strings as Wi.

*b. Codes for Turing Machine

The second important thing that we require in the process of providing a language not a recursively enumerated is binary codes for Turing Machine. After coding a TM by {0,1} we can represent a complete Turing Machine by a sequence of binary string. We can also represent many Turing Machines with the help of binary strings and to identification of the Turing Machine by M¡. The representation of Turing Machine can be M= (Q,{0,1}, Γ, d, q1, B, F) as binary string. To represent the TM by binary strings we first assign binary strings to9 integers of states, tape symbol and directions L and R. Following are the steps used to represent the TM using binary string:

1.) We will assume set of states Q has the states q1, q2,…qk for some k. The start state will always be the q1 and the accept state will be q2. The Turing Machine always halt after entering and accept state and therefore it requires only one accept state.


2.) The tape symbols are X₁, X₂,…Xm for some m. Input symbol X₁ can be represented by 0, X₂ will be by 1 and X₃ by B, the blank. Other tape symbols can be assigned to the remaining integers arbitrarily.


3.) The direction L is represented by D₁ and R can be represented by D₂. The language represented by this TM M can be equivalently represented as L(M)= Ld.


4.)After representation of state, input and directions by binary strings we can encode transition function δ. Suppose one transition rule is δ (q₁, Xі, Dm) where I, j, k, l and m represents integer. This transitions rule can be represented by a binary string.

*c. Diagonalization Language


As we know that a Turing Machine can be represented by binary string. Hence different Turing Machines can be represented by various binary strings. In other words the ith Turing Machine whose code is, the ith binary string. To represent various strings corresponding to various TMs we make use of two dimensional arrays ¡ X j. there are many integers that do not correspond to any TM. If not a valid Turing Machine code then we consider TM with one state and no transitions. That is, for these values of ¡, the Turing Machine is such a machine that immediately halts on any input (being one state machine). Thus L (Mi) = 0 if fails to be valid TM code.

Definition: The diagonalization language, denoted by Ld is a set of strings such that is not in L (M¡). Thus Ld consist of all the strings w such that w is not accepted by TM M whose code is w.

1.) Theorem: The diagonalization language Ld is not recursively enumerable language. In other words, there is no such Turing Machine which can accept Ld .


2. UNDECIDABLE PROBLEM THAT IS NOT RE

There are two distinct senses of the word "undecidable" in contemporary use. The first of these is the sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable function that correctly answers every question in the problem set. The connection between these two is that if a decision problem is undecidable (in the recursion theoretical sense) then there is no consistent, effective formal system which proves for every question A in the problem either "the answer to A is yes" or "the answer to A is no".

Because of the two meanings of the word undecidable, the term independent is sometimes used instead of undecidable for the "neither provable nor refutable" sense. The usage of "independent" is also ambiguous, however. Some use it to mean just "not provable", leaving open whether an independent statement might be refuted.

Undecidability of a statement in a particular deductive system does not, in and of itself, address the question of whether the truth value of the statement is well-defined, or whether it can be determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point among various philosophical schools.

One of the first problems suspected to be undecidable, in the second sense of the term, was the word problem for groups, first posed by Max Dehn in 1911, which asks if there is a finitely presented group for which no algorithm exists to determine whether two words are equivalent. This was shown to be the case in 1952.

The combined work of Gödel and Paul Cohen has given two concrete examples of undecidable statements (in the first sense of the term): The continuum hypothesis can neither be proved nor refuted in ZFC (the standard axiomatization of set theory), and the axiom of choice can neither be proved nor refuted in ZF (which is all the ZFC axioms except the axiom of choice). These results do not require the incompleteness theorem. Gödel proved in 1940 that neither of these statements could be disproved in ZF or ZFC set theory. In the 1960s, Cohen proved that neither is provable from ZF, and the continuum hypothesis cannot be proven from ZFC.

In 1970, Soviet mathematician Yuri Matiyasevich showed that Hilbert's Tenth Problem, posed in 1900 as a challenge to the next century of mathematicians, cannot be solved. Hilbert's challenge sought an algorithm which finds all solutions of a Diophantine equation. A Diophantine equation is a more general case of Fermat's Last Theorem; we seek the integer roots of a polynomial in any number of variables with integer coefficients. Since we have only one equation but n variables, infinitely many solutions exist (and are easy to find) in the complex plane; the problem becomes difficult (impossible) by constraining solutions to integer values only. Matiyasevich showed this problem to be unsolvable by mapping a Diophantine equation to a recursively enumerable set and invoking Gödel's Incompleteness Theorem.


3. UNDECIDABLE PROBLEM ABOUT TURING MACHINE

In 1936, Alan Turing proved that the halting problem—the question of whether or not a Turing machine halts on a given program—is undecidable, in the second sense of the term. This result was later generalized to Rice's theorem.

In 1973, the Whitehead problem in group theory was shown to be undecidable, in the first sense of the term, in standard set theory.

In 1977, Paris and Harrington proved that the Paris-Harrington principle, a version of the Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the Peano axioms but can be proven to be true in the larger system of second-order arithmetic.

Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism.

Goodstein's theorem is a statement about the Ramsey theory of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.

Gregory Chaitin produced undecidable statements in algorithmic information theory and proved another incompleteness theorem in that setting. Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper bound c such that no specific number can be proven in that theory to have Kolmogorov complexity greater than c. While Gödel's theorem is related to the liar paradox, Chaitin's result is related to Berry's paradox.

Douglas Hofstadter gives a notable alternative proof of incompleteness, inspired by Gödel, in his book Gödel, Escher, Bach.

In 2006, researchers Kurtz and Simon, building on earlier work by J.H. Conway in the 1970s, proved that a natural generalization of the Collatz problem is undecidable.



4. POST CORRESPONDENCE PROBLEMS

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

The input of the problem consists of two finite lists \alpha_{1}, \ldots, \alpha_{N} and \beta_{1}, \ldots, \beta_{N} of words over some alphabet A having at least two symbols. A solution to this problem is a sequence of indices (i_k)_{1 \le k \le K} with K \ge 1 and  1 \le i_k \le N for all k, such that

\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.

The decision problem then is to decide whether such a solution exists or not.

Many variants of PCP have been considered. One reason is that, when one tries to prove undecidability of some new problem by reducing from PCP, it often happens that the first reduction one finds is not from PCP itself but from an apparently weaker version.

  • The condition that the alphabet A have at least two symbols is required since the problem is decidable if A has only one symbol.
  • A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 7. It is unknown whether the problem is decidable for 3 ≤ n ≤ 6.
  • The circular Post correspondence problem asks whether indexes i1,i2,... can be found such that \alpha_{i_1} \cdots \alpha_{i_k} and \beta_{i_1} \cdots \beta_{i_k} are conjugate words, i.e., they are equal modulo rotation. This variant is undecidable.
  • One of the most important variants of PCP is the bounded Post correspondence problem, which asks if we can find a match using no more than k tiles, including repeated tiles. A brute force search solves the problem in time O(2k), but this may be difficult to improve upon, since the problem is NP-complete. Unlike some NP-complete problems like the boolean satisfiability problem, a small variation of the bounded problem was also shown to be complete for RNP, which means that it remains hard even if the inputs are chosen at random (it is hard on average over uniformly distributed inputs)
  • Another variant of PCP is called the marked Post Correspondence Problem, in which each ui must begin with a different symbol, and each vi must also begin with a different symbol. Halava, Hirvensalo, and de Wolf showed that this variation is decidable in exponential time. Moreover, they showed that if this requirement is slightly loosened so that only the two-character prefixes need to differ (the so-called 2-marked Post Correspondence Problem), the problem becomes undecidable again.
  • The Post Embedding Problem is another variant where one looks for indexes i1,i2,...\alpha_{i_1} \cdots \alpha_{i_k} is a (scattered) subword of \beta_{i_1} \cdots \beta_{i_k}. This variant is easily decidable since, when some solutions exist, in particular a length-one solution exists. More interesting is the Regular Post Embedding Problem, a further variant where one looks for solutions that belong to a given regular language (submitted, e.g., under the form of a regular expression on the set {1,...,N}). The Regular Post Embedding Problem is still decidable but, because of the added regular constraint, it has a very high complexity that dominates every multiply-recursive function. such that