MCQ IN COMPUTER SCIENCE & ENGINEERING

COMPUTER SCIENCE AND ENGINEERING

THEORY OF COMPUTATION

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Statement:We can use the finite control of Turing machine to hold a finite amount of data.
A
True
B
False
C
Either A or B
D
None of the above
Explanation: 

Detailed explanation-1: -Correct choice is (a) Statement: We can use the finite control of turing machine to hold a finite amount of data. Explanation: The finite control not only contains state q but also three data, A, B, C. The following technique requires no extension to the Turing Machine model.

Detailed explanation-2: -We formalize Turing’s description as follows: A Turing machine consists of a finite program, called the finite control, capable of manipulating a linear list of cells, called the tape, using one access pointer, called the head. We refer to the two directions on the tape as ‘right’ and ‘left.

Detailed explanation-3: -The definition of Turing machines requires that the finite-state control unit have a finite number of states. It’s not allowed to have an infinite number of states. A machine that could have infinitely many states in its control could accept any language (unlike a Turing machine).

Detailed explanation-4: -Detailed Solution. Explanation: Option 1: It may halt and accept the input. This is not correct since Given a Turing machine over an input can halt and accept the input.

Detailed explanation-5: -A turing machine has finite number of states in its CPU. However the states are not small in number. Real computer consist of registers which can store values (fixed number of bits). 1 Crore+ students have signed up on EduRev.

There is 1 question to complete.