Larry Bush November 15, 2001



Download 55.85 Kb.
Date conversion31.01.2017
Size55.85 Kb.

Larry Bush November 15, 2001

email: bushl2@rpi.edu, Lawrence_Bush@dps.state.ny.us

Student ID: 660 220 742
Home Work 4 - Computability and Complexity (CSCI-6050)

Instructor: Prof. Goldberg




Problem 1

Let INFINITEDFA = { : A is a finite automaton and L(A) is an infinite language.}


Show that INFINITEDFA is decidable.
Let D be a TM that decides INFINITEDFA.

In order for D to accept , A must represent a DFA that accepts an infinite language. In order for A to accept an infinite language, A must have at least one loop in it. This is because a DFA without a loop can only accept strings which pass through each of the DFA’s states at most once. Since there are a finite number of states, the strings that it accepts are limited in length to less than the number of states in the DFA.


Therefore, we will construct a TM that determines if A has a loop in it.
D = “On input , where A is a DFA :
- Decode
to determine A.
- Look for Cycles.

  1. Mark the start state of A.

- This becomes the ‘marked state(s)’.

  1. Mark any state that has a transition coming into it from any of the marked state(s).

  2. Loop Test – Go through each newly marked state - If the current state was already marked (we have found a loop) go to step 6.

  3. Stop Test – If no new state has been marked continue with step 5, otherwise, go to step 2.

  4. Reject (this DFA is acyclic – no loops)

- Does Cycle Lead To Accept?



  1. Simulate a stack and push the list of marked states to it.

  2. Add the current state(s) to the cycle state(s).

  3. If any of the cycle state(s) is an accept state, then D accepts.

  4. Add any state that has a transition coming into it from one of the cycle states to the list of cycle states.

  5. If step 9 resulted in no new states being added to the list of cycle states (if old cycle states = new cycle states) then pop the list of marked states from the stack and return to step 3 (Cycle does not lead to accept).

  6. Go to step 8.

The above algorithm accepts any DFA that has a cycle and has a sequence of transitions that lead from a cycle state to an accept state.


Therefore, D accepts the encoding of any DFA that can accept an infinite language. D also rejects the encoding of any DFA that cannot accept an infinite language. Therefore, INFINITEDFA is decidable.

Problem 2
Let Neven = {2, 4, 6, ...} be the set of all positive integers.

Prove that the set K of all subsets of Neven is uncountable.


First we know from Definition 4.12 that a set is countable if either it is finite or it has the same size as N (the set of positive integers).
A set is said to be the same size as N if there is a correspondence from N to the set.
A correspondence is a function that is both one-to-one and onto.
A function is one-to-one if it never maps two different elements of the first set to the same element of the second set.

For example if f is one to one, f(n) will never map two different elements of N to the same subset of Neven in K.

A function is onto if every element in the second set has an element in the first set mapped to it by f.

For example if f is onto, every element in K will have some element of N mapped to it by f(n).


In a correspondence every element of the first set maps to a unique element of the second set and each element of the second set has a unique element of the first set mapping to it.

For example if f is a correspondence between N and K, then f(n) will map every element of N to a unique element of K and each element of K will have a unique element of N mapping to it.


To prove that K is uncountable we show that no correspondence exists between N and K there Kn = f(n).
This proof is by contradiction.
Let’s assume that a correspondence f exists between N and K.

We will then show that f fails to work as it should.


For f to be a correspondence, f must pair all the members of N with all the members of K.

However, we will find an x in K that is not paired with anything in N, which will be a contradiction to the assumption that a correspondence f exists between N and K.


In order to identify x, we will construct it.

K is the set of all subsets of Neven.

Each element of K is a subset of Neven.

f(n) maps an element of N an element of K that we identify as Kn where 1 is mapped to K1, 2 is mapped to K2, etc.


x is an element of K for which there is no mapping to, from N by f.

Then x is comprised of a subset of the elements of Neven.

Then one element of x is an element of Neven.
We choose each element of x to make x different from one of the elements of K that is paired with an element of N.
We do this by making a specific element of x different from that element of f(n).
We use a systematic way of doing this. To keep track of the element of Neven that we are addressing, we use the correspondence N to Neven which is f-even(n) = 2n. Then, for a given n, we determine whether f(n) (which is Kn) contains the element 2n. If it does, we construct x so that it does not.
If Kn does not contain the element 2n, we construct x so that it does contain the element 2n. We do this for every mapping from N to K. When we are done, we have an x where:
if Kn contains the element 2n then x does not contain the element 2n.

if Kn does not contain the element 2n then x contains the element 2n.


After choosing each element of x in this way, x will be different from every element of K that is paired to an element of N.
For example: Suppose the correspondence f exists. Let f(1) = { 2 }, f(2) = {2, 4}, f(3) = {2, 4, 14}... and so on. Then f pairs the number 1 with { 2 }, the number 2, with {2, 4}, the number 3, with {2, 4, 14} ... and so on. The following table (first 2 columns) shows some values of this hypothetical correspondence f between N and K.


n

f(n)

binary representation

x

x – binary representation

1

{ 2 }

1000 0000 ...

{ }

0000 0000 ...

2

{2, 4}

1100 0000 ...

{ }

0000 0000 ...

3

{2, 4, 14}

1100 0010 ...

{ 6 }

0010 0000 ...

4

{2, 4, 16}

1100 0001 ...

{ 6, 8 }

0011 0000 ...

5

{2, 4, 10}

1100 1000 ...

{ 6, 8 }

0011 0000 ...

.

.










.

.










.

.









We construct the desired x by starting with the empty set { }.


Our objective is to ensure that x  f(n) for any n.

To ensure that x  f(1) we determine if f(1) contains 2n (which is 2). Since f(1) contains the element 2, we construct x so that it does not. x = { }


To ensure that x  f(2) we determine if f(2) contains 2n (which is 4). Since f(1) contains the element 4, we construct x so that it does not. x = { }
To ensure that x  f(3) we determine if f(3) contains 2n (which is 6). Since f(3) does not contain the element 6, we construct x so that it does. x = { 6 }
To ensure that x  f(4) we determine if f(4) contains 2n (which is 8). Since f(4) does not contain the element 8, we construct x so that it does. x = { 6, 8 }
To ensure that x  f(5) we determine if f(5) contains 2n (which is 10). Since f(5) contains the element 10, we construct x so that it does not. x = { 6, 8 }
x can also be represented as a binary string of infinite length.

Where, the left most digit represents whether x contains 2, the second digit represents whether x contains 4, etc.


Under this representation, x = 0011 0000 ...
The intermediate steps of the binary representation of x for this example are shown in the table above.
Using these 2 representations, we have constructed an x where:

xn  Neven (each element of x is an element of Neven)

xn = ~f(n) n (the n-th bit of the binary representation of x is flipped to the oppisite of the n-th bit of the binary representation of f(n))

x  K (but x is an element of K)

xn  f(N) (and there is no mapping from N to x by f)

Therefore we have constructed an x in K that is not mapped to by f from N.

This proves that it is not possible to construct a correspondence from N to K.

Thus proving that Neven is uncountable.



Problem 3
Show that the relation A <m B is transitive. (A and B are languages over E.)
A relationship R is said to be transitive if for every x, y, and z, xRy and yRz implies xRz.
To show that the relation A <m B is transitive or more generally mapping reducibility is transitive, we need another relation B <m C.
Therefore we will show that, if :

  1. mapping reducibility is transitive

  2. A <m B

  3. B <m C

Then: A <m C


First we will clarify what mapping reducibility means:
If we are able to reduce problem A to problem B by using a mapping reducibility then this means that a computable function exists that converts instances of problem A to instances of problem B.
A computable function is a function f: E* ->E* if some TM, on every input w, halts with just f(w) on its tape.
Then a language A is mapping reducible to language B if there is a computable function f: E* ->E* , where for every w,

w A  f(w)  B


In other words,
if A <m B by fAB

then for every string w A, fAB (w)  B


and
if B <m C by fBC

then for every string w  B, fBC (w)  C


Then by definition the relation is transitive because if A <m B via function fAB and

B <m C via function fBC, then A <m C via the composed function fBC of fAB :
fBC( fAB(w) )

This of course assumes that fBC( fAB(w) ) is turing computable. This is true and is explained as follows.


First of all we know that if A <m B via function fAB and

B <m C via fBC then fAB and fBC are by definition Turing computable.


If both fAB and fBC are Turing computable, then fBC of fAB is also Turing computable.
This can be shown by describing how to build a TM which computes fBC( fAB(w) ).
We will call TMAB the Turing Machine that computes fAB on an input.

We will call TMBC the Turing Machine that computes fBC on an input.


Then TMBC(AB) works as follows:

First we simulate TMAB on input wA producing output w’B.

Then we simulate TMBC on input w’B producing output w’’C.

Since fAB and fBC are computable functions.


Then by the above description;

TMAB starts with w on its tape and halts with w’ on its tape and

TMBC starts with w’ on its tape and halts with w’’ on its tape on input w’.
Subsequently, TMBC(AB) starts with w on its tape and halts with w’’ on its tape.

or rather TMBC(AB) of wA produces output w’’C


Therefore, TMBC(AB) is a computable function.
Therefore, A <m C via the reduction function TMBC(AB).

Therefore A <m B is transitive.



Problem 4
Let L be a lanuage comprised of the encoding of Turing machines that accept at least on a string of length three:
L = { : M accepts at least one string of length 3 }
Prove that L is a Turing-recognizable language.
To do this, we will construct a TM ‘A3’ that accepts where M  L.
A3 : On input


  1. Generate all strings (wn) over E of length 3.

  2. Run M on w1-wn simultaneously.

    1. One step on w1, w2 ... wn

    2. If one of wn is accepted then A3 accepts.

Since E is finite, the number of strings of length 3 over E is finite.


Therefore, we will be able to get to character 3 of wn in finite time.
Therefore, M will be able to accept if M can accept at least one string of lenth 3.
Therefore, A3 will be able to accept if M accepts.
Therefore, L is Turing recognizable.

Note:


A3 will not be capable of rejecting  L. Therefore, A3 is Turing-recognizable but it is not decidable.

We could add a third step that rejects if M rejects all strings over E of length 3. However,  L may not reject strings that it does not accept.

Therefore, there would still be many cases of  L that A3 would not reject.
Problem 5
Let EQCFG = { : G1 and G2 are CFGs and L(G1) = L(G2)}

Show that EQCFG is undecidable.

To prove that EQCFG is undecidable we will assume that EQCFG is decidable and that D is a TM that decides EQCFG .
Then we will use D to construct a decider for ALLCFG which contradicts Theorm 5.10 from the book which states ALLCFG is undecidable and is followed by a subsequent proof of the theorem.
ALLCFG = { | G is a CFG and L(G)= E* }
Proof:
D is a TM that decides EQCFG.
We will use D to construct a decider M for ALLCFG.
Let G? be a CFG.

We will construct a TM that decides if G? generates all possible strings over E (E*).


M = “On input ?> where G? is a CFG:

  1. Construct a CFG GALL where L(GALL) = all possible strings over E (E*).

  2. Run the decider for EQCFG on < G?, GALL >.

  3. If EQCFG accepts, then M accepts.

  4. If EQCFG rejects, then M rejects.

Conclusion: Since ALLCFG was proven previously to be undecidable, we have constructed a contradiction. Therefore, we conclude that the assumption that D is a TM that decides EQCFG is incorrect and therefore EQCFG is undecidable.




Problem 6
Prove that Accept_Two is undecidable.
Given:
Language Two = EoE (all strings over E of length 2)
Language Accept_Two = { : M is a TM L(M) = Two}
Assume:
DAccept_Two is a TM that decides Accept_Two.
DAccept_Two takes as its input and determines if is in the language Accept_Two or not.
Proof: We let TM DAccept_Two decide Accept_Two and construct the TM ‘S’ to decide ETM as follows.
S = “On input 0> where M0 is a TM that we which to decide if L(M0) = 0.


  1. Using M0 and M2 (where M2 is a TM that accepts all strings of length 2) we can construct a new TM ‘M0o2‘ which accepts the concatenation of L(M0) and (M2) and M2. Therefore, if M is ETM then this concatenation will create a TM that accepts all strings of length 2.

The collection of Turing-recognizable is closed under concatenation.

The collection of decidable languages is also closed under concatenation.

(See concatenation proof below.)




  1. Apply DAccept_Two to < M0o2>

  2. if DAccept_Two accepts

  3. then S accepts

  4. if DAccept_Two rejects

  5. then S rejects

If DAccept_Two decides M0o2, then S decides ETM because L(M0o2) = L(M0) o L(M2) and therefore decides if 0> is in language ETM.


Conclusion: Since Etm was proven previously to be undecidable, we conclude that the assumption that Daccept_two decides Accept_Two is incorrect and therefore Accept_Two is undecidable.

Supporting Proofs

The following are 2 supporting proofs that the collection of Turing-recognizable is closed under concatenation and the collection of decidable languages is also closed under concatenation.

Supporting Proof 1:
Concatenation - L1 recognizable and L2 recognizable -> L1  L2 recognizable
Let L1 and L2 represent arbitrary turing acceptable languages that are accepted (recognized but not necessarilly decided) by the Turing Machines TM1 and TM2 respectively.
To prove that L1  L2 is closed for all Turing acceptable languages we need to show that there is a Turing Machine TM-Union that will recognize the language L = L1  L2 (the language defined by the concatonation of L1 and L2).
TM- can be constructed by creating a TM that non-deterministically splits the input string w (of length p) into every possible combination of 2 pieces at point n where w1 consists of the first n characters of w and w2 consits of the last p-n characters of w. Then, TM1 will be run on w1 and TM2 will be run on w2. TM- will accept w iff TM1 accepts w1 and TM2 accepts w2. Since the correct non-deterministic splitting of w into w1-w2 will be recognized by TM-, then w will be recognized by TM-.
This works because L (L = L1  L2) is a language whose strings (i.e. w) consist of a string from L1 (w1) concatonated to a string from L2 (w2). Therefore, we assume that w will be broken into w1 from L1 and w2 from L2. Then w1 will be run on TM1 and recognized, and w2 will be run on TM2 and recognized. The result is that w will be recognized by TM-.
The non-deterministic splitting of w is an important part of this machine description.

w of length p will be non-deterministically split into every possible 2 pieces at point n where w1 consists of the first n characters of w and w2 consits of the last p-n characters of w. (w1 and w2). Note that this description allows for the possibility that w1 or w2 may be the empty string.

While many of these combinations will not be the w1-w2 strings contained in L1 and L2, and therefore may not be recognized by TM-, one of these combinations will be w1-w2.

Implementation:


This setup can be simulated on a 2-tape TM.
Initially, a new set of transition functions would need to be added, nondeterministically split w into w1 and w1. As it was being split, w1 would be copied onto tape 2 and that portion of tape 1 would be overwritten with a marker.
Next, we need a set of 2-tape transition functions which allow the simultaneous application of any TM-1 transition functions (on tape 1) and the application of any TM-2 transition functions (on tape 2).
Then we have TM- accept if both TM1 and TM2 accept and reject if either TM1 or TM2 reject.

To do this we would make q-accept(TM1) and q-accept(TM2) no longer accept states. Then we would create a new accept state and a new transition function that connects the two previous accept states to it.


This setup works because if L1 and L2 are recognized by TM1 and TM2, they will also be recognized by TM-.

The TM behaves as follows.




  1. String w from L is input into TM- It is initially on tape 1.

  2. The TM tape head 1 reads the string from left to right until the end.

  3. TM tape head 1 reads p-n characters from w, writes them to tape 2 (right to left) and overwrites those characters on tape 1.

  4. The TM alternately runs one transition of TM-1 on tape 1 and one transition of TM2 on tape 2. This is simulated on 2-tape TM by creating a set of 2-tape transition functions which allow the application of any TM-1 transition functions to tape 1 and the application of any TM-2 transition functions to tape 2.

  5. the TM accepts if TM1 and TM2 enter the former accept states.

Note: This is done non-deterministically. Therefore, in effect, the TM tries this for every way that w can be split. If it accepts for one of these tries, then the non-deterministic variation of a TM says that it accepts.

Supporting Proof 2:
Concatenation - L1 decideable and L2 decideable -> L1  L2 decideable
This is a little bit different from the above proof.

In order for L1oL2 to reject, the TM must know when all variations of w have been processed. Therefore, we will construct a TM that deterministically splits the input string w (of length p) into every possible combination of 2 pieces at point n where w1 consists of the first n characters of w and w2 consists of the last p-n characters of w.


Then, TM1 will be run on w1 and TM2 will be run on w2 for each of the possible splittings of w. This is accomplished by simulating them on separate tapes to ensure that the strings are not disturbed. TM- will accept w iff TM1 accepts w1 and TM2 accepts w2. TM-o will reject if each splitting w1,w2 of w were rejected by TM1 and TM2 respectively. Since the correct splitting of w into w1-w2 will be accepted by TM-, then w will be accepted by TM-. If one or both of w1 and w2 are rejected by TM1 and TM2 in all possible splittings, then w is rejected by TM-o. This means that w is not comprised of the concatenation of a string from L(TM2) and L(TM2). Therefore, TM-o decides the language L(TM-o).


--


The database is protected by copyright ©ininet.org 2016
send message

    Main page