Courses

# Test: The Language Of Turing Machine

## 10 Questions MCQ Test Theory of Computation | Test: The Language Of Turing Machine

Description
This mock test of Test: The Language Of Turing Machine for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: The Language Of Turing Machine (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: The Language Of Turing Machine quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: The Language Of Turing Machine exercise for a better result in the exam. You can find other Test: The Language Of Turing Machine extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

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

Solution:

A more mathematically oriented definition with the same universal nature was introduced by church and turing together called the Church-Turing thesis(formal theory of computation).

QUESTION: 2

### Which of the problems are unsolvable?

Solution:

Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

QUESTION: 3

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

Solution:

state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.

QUESTION: 4

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

Solution:

The 7-tuple definition of turing machine: (Q, S, G, d, q0, B, F)
where Q= The finite set of states of finite control
S= The finite set of input symbols
G= The complete set of tape symbols
d= The transition function
q0= The start state, a member of Q, in which the finite control is found initially.
B= The blank symbol
F= The set of final or accepting states, a subset of Q.

QUESTION: 5

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

Solution:

If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, since d is not defined at any pair (hA,X) or (hR,X) where hA = accept halting state and hR = reject halting state.

QUESTION: 6

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

Solution:

Inorder to describe formally what a Turing machine does, we need to develop a notation for configurations or Instantaneous descriptions(ID).

QUESTION: 7

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

Solution:

Many machines that might be thought to have more computational capability than a simple UTM can be shown to have no more power. They might compute faster or use less memory but cannot compute more powerfully i.e. more mathematical questions.

QUESTION: 8

Which among the following is incorrect for o-machines?

Solution:

In automata theory, an o- machine or oracle machine is a abstract machine used to study decision problems. The problem the oracle solves can be of any complexity class. Even undecidable problems like halting problems can be used.

QUESTION: 9

RASP stands for:

Solution:

RASP or Random access stored program is an abstract machine that has instances like modern stored computers.

QUESTION: 10

Which of the following is not true about RASP?

Solution:

In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.