TOC Similar ANS Qs

Question 1

General Formula for Rice’s Theorem:

Answer 1

Given a semantic property R (i.e - Purpleness) that holds in some cases but fails to hold in some cases, we ask whether the code WHILE(TRUE) that just hangs has the property

If it does, then there must be some other piece of code M that doesn’t. Now for any Plain code P of type VOID, let the F(P) be the CODE.
P
M
If P HALTS, then F(P) has the same semantics as M. so F(P) doesn’t satisfy R, just like M doesn’t. If P HANGS, then F(P) has the same semantics as WHILE(TRUE), so F(P) satisfies R, just like as WHILE(TRUE). To Summarize, P HALTS iff F(P) does not have the property R. So we have to reduced the HALTING PROBLEM to R. SO R is UNDECIDABLE

Doesn’t, then we apply the same argument the other way around

Question 2

Non-Regular Language

NOTE ! means doesn’t/ NOT in

For any specific scenario just change either L or the states

Answer 2

Let there be a DFA D that accepts Language L
L is Regular
x_0 is initial state of DFA

L = {a^mb^n|m,n ε N }

Consider x_n the state of D reached after reading a^n. State x_n accepts the word b^n, ∴ a^nb^n ε L

However if considering x_m the state of D reached after reading a^m, x_m will reject b^n where m < n and x_n != x_m ∴ a^nb^n !ε L

∴ the DFA D has infinitely many different states which contradicts its assumed finiteness
∴ L is not regular

Question 3

Rice’s Theorem?

Answer 3

If any sematic property of code holds in some cases and fails to hold in some cases it’s UNDECIDABLE.

Question 4

Church’s Theorem?

Answer 4

States if it cannot be solved by a Turing Machine then it cannot be solved Algorithmically

OR

Any Decision Problem on words that can be solved algorithmically can be solved by a Turing Machine

Question 5

Explain why some properties semantic properties is undecidable?

Answer 5

SAY WHY IT IS SEMANTIC PROPERTY?
- Semantic Property if it depends on the input-output behaviour

Then Give Example of how it Holds
(e.g A Program that sort list and returns it)
Then an example of How it fails to Hold
(e,g A program that just returns input list)

END WITH:
Therefore, by church’s theorem, the property of being a (SEMANTIC PROPERTY) is undecidable

Question 6

Church’s Thesis for Different Languages?

Answer 6

By Church’s thesis, this implies that there is no algorithm in any language that takes a program
and returns TRUE if its is a SEMANTIC PROPERTY & FALSE Otherwise.

Question 7

Define a SEMANTIC PROPERTY?

Answer 7

A property share between similar variants of a code

Question 8

What Sequence Equation gives total NO. of steps?

Answer 8

(n(a_0+a_n))/2

a_0 is first term & a_n is last term

OR

(n(2a+(n-1)*d))
a is the first term

Question 9

SHOW/PROVE that PROPERTY is UNDECIDABLE:

Note:
NON TRIVAL SEMANTIC PROPERTY MUST BE CHANGED WITH CONTEXT OF QUESTION i.e purpleness

Answer 9

We REDUCE Halting Problem to
(FOR PLAIN NULLARY PROGRAM)
the NON TRIVIAL SEMANTIC PROPERTY

Let P be a plain program:
void P(){ }
Let P̃ be a program that halts given by :
void P̃(){…}
Let M be a program that hangs given by:
void M(){while(true)}
Let F(P) be given by:
void P(){P̃}

THERE ARE 2 CASES:
[1] M HAS NON TRIVIAL SEMANTIC PROPERTY& P̃ DOESN’T
- If P halts, F(P) doesn’t have the Non-Trivial Semantic Property and F(P) is Semantically Equivalent P̃

• If P hangs, F(P) does have the Non-Trivial Semantic Property and F(P) is Semantically Equivalent M which has the Property

[2] M DOESN’T HAVE THE NON TRIVIAL SEMANTIC PROPERTY & P̃ DOES
- If P halts, F(P) does have the Non-Trivial Property
F(P) is Semantically Equivalent P̃ which has the property

• If P hangs, F(P) doesn’t have the Non-Trivial Property and F(P) is Semantically Equivalent M which has the Property

The Halting Problem is UNDECIDABLE, the NON TRIVIAL SEMANTIC PROPERTY is UNDECIDABLE

Question 10

What does it mean for a Turing Machine to execute in polytime?

Answer 10

Means there Exists numbers N,C & k such that if the length n of the input is at least N, then the machine terminates in time <= Cn^k

Question 11

Define NP-Complete :

Answer 11

Every Problem in NP can be reduced to it in polytime

Question 12

Define Semantic:

Answer 12

For any two semantically equivalent pieces of code (Have the same externally observable behaviour) if one has the property p, then so does the other

Question 13

Define Non-Trivial

Answer 13

Sime piece of code has the property P and some piece of code fails to have the property P

Question 14

What does it mean to Reduce P to Q

Answer 14

Reduce P to Q:
Means if P is undecidable, then Q is undecidable