Explore topic-wise InterviewSolutions in .

The correct answer is (a) R

To explain: R is the set of all recursive languages, a class of DECISION problems solvable by TURING machines. Although, R is ALSO used for the class RP.

The correct CHOICE is (a) RECURSIVE

Explanation: We can refer to languages as ‘recursive’ and problems as ‘decidable’. If a LANGUAGE is not recursive , then we CALL the problem expressed by that language UNDECIDABLE.

The CORRECT choice is (c) Both (a) and (b)

Easiest explanation: The language accepted by Turing machines are called RECURSIVELY ennumerable (RE), and the subset of RE LANGUAGES that are accepted by a turing MACHINE that always halts are called RECURSIVE.

The correct choice is (a) decidable

The BEST explanation: A LANGUAGE is recursive if there exists a turing machine such that it HALTS i.e. accepts if the INPUT belongs to the language else rejects. It is better CALLED Turing decidable language.

The correct answer is (d) NONE of the mentioned

Easiest explanation: EXAMPLE: Does a GRAPH G has a HAMILTON cycle?

=>Each undirected graph is an instance of Hamilton cycle PROBLEM.

Correct option is (a) tractable

Easy explanation: A problem is called INTRACTABLE IFF there is an EFFICIENT (i.e. polynomial time) algorithm that SOLVES it. A problem is called intractable iff there exists no efficient algorithm that solves it.

Correct choice is (a) DECIDABLE

To ELABORATE: An ALGORITHM is a TM that HALTS on all INPUTS,accepted or not. Putting other way, decidable problems are recursive languages.

The correct OPTION is (a) yes

The best I can EXPLAIN: Yes, it can be. There exists a THEOREM and as WELL as its proofwhich supports the assertion.

Correct choice is (a) Statement: For any TURING machine, the input alphabet is restricted to {0,1}.

To EXPLAIN I would say: When turing machines are CODED as Binary strings, we are restricted to take any input alphabet except {0,1}.

The correct OPTION is (a) polynomial

Easiest EXPLANATION: Example: Runtimes of EFFICIENT algorithms

O(n), O(NLOGN), O(n^3log2^n)

Runtimes of INEFFICIENT algorithms

O(2^n), O(n!)

Correct choice is (C) Both (a) and (B)

To explain: In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this PROGRAM can be IMPLEMENTED asa program.

Right choice is (c) BOOLEAN

The BEST explanation: The DECISION problem requires checking of input (string) has some property or not. That is a string to boolean TRANSACTION.

The correct option is (d) The first order theory of the natural number with addition, multiplication, and equality

To explain I would say: Tarski and Mostowski in 1949, established that the first order theory of natural NUMBERS with addition, multiplication, and equality is an undecidable theory. OTHERS MENTIONED are decidable THEORIES.

The correct choice is (d) All of the mentioned

To elaborate: ACCORDING to Rice’s THEOREM, if there exists atleast ONE computable FUNCTION in a particular class C of computable functions and another computable function not in C then the problem DECIDING whether a particular program computes a function in C is undecidable.

The correct CHOICE is (b) decidable

Easy EXPLANATION: Decidability refers to the decision problem and existence of a EFFECTIVE method for DETERMINING membership, and return TRUE and false accordingly rather that going into a loop forever.

Right CHOICE is (a) POST Correspondence Problem

Explanation: PCP or Post Correspondence PROBLEMIS an undecidable decision problem.

The correct ANSWER is (c) Both (a) and (b)

EXPLANATION: Diagonalization is a TECHNIQUE we use for the following OPERATIONS:

a) To find a non recursively ennumerable language.

b) To prove undecidablility ofhalting problem.

Correct option is (c) undecidable

Explanation: Rice’s THEOREM STATES that ‘Any NON TRIVIAL PROPERTY about the language recognized by a turing machine is undecidable’.

The CORRECT OPTION is (a) Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first STRING on each list.

The best explanation: The MPCP is : GIVEN lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..WIR = x1xi1xi2…xir?

The correct CHOICE is (B) No

The explanation: Any RECURSIVE ennumerable LANGUAGE is not closed under complementation.

Correct choice is (C) Both (a) and (B)

The explanation is: There are two types of TMs on the basis of halting: Recursive and RECURSIVELY Ennumerable(TM MAY or may not halt,could loop forever).