0 Replies - 5264 Views - Last Post: 16 January 2014 - 02:45 PM Rate Topic: -----

#1 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon

Reputation: 10194
  • View blog
  • Posts: 37,646
  • Joined: 27-December 08

Limits of Turing Machines

Posted 16 January 2014 - 02:45 PM

Limitations of Turing Machines

This tutorial will explore languages that Turing Machines can (and cannot) decide and accept. In essence, it takes the concepts from the last tutorials and begins to actually explore the limits of Turing Machines. Familiarity with Formal Languages is assumed, as described in Part 2.

Below is a typeset version of this tutorial:
Attached File  Turing_Machines3.pdf (131.98K)
Number of downloads: 59

Languages Turing Machines Can Decide
This section will introduce certain languages that Turing Machines can decide. Remember that in order for a language to be decidable, there must exist a Turing Machine that can determine correctly whether or not an arbitrary string is in the language.

Consider the first example, LRX = { R,w : R is a regular expression, and w = L® }. Remember that regular expressions are accepted by Finite State Automaton. Without loss of generality, let F be a non-deterministic FSA that accepts w. It is always possible to reduce a non-deterministic FSA to a deterministic FSA, F'. The transformation itself is not important in this section, but the result that follows is. That is, every regular language can be accepted by a deterministic finite state machine. Let T be a Turing Machine to simulate F'. Since FSA do not write anything, T will not write to the tape. Thus, T will generate L(F'). If L(F') = w, then T accepts R,w. Otherwise, T rejects R,w. Thus, the LRX is decidable.

The intuition behind the comparison of L(F') and w comes from using the symmetric difference set operation. That is, if L(F') - w = {}, and w - L(F') = {}, then L(F') = w. Regular languages also have an important property: A regular language L accepted by a FSA M is non-empty iff there exists a string in the language whose length is less than the number of states in M. Regular languages are also closed under intersection and complementation, so L(F') - w and w - L(F') are regular if and only if w and L(F') are regular. Since F' is a FSA, L(F') is regular. So if w is either non-regular or a language differing from L(F'), then the Turing Machine will reject the input R,w. Otherwise, it will accept the input string. Thus, there exists a Turing Machine to decide LRX.

The next two languages to be introduced are R = {p(M) : M is a DFA and L(M) = {} }, and C = {p(G) : G is a Context-Free Grammar and L(G) = {} }. Both of these languages are decidable. Let's first explore how these languages are decidable, then discuss their importance.

To begin, let RE be the set of Recursively Enumerable Languages. The Chomsky Hierarchy depicts a relationship between various sets of languages. In particular, it describes regular languages as a subset of context-free languages. In turn, context-free languages are a subset of context-sensitive languages. Finally, context-sensitive languages are a subset of RE.

It follows by this subset relationship that if C is decidable, then R is decidable, since R is a subset of C. Let's now explore why C is decidable. Remember that a CFG has Terminal Symbols, Non-Terminal Symbols, Rules, and a starting symbol S. The idea is similar to the construction of a Huffman Tree. That is, start by marking the terminal symbols. These are analogous to the leaf-nodes of a Huffman tree. The process is then to build the tree upwards. This is done by reviewing the non-terminals. If a given non-terminal has a rule which can be replaced by already marked symbols, that rule is marked and the symbols are replaced. If S can be reached, then L(G) is non-empty and the Turing Machine rejects the string. Otherwise, L(G) is empty and the input string is accepted.

Regular languages are generated by regular grammars, so a similar method of proof can be used to show that the language R is decidable. Regular languages are also generated by FSA. Thus, it is sufficient to execute a graph traversal on the graph representation of the FSA from the input string, p(M). If it is possible to reach an accepting halt state from the initial state of the FSA, then L(M) is non-empty, so the Turing Machine rejects p(M). Otherwise, p(M) is accepted. Thus, the language R is decidable.

The languages C and R are important in illustrating an important concept: solving a subset of a problem is not the same as solving a problem. Consider the language L = {p(M) : M is a Turing Machine and L(M) = {} }. The language L is undecdiable; however, Turing Machines are capable of deciding all regular languages. Turing Machines are also capable of accepting CFG. Thus, there is the relationship that R subset C subset L. Clearly, deciding L would have implications about deciding C; and C being undecidable would imply that L is undecidable. Remember that Languages are descriptions of problems.

Non-Turing Acceptable Language
This section will introduce a language that is not recursively enumerable. Let Ldiag = { wi : wi is not accepted by Mi }, where wi is the ith string in lexicographical order over the given alphabet, and Mi is the ith Turing Machine. Note that this languages has no constraints about wi with respect to Mj, for i != j.

Proof: Ldiag is not recursively enumerable.

This theorem is proven by contradiction. Suppose Ldiag is recursively enumerable. Then there exists a Turing Machine that accepts Ldiag. Let Mk be a Turing Machine to accept Ldiag. By definition of language acceptance, Mk accepts all strings in the language. Suppose wk is in Ldiag. Then Mk accepts wk, which contradicts the definition of the language Ldiag. Suppose wk is not in Ldiag. Then wk is accepted by Mk. However, by definition of language acceptance, Mk cannot accept any string not in Ldiag. Thus, wk is in Ldiag if and only if wk is not in Ldiag. Therefore, no Turing Machine exists which accepts Ldiag, so Ldiag is not recursively enumerable. QED.

For those familiar with a Cantor diagonal argument, the above proof may have a familiar feel to it. The idea is to look at pairs: (wi, Mi). If wi is not accepted by Mi, then wi is in Ldiag. In order to determine if Ldiag is recursively enumerable, it suffices to show the existence of a Turing Machine that accepts Ldiag. This is the crux of the proof. That is, understanding the definition of language acceptance will lead to a better understanding of why Ldiag is not recursively enumerable. Remember that in order to be recursively enumerable, that there must exist a Turing Machine which accepts Ldiag. The definition of language acceptance states that L(M) = Ldiag. That is, M only halts in the accepting state for strings in Ldiag.

Remember that Turing Machines are countable, as well. That means that there is a natural number k, such that Mk (by assumption) accepts Ldiag. Strings are enumerable as well. Thus, if the string wk over the given alphabet is accepted by Mk, then wk is not in Ldiag and Mk accepts a string not in Ldiag. This is a violation of the definition of language acceptance. Now if wk is in Ldiag, then Mk does not accept wk. Thus, L(Mk) != Ldiag, so Mk does not accept Ldiag.

Recursively Enumerable Languages and the Halting Problem
This section will introduce some recursively enumerable languages that are not decidable, as well as the Halting Problem. Recursively enumerable languages that are not decidable are used to describe problems whose solutions can be easily verified, but are difficult to find.

Consider the language: Ldiag_comp = { wi : wi is accepted by Mi }. This is the complement of Ldiag in the last section. The language Ldiag_comp is recursively enumerable, but not decidable. In order for a language to be decidable, both it and its complement must be recursively enumerable. Since Ldiag is not recursively enumerable, Ldiag_comp is clearly not decidable.

In order to show that Ldiag_comp is recursively enumerable, it is sufficient to show the existence of a Turing Machine that accepts it. The idea here is to have the Turing Machine, Maccept invoke the Universal Turing Machine to find the Turing Machine, Mk. If the input string, wk, is accepted by Mk, then Maccept accepts wk.

The Halting Problem, which is an incredibly important problem in computer science, comes to the forefront in determining limits of computational models. The idea is to determine if a given program will terminate on an arbitrary input string. That is, is it possible to determine if for all programs and for all input strings, a given program will terminate on a given input string? Note the universal quantifiers. The answer is that it is impossible to determine if a given program will halt an an arbitrary input. However, there are examples of programs where it is possible to determine if they halt on given input. Examples of these, and associated proofs, are reviewed in the context of Algorithm Analysis.

The consequences of the Halting Problem are far reaching. An important goal of software engineering is to show correctness and halting of a piece of industrial grade software. The Halting Problem implies that it is impossible to do this. There are practices in software engineering to improve one's ability to verify a program's correctness, but it is impossible to do this universally.

Now let's formalize the Halting Problem. Let LH = { p(M),w : M halts on w }. The language LH is not decidable, but it is recursively enumerable. To show that LH is recursively enumerable, the same approach is used as in showing that Ldiag_comp is recursively enumerable. That is, let H be the Turing Machine to accept LH. Given an input string, H invokes the UTM to simulate M on w. H accepts the input string if and only if M halts on w. Thus, H accepts LH, so LH is recursively enumerable.

Showing that LH is not decidable is a bit more subtle. It is done by contradiction. That is, assume there exists a Turing Machine T to decide LH. Since decidable languages are closed under complementation, ~LH = { p(M),w : M does not halt on w } is also decidable. Consider Ldiag. For each string xk in Ldiag, compose strings p(Mk),xk and let L'diag = { p(Mk),xk : Mk does not halt on xk }, which is a subset of ~LH. It follows that since LH can be decided by assumption, L'diag can be decided too. This implies that Ldiag can be decided, which is a contradiction, since Ldiag is not recursively enumerable. Thus, LH is undecidable. QED.

The Halting Problem is commonly used in proofs showing certain other languages are undecidable. The idea is to prove such languages are undecidable, using proof by contradiction. It is then shown that the given language being decidable implies the existence of a Turing Machine to decide LH, which is known to be a contradiction. A common mistake when reducing one language (problem) to another language (problem) is simply reducing one problem to a known hard problem. This proves nothing about the original problem. Instead, it must be shown that the reduction yields a solution to the known hard problem, which produces the necessary contradiction.

Some of these problems will now be explored.
  • Consider the language LES = { p(M) : L(M) contains the empty string }. LES is a recursively enumerable, but not decidable language. It is easy to show that LES is recursively enumerable. Let T be a Turing Machine to accept LES. T operates by invoking the Universal Turing Machine to run M, from the input p(M), on an empty tape. T accepts p(M) if and only if M halts on the empty tape.

    Showing that LES is undecidable is a bit trickier. It is done by contradiction, with reduction to the halting problem. The idea is to assume the existence of a TM, MES, that decides LES. Then, it suffices to find a Turing Machine such that it is impossible to decide if it contains the empty string. Thus, LES is undecidable.

    Consider an arbitrary Turing Machine M, and input string w, and construct a Turing Machine Mw. The TM Mw, when given the empty string as input, writes w to the tape and simulates M on w. Mw accepts the empty string if and only if M halts on w. It has already been shown that it is impossible to decide if M halts on w, as the Halting Problem is undecidable. Thus, it cannot be decided if L(M) contains the empty string, and p(M) is in LES. It follows that since L(M) is undecidable that LES is undecidable.

  • Let Lempty = { p(M) : L(M) = {} }. This language is undecidable. The idea in proving Lempty undecidable is similar to showing LES to be undecidable. That is, it suffices to show the existence of a Turing Machine where deciding if its language is empty will produce a solution to the Halting Problem. The clever bit is in designing such a Turing Machine. Consider an arbitrary Turing Machine M, and an arbitrary string w. Now construct a Turing Machine Mw. Given an input string x, it ceases to halt if x != w. Otherwise, if x = w, then it simulates M on w. Thus, L(Mw) is empty if and only if M does not accept w. Thus, Lempty is decidable if and only if the Halting Problem is decidable. It has already been shown that the Halting Problem is undecidable; and thus, the contradiction.

    It follows that since Lempty is undecidable that determining if two languages of Turing Machines are equal is undecidable. It simply reduces to the case showing that L(M1) = {} is undecidable, where M1 is a Turing Machine.

  • Let Lreg = {p(M) : L(M) is regular }. This language is undecidable. This proof of this is another proof by contradiction. The idea is to find a Turing Machine whose language is regular, but that it cannot be decided as such. The construction will be a Turing Machine whose language is conditionally regular, based on whether or not another Turing Machine accepts an arbitrary input string. This condition is undecidable, thus Lreg is undecidable.

    Let T be a Turing Machine and let w be an input string. Now construct a second Turing Machine, T', which will work in the following way. If the input string x is of the form 0n1n, for n a non-negative integer, then T' accepts it. Otherwise, T' simulates T on w. T' accepts x if T accepts w. Thus, if T accepts w, then L(T') = Σ*, which is regular. Otherwise, L(T') = { 0n 1n : n >= 0 }, which is strictly a context-free grammar. Determining if T accepts w is undecidable, determining if L(T') is regular is also undecidable. Thus, Lreg is undecidable.

The language Lreg is a special case of Rice's Theorem. In many texts, Rice's Theorem is stated as "any non-trivial property is undecidable," where a trivial property is one that applies to either all languages in RE or no languages in RE. This formalizes quite well to the following: Let RE be the set of Recursively Enumerable Languages, and let C be a non-empty, proper subset of RE. Then C is undecidable.

The idea in the proof of Rice's Theorem is quite similar to the proof that Lreg, by constructing a Turing Machine T whose language is conditional on a secondary Turing Machine. That condition relies on the Halting Problem being decidable, which is known not to be the case. Hence, the contradiction.

It is important as well to remember that the set of decidable languages is closed under complementation. So if C is decidable, then C's complement is decidable as well. Without loss of generality, let the language Lnull = {} be contained in C. If Lnull is in C's complement, the Turing Machine to decide C will still have to decide if Lnull is (not) present in C.

Since C is a proper subset of RE, C's complement is non-empty. Consider a language L' in ~C, with L' != {}. Since both Lnull and L' are recursively enumerable, there exist Turing Machines Mnull and M' such that L(Mnull) = Lnull, and L(M') = L'.

The idea now is to construct a Turing Machine T, such that L(T) = {} or L(T) = L', based on another Turing Machine, M. Given M and an arbitrary string, w, T will operate in the following way. Given an input x, T first simulate M on w. If M rejects w, then M' rejects w. If M accepts w, then T simulates M' on x, accepting x if and only if M' accepts x. Thus, L(T) = {} if M does not accept w, and L(T) = L' otherwise.

In order to decide if L(T) is in C, it is necessary to decide if M halts on w and accepts it. Given that the Halting Problem is undecidable, it follows that C is undecidable.

Is This A Good Question/Topic? 0
  • +

Page 1 of 1