Chapter 4: Decidability

After knowing the capabilities of each model of computation, it is outright to know their limitations.

At this point, Turing Machine(TM) is the most powerful model of computation .But one needs to ponder the question “Are there problems that cannot be computed by a TM?”.

This chapter from “Introduction of Theory of Computation” by Michael Sipser, discusses the solvability or decidability of a certain problem

Recall:

From Chapter 3: Church – Turing Thesis, we learned about languages that are Turing Recognizable and Turing decidable.

From that chapter also, we learned that Every decidable language is Turing recognizable but not all Turing recognizable are decidable.

In this chapter we present languages that are decidable by algorithms.

We will begin with computational problems concerning finite automaton.

  1. ACCEPTANCE PROBLEM: A test whether an automation M accepts a string w.
  2. A test whether the language of finite automaton M is empty or L(M)= null.
  3. A test whether two finite automata M1 and  M2 are equivalent. (When we say equivalent, they should accept the same language)

ACCEPTANCE PROBLEM

Given a finite automaton M and a string w, determine whether w ε L(M).

This problem can be expressed in a language, say ADFA

ADFA= {<M,w>| M is a DFA accepting string w}

The original question is similar to determining whether <M,w > is a member of ADFA.

Showing that the Language is decidable is like showing that the problem is decidable.

Theorem:

ADFA is a decidable language.

ADFA= {<M,w>| where M is a DFA accepting w}

_________________________

Proof Idea:

We simply need to present a TM that decides  ADFA.

TM1= on input <M, w>, where M is a DFA and w is a string

  1. Simulate M on w. (This assumes that M has an encoding for TM)
  2. If the simulation ends on an accept state then TM accepts <M,w>. If is ends on a non accepting state then TM rejects <M,w>

Theorem:

ANFA is a decidable language.

ANFA= {<N,w>| where N is  NFA accepting w}

_________________________

Proof Idea:

We need to present a TM that decides ANFA, but instead of making  another TM  that decides on ANFA we will make use of TM1 as a subroutine of TM2

TM2= on input <N, w>, where N is an NFA and w is a string

  1. TM2 first converts N to a DFA N’
  1. Simulate DFA N’ to TM1
  2. If TM1 accepts w, accept, if not then reject.

Theorem:

AREX is a decidable language.

AREX= {<R,w>| where R is a regular expression that generates w}

_________________________

Proof idea:

We need to present TM that decides on AREX.

TM 3 uses TM2 as a subroutine.

TM3= on input <R,w>, where R is a regular expression and w is a string.

  1. Convert the regular expression  R to an equivalent NFA RN.
  2. Simulate RN on TM2.
  3. If TM2 accepts, accept; if TM2 rejects, reject.

Theorem:

EDFA is a decidable language.

EDFA= {<A>| where A is a DFA and L(A)= null}

_________________________

Proof Idea:

Need to present TM that decides on EDFA.

We know  that a DFA accepts a string if there is a path from the start state to an accept state.

To determine whether L(A)= null or not, we will use a marking algorithm.

T= on input <A> ,where <A> is an encoding of a DFA A

  1. Mark the start state of A
  2. Repeat until no new states are marked
    1. Mark any state connected to a marked state
  3. If no accept state is marked, then accept; otherwise reject.

Theorem:

EQDFA is a decidable language.

EQDFA= {<A,B>| where A  and B are DFAs and L(A)=L(B)}

________________________

Proof Idea:

One way to prove the above statement is to show that L(A)is a subset of L(B) and L(B) is a subset of A. That is to show that there is a Turing Machine that decides on L(A) is a subset of L(B) and its reverse.

One elegant algorithm  uses TM T as a subroutine.

First generate a DFA C from A and B.

C = {L©(C) |  L(C) =( L(A) and !L(B) ) or (!L(A) and L(B)) }

L(C) is simply the set difference of L(A) and L(B), so if L(C)=null then

L(A)= L(B)

We will just need to simulate C on TM T.

If its accepts, accept; otherwise, reject.

************************************************************************

Now we will consider computational problems concerning CFGs.

Let’s start off with the Acceptance Problem of CFGs

Theorem:

ACFG  is a decidable language.

ACFG= {<C,w>| where C is a CFG and it generates string w}

________________________

Proof Idea:

One idea is to generate all derivations of C then check whether w is one of its derivation, This is not a good idea because the TM that will simulate the generation will not stop if w is not derived from C.

This leads us to a Turing Machine that recognizes but not decides on ACFG.

But to make a Turing Machine that will decide on ACFG, we need to have a finite derivations of C. We know that C in its Chomsky Normal Form (CNF) has 2n-1  derivations of w, where n is the length of w. In that case checking only 2n-1 derivations on w is sufficient to determine whether C generates w or not.

Let TM_CFG be the Turing Machine that decides on ACFG

TM_CFG= on input <C,w>, where C is a CFG and w is a string

  1. Convert C to its equivalent CNF denoted by C_CNF.
  2. Generate all 2n-1 derivations of C_CNF.
  3. If w is one of its derivation, accept; otherwise, reject.

Theorem:

ECFG is a decidable language.

ECFG= {<A>| where A is a CFG and L(A)= null}

_________________________

Proof Idea:

In order to determine whether a grammar can generate a string, we need to test if the start symbols can generate a string of terminals.

Proof:

TM_ECFG= on input <A>, where A is a CFG

  1. Mark all terminal symbols
  2. Repeat until no new symbol is marked
    1. Mark any variable B if B has a rule, B-> U1,U2,…,Uk and each symbol Ui has already been Marked
  3. If the start state is not marked, accept; otherwise, reject.

EQCFG= {<A,B>| where A and B are CFGs and L(A)= L(B)}

Since the class of CFGs are not closed under complementation or intersection, the proof idea we used in proving EQDFA is not valid. In fact

EQCFG is not decidable!

Theorem:

Every Context free Language is decidable.

_________________________

Proof Idea:

One (bad) idea one must instantly think is to convert a PDA to a TM, but instead of making use of the infinite tape, the tape should behave as a Stack and since PDA are nondeterministic, we can easily convert a dTM to a nTM.

This idea is not a valid proof for the decidability of every CFG, to be able to decide, TM should halt on all input, and because the generation of strings can possibly end up in an infinite derivation, clearly TM will not decide on the CFG.

Instead we use the Turing Machine that decides on ACFG.

Proof:

Let A be a CFL. Let G be a CFG for A.

Let TM_CFL be a TM that decides on A.

TM_CFL= on input w

  1. Simulate G on TM_CFL on input w
  1. If this machine accepts w, accept; otherwise, reject.

*****************************************************************************

One of the famous problems that gave birth to the theory of computation is the Halting Problem.

This was proposed by Alan Turing as a hypothetical problem to prove unsolvability.

Though computers  seems to be so powerful, they are still bounded by some limitations.

One can possibly think that  problems that are unsolvable are too complex, but as a surprise, there are set of problems that are deceivingly simple to be classified as unsolvable

HALTING PROBLEM

ATM= {<M,w>| M is a TM and it accepts w}

Is ATM  decidable??

___________________________________

From Chapter 3 we know that all Turing decidable are Turing Recognizable, but not all Turing Recognizable are decidable. The condition in decidable language(TM should halt on all input) added more restriction to Turing Recognizable.

In this discussion of the Halting problem, we will learn that a n ATM is not decidable. This is proven using a simple proof by contradiction and a method called Diagonalization introduced by Georg Cantor in 1873.

Proof 1: Proof by Contradiction

Let’s assume we have a TM H that decides on ATM.

On input <M, w> where M is a Turing Machine and w is an input string.

H(<M,w>)={accept                          if M accepts w}

{reject                           if M rejects w }

Now we have a Turing Machine D with H as a subroutine.

TM D= on input <M>, where M is a TM

  1. Simulate H on input<<M>, M>
  2. Output the opposite of what H outputs

D(<M>)= {accept if M does not accept

reject if M rejects w }

Now if we run <D> on D

D(<D>)= {accept if  D does not accept

reject if D rejects}

Tadaaa!!! Contradiction, There a Decider H does not exist.

Another method is called the Diagonalization. You can check page 183 of Sipser’s “Introduction to Theory of Computation”.

Theorem:

Some Languages are not Turing-recognizable

________________________________________

Proof Idea:

We just need to show that the number of encoding of problems are infinite while the Turing Machine is finite.

Therefore, there will be problems that cannot be solved by a Turing Machine

The Languages that are not Turing-recognizable belongs to the class of Turing-unrecognizable

Theorem:

A language is decidable iff it is Turing-recognizable and co-Turing recognizable.

Or in other words a language is decidable exactly when both it and its complement are Turing-recognizable.

_______________________________________________________

from this above theorem it follows that !ATM is Turing-unrecognizable.


Advertisements

2 thoughts on “Chapter 4: Decidability

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s