Computer Sciences > GATE 2021 SET-1 > Turing Machines

Contributed by: Dr. Sarah Chen

Report Correct Copyright Claim

For a Turing machine M, denotes an encoding of M. Consider the following two languages.
L1 = { | M takes more than 2021 steps on all inputs}
L2 = { | M takes more than 2021 steps on some input}
Which one of the following options is correct?

A

Both L1 and L2 are decidable.

B

L1 is decidable and L2 is undecidable.

C

L1 is undecidable and L2 is decidable.

D

Both L1 and L2 are undecidable.

Check Answer

Explanation

Correct : a

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?

Question #23 Medium

Which operations on a binary search tree have O(h) complexity?

Question #31 Easy

Compare search complexities of sorted array vs balanced BST.

Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science