Turing Machine

Which of the problems are unsolvable?

• a) Halting problem

• b) Boolean Satisfiability problem

• c) Both (a) and (b)

• d) None of the mentioned

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

• a) input tape

• b) head

• c) state register

• d) none of the mentioned

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

• a) Nested Turing machines

• b) Universal Turing machine

• c) Counter machine

• d) None of the mentioned

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

• a) does not halts

• b) halts

• c) goes into loop forever

• d) none of the mentioned

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

• a) Multi tape turing machine

• b) Multi track turing machine

• c) Register machine

• d) All of the mentioned

A turing machine operates over:

• a) finite memory tape

• b) infinite memory tape

• c) depends on the algorithm

• d) none of the mentioned

Which of the functions are not performed by the turing machine after reading a symbol?

• a) writes the symbol

• b) moves the tape one cell left/right

• c) proceeds with next instruction or halts

• d) none of the mentioned

Turing machine can be represented using the following tools:

• a) Transition graph

• b) Transition table

• c) Queue and Input tape

• d) All of the mentioned

Statement 1: Multitrack Turing machine.

Statement 2: Gamma is Cartesian product of a finite number of finite sets.

Which among the following is the correct option?

• a) Statement 1 is the assertion and Statement 2 is the reason

• b) Statement 1 is the reason and Statement 2 is the assertion

• c) Statement 1 and Statement 2 are independent from each other

• d) None of the mentioned

According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable language?

• a) Type 0

• b) Type 1

• c) Type 2

• d) Type 3