CS 231 AUTOMATA AND FORMAL LANGUAGES

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 is known to be recursively undecidable, where denotes the Turing machine with Gödel number . Hence the set of all for which is convergent is not recursive. However, this set is recursively enumerable because it is the range of defined as follows:

(1)

A set is recursive iff both 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 is recursively enumerable iff 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.

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 M¡ whose code is w¡, 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 w¡ not a valid Turing Machine code then we consider TM M¡ with one state and no transitions. That is, for these values of ¡, the Turing Machine M¡ is such a machine that immediately halts on any input (being one state machine). Thus L (Mi) = 0 if w¡ fails to be valid TM code.

Definition: The diagonalization language, denoted by Ld is a set of strings w¡ such that w¡ 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.

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.