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

Theory of Computation and Compilers MCQ - Turing Machines

6 Which of the following is not primitive recursive but partially recursive?

7 Turing machine (TM) is more powerful than FMS (Finite State Machine) because

8 If f : N--> N. If L can be recoognized by a TM T, so that τ_T(n) ≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).

9 Let s is a step-counting function satisfying s(n) ≥ n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T ∈

10 Which of the following statements is false?

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.