Avatto > UGC NET COMPUTER SCIENCE > PRACTICE QUESTIONS > Theory of Computation and Compilers > Turing Machines

Theory of Computation and Compilers MCQ - Turing Machines

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

17 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

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

19 A total recursive function is a

20 The running time T (n), where 'n' is input size of a recursive algorithm, is given as
T (n) = c + T (n - 1), if n > 1
= d, if n ≤ 1
The order of the algorithm is

Recuesivelt applying the relation, we get
T( n + 1 ) = C ( n - 1 ) + T (1)
= C ( n - 1 ) + d
Hence order is n.

Your Progress

0%

Start Practising!

You've answered 0 of 22 questions in this topic.

Practice Spotlight

Build momentum in Turing Machines

Start with a short question set, review every explanation, and revisit difficult questions before moving ahead.

Day 7 / 10

Global Spotlight

Challenge Your Accuracy

Strong work at 0% accuracy. Attempt the hardest Turing Machines questions and explain why every incorrect option is wrong.

Day 1 / 10

Question Spotlight

Question:

Consider an alternate Turing machine model, in which there is an input tape on which the tape head can move in both directions but cannot write, and one…

A. DSpace (1+ ⌈log₂ (n + 1 ⌉). (⌈ x ⌉) means the smallest integer greater than or equal to x.
B. DSpace (1+ ⌈log₂n⌉)
C. DSpace ( 1+ ⌈ log₂ n²⌉)
D. none of these

Correct answer: A

Click to view the complete question details

Day 7 / 10 Open this question

Community Insight

Based on 39 saved attempts

Most Attempted TopicBasic Of Compiler Design
Most Challenging TopicBasic Of Compiler Design
Average Accuracy87%

Featured Question

(Based on recent community answers)

Q. #25436New

Consider an alternate Turing machine model, in which there is an input tape on which…

Try This Question →

This Week's Challenge

Complete 20 questions and set the community benchmark!

0 / 20 Start Challenge →

Why Practice with Avatto?

High Quality MCQsExam-focused questions with accurate answers

Detailed ExplanationsStep-by-step explanations to enhance learning

Latest Exam PatternBased on updated syllabus and pattern

Performance AnalyticsTrack performance and improve weak areas

100% Free PracticePractice unlimited questions for free

Forgot your password?

I agree with the Terms.