849 views
1 votes
1 votes
Which of the following problems is(are) decidable ?

I.    Given a (finite) string W, is W a prefix of the decimal expansion of $\pi$

II.   Given a Program and an input, is the programs output the decimal expansion of $\pi$

III.  Given a Program and an input a prifix of the decimal expansion of $\pi$, the prorams output

      always the same for every prifix

(A). I only

(B). II only

(C). I and II only

(D). III only

2 Answers

1 votes
1 votes
A is decidable bcz we can write an algo to TM that will either accept or reject,will never halt.

B is not decidable bcz the given program may go to infinite loop and same for C ie. the given program may go to infinite loop on some prefix .So A
1 votes
1 votes

1)Yes, it is decidable for string W. As, for a given string, if it is finite, it is enough to tell it is decidable. But if we think it's prefix, yes number of prefix in a finite string is countable. So, 'yes' answer possible here, but we cannot say 'no' for any given string. Hence it is partially decidable or semidecidable.

2) It is undecidable. What the string actually telling? it is asking if input= output? So, we cannot decide if both input and output strings are equal or not.Equality doesnot imply decidable property.Hence, undecidable

3)For every input prefix there is one output. Which means output doesnot depend on input. Say for output phi, there are inputs phi, 0,1,11,001.............. Here nonmonotonic property of Rice Theorem satisfies. Hence it is not even partially decidable.

Related questions

3 votes
3 votes
0 answers
1
Shreya Roy asked Nov 18, 2016
366 views
There is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products, left recursion,). What would be the max number of...
3 votes
3 votes
2 answers
4
Shreya Roy asked Nov 18, 2016
1,008 views
Let L = {xy | xwy L1, |x| = |w| = |y|}. Then L is(L1 is regular)(A). Regular(B). Non regular(C). May be regular(D). None