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 (CSCI6050)
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 onetoone and onto.
A function is onetoone 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_{1}, 2 is mapped to K_{2}, 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 feven(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 nth bit of the binary representation of x is flipped to the oppisite of the nth 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_{AB }is 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 wA producing output w’B.
Then we simulate TM_{BC} on input w’B producing output w’’C.
Since f_{AB} and f_{BC }are 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 wA 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 Turingrecognizable 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_{1}w_{n} simultaneously.

One step on w_{1}, w_{2} ... w_{n}

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 Turingrecognizable 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_{0} is a TM that we which to decide if L(M_{0}) = 0.

Using M_{0} and M_{2 }(where M_{2 } 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_{0}) and (M_{2}) 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 Turingrecognizable 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_{0}) o L(M_{2}) 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 Turingrecognizable 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 TMUnion 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 nondeterministically 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 pn 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 nondeterministic splitting of w into w1w2 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 nondeterministic splitting of w is an important part of this machine description.
w of length p will be nondeterministically 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 pn 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 w1w2 strings contained in L1 and L2, and therefore may not be recognized by TM, one of these combinations will be w1w2.
Implementation:
This setup can be simulated on a 2tape 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 2tape transition functions which allow the simultaneous application of any TM1 transition functions (on tape 1) and the application of any TM2 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 qaccept(TM1) and qaccept(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 pn 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 TM1 on tape 1 and one transition of TM2 on tape 2. This is simulated on 2tape TM by creating a set of 2tape transition functions which allow the application of any TM1 transition functions to tape 1 and the application of any TM2 transition functions to tape 2.

the TM accepts if TM1 and TM2 enter the former accept states.
Note: This is done nondeterministically. 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 nondeterministic 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 pn 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. TMo will reject if each splitting w1,w2 of w were rejected by TM1 and TM2 respectively. Since the correct splitting of w into w1w2 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 TMo. This means that w is not comprised of the concatenation of a string from L(TM2) and L(TM2). Therefore, TMo decides the language L(TMo).

