Yioop - PHP Search Engine

Re: Practice Final Problem 10.

Originally Posted By: chinukamboj

Gobinder Kamboj
Raghav Baldania
Caterinal Petre

'''Originally Posted By: chinukamboj''' Gobinder Kamboj Raghav Baldania Caterinal Petre

Practice Final Problem 10

Originally Posted By: lambert

P = { | K(w) .
S on input :

Step 1. Construct a TM N using M and w
N on input x:
i. Simulate M on w. If M rejects w, N will halt and reject. When M accepts w go to Step ii
ii. Simulate the TM T on input x. When T accepts N will accept

Step 2. Run decider R on . When R accepts, S accepts. When R rejects, S rejects.
Notes: When M accepts w, L(N) = L(T) and when M rejects w, L(N) = L(T_empty).
So L(N) in P iff L(T) in P

S decides A_TM, and A_TM is undecidable therefore P is undecidable.

Hope this is worth at least 1 point this time

group
Lambert Fong
Gobinder Kamboj
Raghav Baldania
Caterinal Petre

'''Originally Posted By: lambert''' P = { | K(w) . S on input : Step 1. Construct a TM N using M and w N on input x: i. Simulate M on w. If M rejects w, N will halt and reject. When M accepts w go to Step ii ii. Simulate the TM T on input x. When T accepts N will accept Step 2. Run decider R on . When R accepts, S accepts. When R rejects, S rejects. Notes: When M accepts w, L(N) = L(T) and when M rejects w, L(N) = L(T_empty). So L(N) in P iff L(T) in P S decides A_TM, and A_TM is undecidable therefore P is undecidable. Hope this is worth at least 1 point this time group Lambert Fong Gobinder Kamboj Raghav Baldania Caterinal Petre

-- Practice Final Problem 10

I think the proposed solution would not receive much credit. So let me try to give a solution...

The property we are considering is:
P = { | K(w) , such that in P and not in P.
To see this, let M be the Turing Machine that rejects all strings. Then every string that it accepts
(which is none) has Kolmogorov complexity less than 10. On the other hand, let M' be
the machine that accepts all strings. From class we know that there are incompressible strings
of every length. So M' will accept one of these of length greater than 10 and so will not have the
property.

The second criteria for Rice's Theorem is that if two machine M1 and M2 accept the same language
then they either both have property P or both don't have property P.
Well, if M1 accepts only strings w of K(w) 10 then as M2 has the same language as M1, it too would
accept this string so neither M1 nor M2 would have property P.

So we have shown both of the conditions for Rice's theorem hold, therefore, we can conclude P is
undecidable.

I think the proposed solution would not receive much credit. So let me try to give a solution... The property we are considering is: P = { | K(w) , such that in P and not in P. To see this, let M be the Turing Machine that rejects all strings. Then every string that it accepts (which is none) has Kolmogorov complexity less than 10. On the other hand, let M' be the machine that accepts all strings. From class we know that there are incompressible strings of every length. So M' will accept one of these of length greater than 10 and so will not have the property. The second criteria for Rice's Theorem is that if two machine M1 and M2 accept the same language then they either both have property P or both don't have property P. Well, if M1 accepts only strings w of K(w) 10 then as M2 has the same language as M1, it too would accept this string so neither M1 nor M2 would have property P. So we have shown both of the conditions for Rice's theorem hold, therefore, we can conclude P is undecidable.