COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
infinite input tape
|
|
|
sensing read/write head
|
|
|
states and transition functions
|
|
|
none of the mentioned
|
Detailed explanation-1: -Explanation: Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. 3. Which of the following a turing machine does not consist of? Explanation: A state register is one which stores the state of the turing machine, one of the finitely many.
Detailed explanation-2: -A Turing machine consists of (a) a finite control, (b) one tape, representing the memory, that has a left margin and is divided into an infinite number of cells, and (c) a moving read/write head. The finite control can be in any one of a finite set Q of states.
Detailed explanation-3: -A Turing machine consists of an infinitely long tape, which has been divided up into cells. Each cell can contain either a 1, a 0, or an empty space. Above one cell of the tape is a head, which can either move left or right, and can read the symbols written in the cells.