edited by
12,494 views
46 votes
46 votes

It is undecidable whether:

  1. An arbitrary Turing machine halts after $100$ steps.
  2. A Turing machine prints a specific letter.
  3. A Turing machine computes the products of two numbers
  4. None of the above.
edited by

2 Answers

Best answer
63 votes
63 votes
  1. An arbitrary Turing machine halts after $100$ steps. DECIDABLE,we can run TM for $100$ steps and conclude that. (assuming "after $100$ steps" mean "exactly after $100$ steps")
  2. A Turing machine prints a specific letter. UNDECIDABLE, 
  3. A Turing machine computes the products of two numbers,UNDECIDABLE, Even though we can design a TM for calculation product of $2$ numbers but here it is asking whether given TM computes product of $2$ numbers,so the behavior of TM unknown hence,Undecidable.
edited by
25 votes
25 votes

Watch Complete Explanation of “Rice Theorem for Programs” here:

https://youtu.be/92BkNvlGNyY 

My answer is specifically for option C.

Option C : A Turing machine computes the products of two numbers.

The question is not asking if there exist a TM which can do the product of two numbers. Instead, it is asking that "Given any arbitrary TM, does it compute the product of two numbers ?"

This is undecidable. 

Rice’s Theorem says that testing any non-trivial semantic property of a Turing machine is undecidable, where a semantic property depends only on whether the machine halts or produces a particular output for each input, and not on the details of the computation, and a property is non-trivial if there is at least one machine for which it holds and at least one for which it doesn’t.

Property "computes the product of two numbers" is :

1. Semantic Property : 

Because a semantic property depends only on whether the machine halts or produces a particular output for each input, and not on the details of the computation. 

Here, in the problem of finding if "Given any arbitrary TM, does it compute the product of two numbers ?" , we only bother about producing a particular output for each input, and not on the details of the computation. i.e. we do not care how the computation internally goes on i.e. we do not care whether machine takes 400 steps Or machine has 30 states Or machine never moves to the left etc. 

2. Non-trivial property : 

Because a property is non-trivial if there is at least one machine for which it holds and at least one for which it doesn’t. Clearly, there are TMs which do not compute the product of two numbers and there are TMs which do compute product of two numbers. 

So, by Rice's theorem, testing any non-trivial semantic property of a Turing machine is undecidable. 


Note that Rice’s Theorem is only about inputs and outputs. There are non-semantic properties (like “does this machine run in polynomial time on input x?” or “are the first 3 bits of <M> 011?”) that are easily decidable even though they are non-trivial. It also only works because we consider machines that might not halt.

Rice Theorem for Programs, Complete Explanation

Watch the following playlist on “Undecidability and Countability”, Rice Theorem:

https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI

edited by
Answer:

Related questions

20 votes
20 votes
3 answers
1
makhdoom ghaya asked Nov 22, 2016
9,024 views
Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:$R_{1} \cap R_{2}$ is not regular.$R_{1} \cup R_{2}$ is regular.$\Sigma^{*}-R_{1}$ is regu...
27 votes
27 votes
2 answers
2
makhdoom ghaya asked Nov 22, 2016
16,672 views
Recursive languages are:A proper superset of context free languages.Always recognizable by pushdown automata.Also called type $0$ languages.Recognizable by Turing machine...
29 votes
29 votes
6 answers
4
makhdoom ghaya asked Nov 22, 2016
9,204 views
Indicate which of the following well-formed formulae are valid:$\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)...