Turing machine acceptors and decidability:

Deterministic TM: M = (Q, A, f: Q x A -> Q x A x {L, R}, q0, qa , qr}.

Tape actions: L = move left, R = move right. Designated states: q0 = begin state, qa = accept, qr = reject. qa and qr are the halting states.

The Turing machine acceptor has three possible outcomes: accept, reject and loop.

Df: M accepts w ∈ A* if and only if M’s computation on w ends in qa. L(M) = {w ∈ A* / M accepts w}
Df: L ⊆ A* is Turing recognizable (that is, recursively enumerable, semi-decidable) if and only if there is a TM M with L = L(M).
Df: The TM acceptor M which always halts (that is, in one of its states qa or qr) is termed as a decider for its language L(M).
Df: L ⊆ A* is Turing decidable (that is, recursive) if and only if there is a TM decider M with L = L(M).

Notice: Any TM acceptor M is recognized for its language L(M), however merely some of them are deciders.

Theorem: L is a Turing decidable if and only if both L and its complement ¬L are Turing recognizable

Proof ->: When M is a decider for L, then M’ with q’a = qr and q’r = qa is a decider for ¬L.

As deciders are as well recognizers, both L and ¬L are the Turing recognizable.

Proof <-: Assume M be a recognizer for L and  ¬M a recognizer for  ¬L. Build a decider Z (‘zigzag’) for L as follows. Z has three tapes: input tape with w on it, tape T (M’s tape), and tape ¬T (¬M’s tape).

Z on input w alternates simulating the transition of M by using T and a transition of ¬M by using ¬T. One of M and ¬M will accept w and halt and at this moment Z halts as well, announcing the verdict ‘accept’ or ‘reject’ based on which the recognizer accepted w. QED

The word problem for automaton M or language L (of any type): given M and w ∈ A*, does M accept w?

Given L and w ∈ A*, is w ∈ L? Represent the word problem and their corresponding languages) for FAs, PDAs, and TMs by WFA, WPDA, WTM correspondingly.

Example: WDFA = {<M, w> | M is a DFA, M accepts w} is decidable. The TM simulates action of M on w.
Example: WNFA = {<M, w> | M is a NFA, M accepts w} is decidable.

The TM traces all legal paths labeled w via M’s state space.

Example: WNPDA = {<M, w> | M is a NDPA, M accepts w} is decidable. The TM which merely simulates the action of M on w is no decider, as a PDA can loop, and therefore, simulation might never terminate. Though, we can transform an NPDA to an equivalent CFG G (example in Chomsky normal form) and test all the derivations which produce words of length |w|.

Theorem (the word problem for TMs is undecidable):

WTM = {<M, w> | M is a TM, M accepts w} is not decidable.

Proof: Suppose WTM is decidable, and D is a decider for WTM, that is,

D(<M, w>) = accept, when M accepts w, and
D(<M, w>) = reject, when M rejects w or M loops on w.

From this supposition we will derive a contradiction by using a method which is standard in logic, set theory, and computability. Prior to proceeding, consider several explanatory historical comments.

Most of the undecidability proofs continue by self-reference, example by having a supposed TM (or algorithm in other notation, as we had seen in halting problem) examines itself. In order for the self-reference to outcome a proof of impossibility, we have to craft core of a contradiction to the argument. These contradictions lead to familiar ancient paradoxes like ‘the Cretan Epimenides who states Cretans always lie’, or ‘the barber who shaves all people which do not shave themselves’. Is Epimenides lying or telling truth? Does barber shave himself or not?

The kind of self-reference which leads to paradoxes was formalized by the Cantor in the form of his ‘diagonalization method, used to prove lots of impossibility or non-existence outcomes. Why the word ‘diagonalization’? In terms of example above, consider all the pairs <M, w> arranged as a doubly infinite array, with TM M as rows and tapes or words w as columns. The explanation <M> of TM M is as well a word over the alphabet we are considering. Therefore, some of w’s are as well <M>’s, and it is natural to call the pairs <M, <M>> the ‘diagonal’ of array. In case of WTM, diagonal entries signify ‘M is a TM which accepts its own explanation <M>’. Nothing suspicious so far, just as there is no paradox when Epimenides states ‘Cretans always tell the truth’ (this statement may be untrue, however it is consistent - in an ideal world, it may be true). Deriving a contradiction needs devious cleverness. By analogy with paradoxes, we build TM Cantor which derives a contradiction from the supposed existence of a decider D for WTM. Cantor (<M>) interprets its input as the explanation <M> of a TM M according to certain fixed coding scheme. When the input is not the explanation of any TM, Cantor halts with the message ‘syntax error’. On syntactically correct input <M>, Cantor simulates D on the input <M, <M>>, deciding whether M will halt when fed its own description.
Subsequent to having heard D’s answer, Cantor contrives to say the opposite:

When D(<M, <M>>) accepts, Cantor(<M>) rejects; When D(<M, <M>>) rejects, Cantor(<M>) accepts.

This holds for all M, therefore consider the special case M = Cantor. We find out that Cantor (<Cantor>) accepts, when Cantor (<Cantor>) rejects and vice-versa. This contradiction in Cantor’s behavior forces us to refuse the weakest link in the argument, namely, the unsupported supposition that a decider D exists for WTM. QED

Proof: Suppose HALTTM is decidable by using a decider H, that is, H(<M, w>) halts, rejecting or accepting based on whether M halts on w, or loops. Build TM R (‘reduce’), a decider for WTM, as follows:

A) R(<M, w>)  simulates H(<M, w>), a procedure which halts beneath the supposition that the decider H exists.
B) When H rejects <M, w>, we know M(w) loops, therefore R rejects <M, w>;
C) When H accepts <M, w>, we know M(w) will halt, therefore R simulates M(w) and reports the outcome, reject or accept.

Therefore, the existence of H implies the existence of R, a decider for word problem WTM, a problem we have just verified to be undecidable. Contradiction -> QED.

Example: Prove that REGULARTM = {M | M is a Turing machine and L(M) is regular} is undecidable.

Proof: Suppose that there is a TM R which decides REGULARTM. From R we derive a TM W which decides the ‘word problem’ WTM = {<M, w> | M accepts w}, that has been proven to undecidable -> contradiction.

At first, consider a 2-d family of TMs NM, w, where M ranges over all the TMs, in some order, and w ranges over all the words ∈ A*. Such artificially made TMs NM, w will never be executed; they are mere ‘Gedanken-experiments’. Various NM, w accept the non-regular language 0n1n, n ≥ 1, the other NM, w accept the regular language A*. Therefore, the supposed TM R which decides REGULARTM can analyze any NM, w and tell whether it accepts the non-regular language L(NM, w) = {0n1n} or the regular language  L(NM, w) = A*. The main goal of the proof is to arrange things in such a way that L(NM, w) is regular or irregular based on whether M accepts w or refuses w. When this can be arranged, then TM R which decides REGULARTM can indirectly decide the ‘word problem’ WTM and we have desired contradiction to the supposition of R’s existence.

Therefore let us construct NM, w. NM, w (x) at first does a syntax check on x, then proceeds as shown:

i) When x = 0n1n, for some n ≥ 1, NM, w accepts x.

ii) When x ≠ 0n1n, for any n ≥ 1, NM, w simulates M on w. This mainly relies on NM, w having a universal TM which can simulate any TM, given its explanation. This simulation of M on w can have three outcomes: M accepts w, M rejects w, or M loops on w. NM, w‘s action in each of such case is as shown:

M accepts w: NM, w accepts x. Note: in this case NM, w accepts all x ∈ A*, that is, L(NM, w) = A*.
M rejects w:  NM, w rejects x. Note: In this case NM, w accepts ONLY words of the form 0n1n by rule (i).
M loops on w: NM, w loops. Note: NM, w has no other choice. When M loops, NM, w never recovers control.

The total effect is that L(NM, w) is regular if and only if M accepts w, and irregular if and only if M rejects w. The supposed TM R which decides REGULARTM, given an explanation <NM, w>, indirectly decides whether M accepts w.

In order to complete the proof, we examine that it is straightforward to build a TM W which reads <M, w>, from this constructs a  description < NM, w>, and ultimately calls R to decide the word problem, known to be undecidable.

Contradiction -> QED.

Theorem: The computable numbers, while countable, can’t be efficiently enumerated!

Proof: Suppose there exists TM M which enumerates all the computable real numbers. By Cantor’s diagonalization method, we construct a new TM M’’’ which computes a new computable number y, y ≠ xk for all k. This contradiction verifies the non-existence of M. Let consider the infinite array of digits

 x1 = x11 x12 x13 ..
 x2 = x21 x22 x23 .. x3 = x31 x32 x33 ..
 ..

Alter M to get a TM M’ which, given k, prints the digit xkk. This merely includes computing the digits of xk in sequence as M does, throwing away the first k-1 digits and stopping after printing xkk. Now alter M’ to get M’’ that prints the diagonal sequence of digits x11 x22 x33 ..... Lastly, alter M’’ to get M’’’ that prints the sequence of complements of bits xkk. This sequence denotes a new computable number y that varies from all xk - contradiction, QED.

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.