TOC_CO4&CO5

A Turing machine that is able to simulate other Turing machines:

• Nested Turing machines

• Universal Turing machine

• Counter machine

• None of the mentioned

Which of the problems are unsolvable?

• Halting problem

• Boolean Satisfiability problem

• Halting problem & Boolean Satisfiability problem

• None of the mentioned

Which of the following a Turing machine does not consist of?

• input tape

• head

• state register

• none of the mentioned

The value of n if Turing machine is defined using n-tuples:

• 6

• 7

• 8

• 5

If d is not defined on the current state and the current tape symbol, then the machine ______

• does not halts

• halts

• goes into loop forever

• none of the mentioned

Statement: Instantaneous descriptions can be designed for a Turing machine. State true or false:

• true

• false

Which of the following are the models equivalent to Turing machine?

• Multi tape Turing machine

• Multi track Turing machine

• Register machine

• All of the mentioned

A language L is said to be Turing decidable if:

• recursive

• TM recognizes L

• TM accepts L

• recursive & TM recognizes L

The class of recursively enumerable language is known as:

• Turing Class

• Recursive Languages

• Universal Languages

• RE

Which of the following statements are false?

• Every recursive language is recursively enumerable

• Recursively enumerable language may not be recursive

• Recursive languages may not be recursively enumerable

• None of the mentioned