Test: Turing Machine: RE, REC & Undecidability- 1

Test: Turing Machine: RE, REC & Undecidability- 1

Test Description

10 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Test: Turing Machine: RE, REC & Undecidability- 1

Test: Turing Machine: RE, REC & Undecidability- 1 for Computer Science Engineering (CSE) 2022 is part of Question Bank for GATE Computer Science Engineering preparation. The Test: Turing Machine: RE, REC & Undecidability- 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Turing Machine: RE, REC & Undecidability- 1 MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Turing Machine: RE, REC & Undecidability- 1 below.
Solutions of Test: Turing Machine: RE, REC & Undecidability- 1 questions in English are available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Test: Turing Machine: RE, REC & Undecidability- 1 solutions in Hindi for Question Bank for GATE Computer Science Engineering 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 Machine: RE, REC & Undecidability- 1 | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Turing Machine: RE, REC & Undecidability- 1 - Question 1

Which of the following functions are computable with Turning Machine?

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 1

All the above functions are total recursive functions. The total recursive functions are like recursive language. Turing machine halts on each and every input of recursive language. All of the above functions are turing computable.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 2

A countable union of countable sets is not

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 2

A countable union of countable set is countable. Countably infinite and denumerable are alternate names of countable sets.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 3

∑* over {0,1} and 2∑* are respectively,

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 3

Since ∑* is all the combinations of 0 and 1 and yet it is enumerable and belongs to the category of countably infinite. But 2∑* is the power set of ∑* which is infinite. By diagonalisation theorem, power set of any countably infinite set is always uncountable, hence 2∑*​ belongs to uncountably infinite set.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 4

Which of the following is undecidable?

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 4

According to the decision properties of the CFL and Regular languages, Equivalence of regular languages and emptiness of regular languages are decidable. Also the finiteness of CFL is decidable. For each of above property an algorithm exist. But no algorithm exist for checking the equivalence of the two context-free language.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 5

The statement "ATM can’t solve halting problem’’ is

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 5

ATM cannot solves the halting problem because it cannot find in finite time that for the given word the machine will halt or not.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 6

A PDA behaves like a TM when the number of auxiliary memory it has, is

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 6

Auxiliary memory = memory used by the machine for calculations or swappings.
PDA with 2 or more stacks is equivalent to TM.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 7

Halting problem/language is

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 7

Halting problem belongs to the TM. The language in which halting problem belongs is recursively enumerable i.e. RE. In this TM can’t tell in finite time the word is rejected or not. Although it can tell in finite time that the given word is accepted or not. Although REC can tell in finite time and comes into halt about both i.e.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 8

The statement is

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 8

The statement   is always true.

Test: Turing Machine: RE, REC & Undecidability- 1 - Question 9

If e1 and e2 are the RE denoting the languages Land L2 respectively, then which of the following is wrong?

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 9

Choice (c) is wrong since “φ” is a regular. In fact

*Multiple options can be correct
Test: Turing Machine: RE, REC & Undecidability- 1 - Question 10

Which of the following is in P?
PATH, HAMPATH, SAT, 3SAT

Detailed Solution for Test: Turing Machine: RE, REC & Undecidability- 1 - Question 10

SAT and PATH is in P while 3SAT and HAMPATH are NPC.

Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Turing Machine: RE, REC & Undecidability- 1 Page
In this test you can find the Exam questions for Test: Turing Machine: RE, REC & Undecidability- 1 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Turing Machine: RE, REC & Undecidability- 1, EduRev gives you an ample number of Online tests for practice

Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests