CS 381 HW #12 SOLUTIONS

1. (30.1 , P 344 #111)
(a)
L={M | L(M) has atleast 481 elements }


L is r.e . Here is an english description of a TM M , such that
L(M) =L
input of M is a TM M1
outputs "Yes" if M1 is in L
Let the strings be arranged in canonical order. Canonical ordering
of strings over {0,1} is as follows :
e, 0, 1 , 00, 01, 10, 11, 000 , 001, 010, 011, 100, 101, 110 ,
111, 0000, ...
(e is epsilon )
i.e all strings of length i are places before all strings of length (i+1)
therefore string 1 is "e", string 5 is "01", string 12 is "100" ....

count=0;
k=1;
loop
for all possible positive integer solutions to i+j =k (k is known,
i & j are variables) do
simulate M1 on i^th string for j steps.
if M1 halts on the i^th string within those j steps then
begin
++count;
if (count == 481) then
begin
Output "Yes"
exit
end
end
++k;
end
forever

The key step is "i+j=k" . You have to convince yourself that this indeed
works. It is a good idea to do a trace of the above code for a few iterations
to understand what is going on.

(b)
L={M | L(M) has atmost 481 elements }
L is not r.e.  
Proof : On the contrary assume L is r.e. i.e there is a TM M such that
L(M)=L. i.e if M1 is a TM s.t L(M1) has atmost 481 elements, then M
on input M1, halts & accepts M1.

We will solve the halting problem using M. Let (M1,x) be an instance
of the halting problem. Construct  M2 as follows

M2 ignores is input y and simulates M1 on x. if M1 halts on x, then
M2 accepts y else loops forever on y.

Now it should be clear that M2 halts on all inputs iff M1 halts on x. i.e
L(M2) has infinite elements if M1 halts on x else is empty. Hence M2 is
in L iff M1 doesnt halt on x. 

Hence if we feed M2 to M & M says "Yes"  it means M1 doesnt halt on x.
Conversely if M1 doesnt halt on x, then M on M2 will output "Yes". Hence
we have shown that the complement of halting problem is r.e which is
not possible. Hence assumption L is r.e is false.


2. (30.2 , P 344 #112)

L={M | M halts on all inputs of lengths less than 481 }

L is r.e . Here is an english description of a TM M , such that
L(M) =L

input of M is a TM M1
outputs "Yes" if M1 is in L
Let the strings be arranged in canonical order. Let there be "k" strings
with lengths <= 481.

for i=1 to k do
begin
M simulates M1 on string i
If M1 halts on string i, then M proceeds to check the response of
M1 on the (i+1)st string.
end
Output "Yes"

complement(L) is not r.e . This is because L is not recursive.
Proof of L is not recursive :
On the contrary assume L is recursive. That is a a TM M s.t
L(M)=L and M halts on all inputs. i.e

input of M is a TM M1
outputs "Yes" if M1 is in L
o/w "No" 
i.e in either case M gives a Yes or No answer and halts.

We will solve the halting problem using M. Let (M1,x) be an instance
of the halting problem. Construct  M2 as follows

M2 ignores is input y and simulates M1 on x. if M1 halts on x, then
M2 accepts y else loops forever on y.

Now it should be clear that M2 halts on all inputs iff M1 halts on x. In
particular M2 halts on all inputs of length <= 481 iff M1 halts on x.

Now input M2 to M. if M says "Yes" it implies M1 accepts x and "No" means
M1 doesnt halt on x. Hence we have solved the halting problem which is
not possible. Hence our assumption that L is recursive is false.

3. (31.1 , P 310 #1)
We know that if a TM halts, it has to be either in accept state (t)
or reject state (r).

Suppose the given language is decidable. i.e there a TM M which does the 
following

M takes in as input a TM M1 and a state q of M1
outputs "Yes" if M1 reaches q on some input
o/w "No" (i.e M either says "yes" or "no" and halts)

We can solve the halting problem as follows. Let (M1,x) be an instance
of the halting problem. Construct M2 as follows

M2 ignores is input y and simulates M1 on x. if M1 halts on x, then M2
goes to its accept state "t" and halts.

It should now be clear that M2 on any input y reaches state "t" iff
M1 halts on x.

Feed in M2, t to M. If M says "Yes" it means M1 halts on x & "No" means
M1 doesnt halt on x and thus we have solved the halting problem which is
not possible. Hence our assumption is wrong.


4. (31.2 , P 310 #2)
Suppose the given language is decidable. i.e there a TM M which does the 
following

M takes in as input  TMs M1 and M2
outputs "Yes" if L(M1)==L(M2)
o/w "No" (i.e M either says "yes" or "no" and halts)

We can solve the halting problem as follows. Let (M1,x) be an instance
of the halting problem. Construct M2  as follows

if y is different from x then
M2(y) = M1(y) i.e M2 simulates M1 on y. if M1 accepts y , M2 accepts y and
if M1 doesnt accept y, M2 doesnt accept y.
and M2 accepts x.
L(M1) == L(M2) iff M1 accepts x. WLOG, we can assume that M1 halts on x
iff M1 accepts x.

Feed in M1, M2 to M . If M says "yes" it means M1 halts on x & "no" means
M1 doesnt halt on x and thus we have solved the halting problem which is
not possible. Hence our assumption is wrong.


5. (31.3 , P 343 #7)

No. By Rice's theorem.
Justification : L(M)=rev(L(M)) is non-trivial.
Consider TM M1 which accepts everything. Clearly L(M1)=rev(L(M1)). 
Consider TM M2 which accepts only "10" and rejects everything else.
L(M2) != rev(L(M2))
Hence can use Rice's theorem.