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

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.

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

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.

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.

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

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

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.

The statement   is always true.

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

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