Register

Turing Machine

2,056 views
2 2 votes

Consider the following languages :
L1 : {< M, q >|M is a Turing Machine that visits state q on some input within 15 steps}.
L2 : {< M >|M is a Turing Machine, |M|< 200 where |M|is number of states in machine}.
Which of the following is correct ?

  • L1 is decidable but L2 is not decidable
  • L2 is decidable but L1 is not decidable
  • Both L1 and L2 is decidable
  • Neither L1 nor L2 is decidable

1 Answer

Best answer
6 6 votes
L1: ​​​​​​ Since steps are finite, configurations are also finite. Within finite configurations we can know whether that particular state has been encountered or not. Hence decidable.

L2: Number of states can be known just looking at encoding of inputted TM by/in UTM. Hence decidable.

Therefore, both decidable.
• selected by
Voting & Accepting an answer helps improve the community
← Previous · MATCHING NUMBERNext → · channel utilization
← Previous in category · Finite AutomataNext in category → · Regular Expression
Position:
Show:

Related questions

0 0 votes
0 0 answers
16
16 views
GO Classes asked 11 hours ago
16 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Consider the Turing machine $T$ with $Q=\{00,01,02,50,99\}$Input alphabet $\Sigma=\{1\}$, and tape alphabet $\Gamma=\{1,\square\}$. $q_0 = 00,q_{\mathrm{accept}}=99,q_{\...
0 0 votes
1 1 answer
21
21 views
GO Classes asked 12 hours ago
21 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Consider the Turing machine $M$ given below.Configurations use the format $:u\ q\ v$where $q$ is the current state, $u$ is the tape content to the left of the head, and t...
0 0 votes
1 1 answer
40
40 views
GO Classes asked 1 day ago
40 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Consider a Turing machine defined by the following transition rules, starting in state $q_0$:$$\begin{aligned} \delta(q_0,0)&=(q_0,0,R)\\ \delta(q_0,1)&=(q_1,0,R)\\ \delt...
1 1 vote
1 1 answer
50
50 views
GO Classes asked 1 day ago
50 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine Design
Consider the language, $L=\{a^nb^nc^n\mid n\geq1\}$This language is not context-free and requires a mechanism that can verify equality among three consecutive blocks.Whic...