Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Tests > Test: Turing Machines & Undecidability- 2 - Computer Science Engineering (CSE) MCQ

Test Description

Test: Turing Machines & Undecidability- 2 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Turing Machines & Undecidability- 2 questions and answers have been prepared
according to the Computer Science Engineering (CSE) exam syllabus.The Test: Turing Machines & Undecidability- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam.
Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Turing Machines & Undecidability- 2 below.

Solutions of Test: Turing Machines & Undecidability- 2 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Turing Machines & Undecidability- 2 solutions in
Hindi for Computer Science Engineering (CSE) course.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Turing Machines & Undecidability- 2 | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions

Test: Turing Machines & Undecidability- 2 - Question 1

Let < M > be the encoding of a Turing machine as a string over {0, 1}. Let L = { < M > |M is a Turing machine that accepts a string of length 2014 }. Then, L is

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 1

Test: Turing Machines & Undecidability- 2 - Question 2

Which of the following problems is undecidable?

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 2

1 Crore+ students have signed up on EduRev. Have you? Download the App |

Test: Turing Machines & Undecidability- 2 - Question 3

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 3

Test: Turing Machines & Undecidability- 2 - Question 4

Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f^{-1} be also polynomial time computable. Which of the following CANNOT be true?

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 4

Test: Turing Machines & Undecidability- 2 - Question 5

Consider the following problem X.

Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q?

**Q. Which of the following statements about X is correct?**

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 5

Test: Turing Machines & Undecidability- 2 - Question 6

Consider the following decision problems:

(P1) Does a given finite state machine accept a given string

(P2) Does a given context free grammar generate an infinite number of stings

**Q. Which of the following statements is true?**

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 6

Test: Turing Machines & Undecidability- 2 - Question 7

Consider the following statements:

1. The complement of every Turning decidable language is Turning decidable

2. There exists some language which is in NP but is not Turing decidable

3. If L is a language in NP, L is Turing decidable

**Q. Which of the above statements is/are True?**

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 7

Test: Turing Machines & Undecidability- 2 - Question 8

Which of the following decision problems are undecidable

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 8

Test: Turing Machines & Undecidability- 2 - Question 9

Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 9

Test: Turing Machines & Undecidability- 2 - Question 10

Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 10

Test: Turing Machines & Undecidability- 2 - Question 11

For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 11

Test: Turing Machines & Undecidability- 2 - Question 12

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

L1' --> Complement of L1

L2' --> Complement of L2

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 12

Test: Turing Machines & Undecidability- 2 - Question 13

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.

S1 : L1 is recursive implies L2 is recursive

S2 : L2 is recursive implies L1 is recursive

**Q. Which of the following statements is true ?**

Test: Turing Machines & Undecidability- 2 - Question 14

Nobody knows yet if P = NP. Consider the language L defined as follows :

**Q. Which of the following statements is true ?**

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 14

Test: Turing Machines & Undecidability- 2 - Question 15

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

**Q. The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?**

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 15

Test: Turing Machines & Undecidability- 2 - Question 16

Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}

L1 = {< M, w, 1 > | M does not halts on w}

Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?

Test: Turing Machines & Undecidability- 2 - Question 18

For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

1. L1' (complement of L1) is recursive

2. L2' (complement of L2) is recursive

3. L1' is context-free

4. L1' ∪ L2 is recursively enumerable

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 18

Test: Turing Machines & Undecidability- 2 - Question 19

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y' reduces to W, and Z reduces to X' (reduction means the standard many-one reduction). Which one of the following statements is TRUE

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 19

Test: Turing Machines & Undecidability- 2 - Question 20

Consider the following types of languages:

L1 Regular,

L2: Context-free,

L3: Recursive,

L4: Recursively enumerable.

**Q. Which of the following is/are TRUE?**

I. L3' U L4 is recursively enumerable

II. L2 U L3 is recursive

III. L1* U L2 is context-free

IV. L1 U L2' is context-free

Detailed Solution for Test: Turing Machines & Undecidability- 2 - Question 20

Information about Test: Turing Machines & Undecidability- 2 Page

In this test you can find the Exam questions for Test: Turing Machines & Undecidability- 2 solved & explained in the simplest way possible.
Besides giving Questions and answers for Test: Turing Machines & Undecidability- 2, EduRev gives you an ample number of Online tests for practice

Download as PDF