Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

76) Universal TM influenced the concept of

Answer is:

all of these

Explanation:

Universal TM influenced the concept of
* stored program computers
* interpretative implementation of programming language
* computability

77) Number of external states of a UTM should be at least

Answer is:

2

78) The statement, “A TM can’t solve halting problem” is

Answer is:

TRUE

79) If there exists a TM which when applied to any problem in the class, terminates, if correct answer is yes and may or may not terminate otherwise is called

Answer is:

partially solvable

80) Given a Turing machine T and a step-counting function f, is the language accepted by T in Time(f) ? This decision problem is

Answer is:

unsolvable

13
14
15
16
17
18
19