Larry Bush November 15, 2001

Download 55.85 Kb.

Date	31.01.2017
Size	55.85 Kb.
	#12902

Supporting Proofs

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 INFINITE_DFA = { : A is a finite automaton and L(A) is an infinite language.}

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

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.

Mark the start state of A.

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

Mark any state that has a transition coming into it from any of the marked state(s).
Loop Test – Go through each newly marked state - If the current state was already marked (we have found a loop) go to step 6.
Stop Test – If no new state has been marked continue with step 5, otherwise, go to step 2.
Reject (this DFA is acyclic – no loops)

- Does Cycle Lead To Accept?

Simulate a stack and push the list of marked states to it.
Add the current state(s) to the cycle state(s).
If any of the cycle state(s) is an accept state, then D accepts.
Add any state that has a transition coming into it from one of the cycle states to the list of cycle states.
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).
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, INFINITE_DFA is decidable.

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

Prove that the set K of all subsets of N_even 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 N_even 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 K_n = 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 N_even.

Each element of K is a subset of N_even.

f(n) maps an element of N an element of K that we identify as K_n where 1 is mapped to K₁, 2 is mapped to K₂, 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 N_even.

Then one element of x is an element of N_even.
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 N_even that we are addressing, we use the correspondence N to N_even which is f-even(n) = 2n. Then, for a given n, we determine whether f(n) (which is K_n) contains the element 2n. If it does, we construct x so that it does not.
If K_n 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 K_n contains the element 2n then x does not contain the element 2n.

if K_n 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:

x_n  N_even (each element of x is an element of N_even)

x_n = ~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)

x_n  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 N_even 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 :

mapping reducibility is transitive
A <_m B
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 f_AB

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

and
if B <_m C by f_BC

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

Then by definition the relation is transitive because if A <_m B via function f_AB and

B <_m C via function f_BC, then A <_m C via the composed function f_BC of f_AB:
f_BC( f_AB(w) )

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

First of all we know that if A <_m B via function f_AB and

B <_m C via f_BC then f_AB and f_BC are by definition Turing computable.

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

We will call TM_BC the Turing Machine that computes f_BC on an input.

Then TM_BC(AB)works as follows:

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

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

Since f_AB and f_BCare computable functions.

Then by the above description;

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

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

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

Therefore, TM_BC(AB) is a computable function.
Therefore, A <_m C via the reduction function TM_BC(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

Generate all strings (w_n) over E of length 3.
Run M on w₁-w_n simultaneously.
1. One step on w₁, w₂ ... w_n
2. If one of w_n 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 w_n 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 EQ_CFG = { : G1 and G2 are CFGs and L(G1) = L(G2)}

Show that EQ_CFG is undecidable.

To prove that EQ_CFG 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:

Construct a CFG G_ALL where L(G_ALL) = all possible strings over E (E*).
Run the decider for EQ_CFG on < G_?, G_ALL >.
If EQ_CFG accepts, then M accepts.
If EQ_CFG 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:
D_{Accept_Two} is a TM that decides Accept_Two.
D_{Accept_Two} takes as its input and determines if is in the language Accept_Two or not.
Proof: We let TM D_{Accept_Two} decide Accept_Two and construct the TM ‘S’ to decide E_TM as follows.
S = “On input 0> where M₀ is a TM that we which to decide if L(M₀) = 0.

Using M₀ and M₂(where M₂ is a TM that accepts all strings of length 2) we can construct a new TM ‘M_0o2‘ which accepts the concatenation of L(M₀) and (M₂) and M2. Therefore, if M is E_TM 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.)

Apply D_{Accept_Two} to < M_0o2>
if D_{Accept_Two} accepts
then S accepts
if D_{Accept_Two} rejects
then S rejects

If D_{Accept_Two} decides M_0o2, then S decides E_TM because L(M_0o2) = L(M₀) o L(M₂) and therefore decides if 0> is in language E_TM.

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.

String w from L is input into TM- It is initially on tape 1.
The TM tape head 1 reads the string from left to right until the end.
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.
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.
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).

Download 55.85 Kb.

Share with your friends: