Exams › GATE › Technical
For a Turing machine M, ⟨M⟩ denotes an encoding of M. Consider the following two languages.
L1 = {⟨M⟩ | M takes more than 2021 steps on all inputs}
L2 = {⟨M⟩ | M takes more than 2021 steps on some input}
- L1 is decidable and L2 is undecidable
- L1 is undecidable and L2 is decidable
- Both L1 and L2 are decidable
- Both L1 and L2 are undecidable
Correct answer: Both L1 and L2 are undecidable
Solution
Both languages L1 and L2 are undecidable because they involve determining the behavior of Turing machines over all inputs or some inputs, which relates to the Halting Problem. Specifically, there is no algorithm that can universally decide whether a Turing machine will exceed a certain number of steps for all or any input.
Related GATE Technical questions
- The decimal number 42 is represented in base 3 as 1120. What is the hexadecimal representation of 42?
- Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery.
- Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127.
S: 1 E: 10000001 F: 11100000000000000000000
Here S, E and F denote the sign, exponent and fraction components of the floating point representation. The above representation (rounded to 2 decimal places) is
- The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key:
empAge(empNo, age)
Consider the following relational algebra expression:
π_empNo, age (σ_age > age1 (ρ_empNo1, age1 (empAge)))
What does it generate?
- Let G be a group of order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?
- The three-dimensional state of stress at a point is given by σ = [[10, 0, 0],[0, 40, 0],[0, 0, 0]] MPa. The maximum shear stress at the point is
⚔️ Practice GATE Technical free + battle 1v1 →