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

# Test: Turing Machine: RE, REC & Undecidability- 1 - Computer Science Engineering (CSE)

Test Description

## 10 Questions MCQ Test Theory of Computation - Test: Turing Machine: RE, REC & Undecidability- 1

Test: Turing Machine: RE, REC & Undecidability- 1 for Computer Science Engineering (CSE) 2023 is part of Theory of Computation 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) 2023 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 Theory of Computation for Computer Science Engineering (CSE) & Test: Turing Machine: RE, REC & Undecidability- 1 solutions in Hindi for Theory of Computation 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 Theory of Computation 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.

## Theory of Computation

18 videos|56 docs|44 tests
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

## Theory of Computation

18 videos|56 docs|44 tests