Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015,May 2014

a) Halting Problem

• The Halting Problem is a special kind of a problem wherein a machine is proved to be undecidable in its behaviour at one point where its composition is changed.

• For this, we assume a universal machine for this example and a couple of simpler machines

• We consider two simple machine, one(A) which performs addition of two numbers, and another(B) that converts a number from decimal to binary

• Machine A cannot execute the output of machine B, neither can machine B execute machine A’s output.

• Now, we have a machine D which executes any machine’s(here, A or B) output taking that machine’s blueprint and that machine’s individual input set as the input.

• So, machine D will execute machine A’s output on gaining machine A’s blueprint and so is the case for machine B.

• Now, we construct a universal machine U that has machine D(to identify the machine to be executed) and a negator machine N(to reverse the output)

• If we give machine B’s blueprint and machine A’s input set to U, we should be getting an error, which doesn’t happen as the negator reverses the ‘false’ output to ‘true’.

• If we give machine B’s blueprint and machine B’s input set to U, we should be getting the correct, which doesn’t happen as the negator reverses the ‘true’ output to ‘false’.

• This problem of undecidability is often what is termed as the Halting Problem.

b) Rice’s Theorem

• Rice's theorem helps explain one aspect of the pervasiveness of undecidability. Here is the theorem and its proof, following the needed definition.

• A property of languages is a predicate P : ‘P (Σ*) =>{false,true} for some alphabet Σ. That is, the input of P is a language and the output is a truth value.

• The value P(L) =true means L has property P.

• The value P(L) =false means L does not have property P.

• Example properties are : is finite, is infinite, is r.e. , etc.

• A non-trivial property of r.e. languages is a property of languages P such that P(L0) for some r.e. language L0 and P(L1) for some r.e. language L1

• In English, some r.e. language has the property and some r.e. language does not. All the example properties we listed above are

• nontrivial with the exception of \is r.e." for some alphabet . Thatis, the input to P is a language and the output is a truth value. The value P(L) = true means that L has the property P ; the value P(L) = false means that L does not have property P

Rice’s Theorem : -

If P is a non-trivial solution of r.e. languages then

LP={(M):P(L(M))}

is undecidable

Proof:

We assume that Φ does not have a property P:P(Φ)=false.

We show that $ATM \lt mLP$ . For this we must exhibit a Turing computable function for which $M' = f(M,w)$ is a machine accepting a language with property P iff M accepts w.

Let the behaviour of M’ on input x to be :

1.) Run M on w.

2.) If M rejects, reject

3.) Run $M_1$ on x where $M_1$ is a fixed machine for which P(($M_1$))=1. We know that such a $M_1$ exists because P is a non-trivial solution of r.e. languages

4.) If $M_1$ accepts, accept; if $M_1$ rejects , reject.

c) Arden’s Theorem

• The Arden’s theorem is used in regular languages to determine whether a given expression has a unique solution

• It states that for two regular expressions out of which one does not contain ε as its input, there exists a unique solution

• Let P and Q be two regular expressions So if P doesn’t have ε as its input, R = Q + RP will have a unique solution represented by R = QP*

  Proof:

  We need to consider the fact that a regular expression r can be represented as ε + $r^2$ + $r^3$ +…

  So, we begin the proof using

  R = Q + RP

  We substitute R = Q + RP in the RHS

  We get,

  R = Q + (Q + RP) P

  $= Q + QP + RP^2$

  Again replacing R = Q + RP in RHS gives us

  $R = Q + QP + QP^2 + RP^3$

  Hence, a series is generated as follows:

  $R = Q(ε + P + P^2 +…)$

  But $(ε + P + P^2)$ can be replaced by P*

  Hence, R = QP*, a unique solution hence exists.

d) Post Correspondence Problem

• The Post Correspondence Problem is an undecidable problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable

• Let Σ be an alphabet with at least two letters. An instance of the Post Correspondence problem (for short, PCP) is given by two sequences U = (u1,...,um) and V = (v1,...,vm), of strings ui,vi∈ Σ*.

• The problem is to find whether there is a finite sequence (i1,...,ip), with ij∈ {1,...,m} for j = 1,...,p, so that

  ui1ui2 ....uip = vi1vi2 ...vip.

• Example:

  Let U= {0,2,4,6,8} and V={1,3,5,7,9}

• As per the theorem we have to find a finite sequence I such that

  ui1, ui1,…,uip= vi1, vi1,…, vip

• Let us assume we have a sequence I = {1,2,3,4,5}

• So, as p = 5 in this case,

  ui1, ui1,…,uip= u1, u2,…, u5 = 0,2,4,6,8

  vi1, vi1,…,vip= v1, v2,…, v5 = 1,3,5,7,9

• But as we see in this example,

  ui1, ui1,…,ui ≠ vi1, vi1,…, vip

  So we need to find another finite sequence I such that

  ui1, ui1,…,uip= vi1, vi1,…, vip

• Finding such a sequence I would hence be undecidable as it would also depend on the two sequences U and V

• The Post correspondence problem is undecidable, provided that the alphabet Σ has at least two symbols.

• We shall reduce the halting problem to the PCP, by encoding sequences of ID’s as partial solutions of the PCP.

• For instance, this can be done for RAM programs. The first step is to show that every RAM program can be simulated by a single register RAM program.

• Then, the halting problem for RAM programs with one register is reduced to the PCP (using the fact that only four kinds of instructions are needed). As an application, we prove the following result:

  It is undecidable whether a context-free grammar is ambiguous.

• Proof . We reduce the PCP to the ambiguity problem for CFG’s. Given any instance U = (u1,...,um) and V = (v1,...,vm) of the PCP, let c1,...,cm be m new symbols, and consider the following languages:

• LU = {ui1 ....uipcip ...ci1 | 1 ≤ ij ≤ m, 1 ≤ j ≤ p, p ≥ 1},

• LV = {vi1 ...vipcip ...ci1 | 1 ≤ ij ≤ m, 1 ≤ j ≤ p, p ≥ 1}, and LU,V = LU ∪ LV .

• We can easily construct a CFG, GU,V , generating LU,V . The productions are:

  S −→ SU S −→ SV SU −→ uiSUci SU −→ uici SV −→ viSV ci SV −→ vici.

• It is easily seen that the PCP for (U,V ) has a solution iffLU ∩ LV 6= ∅iff G is ambiguous.

• Remark: As a corollary, we also obtain the following result: It is undecidable for arbitrary context-free grammars G1 and G2 whether L(G1) ∩ L(G2) = ∅.