Register

GO Classes DPP | TOC|DECIDABILITY

250 views
1 1 vote

A Reversible-Check TM (RCTM) does the following on input w :

  1. Simulates $\mathrm{M}$ on $\mathrm{w}$
     
  2. Attempts to reverse every step
     
  3. Accepts iff $\mathrm{M}$ halts on $\mathrm{w}$ and the entire computation is perfectly reversible
     

Define:

$\mathrm{L}_2=\{\langle\mathrm{M}, \mathrm{w}\rangle \mid \mathrm{M}$ halts on $\mathrm{w}$ and every step taken is reversible by the RCTM $\}$
 

Which statement correctly describes the decidability of $\mathrm{L}_2$ ?
 

  1. $\mathrm{L}_2$ is decidable
     
  2. $\mathrm{L}_2$ is undecidable
     
  3. $\mathrm{L}_2$ becomes decidable if $\mathrm{M}$ always halts
     
  4. $\mathrm{L}_2$ is regular

1 Answer

0 0 votes
Reduce HALT to $\mathrm{L}_2$ by constructing $\mathrm{M}^{\prime}$ that first simulates $\mathrm{M}$ on $\mathrm{x}$ and, only if that halting occurs, executes a carefully designed reversible halting computation; otherwise it never produces a reversible halting trace. Hence deciding $\mathrm{L}_2$ would decide HALT, so $\mathrm{L}_2$ is undecidable.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | TOC...Next → · GO Classes DPP | TOC...
← Previous in category · GO Classes DPP | TOC...Next in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

1 1 vote
1 1 answer
351
351 views
GO Classes asked Nov 20, 2025
351 views
GO Classes DPP | TOC|DECIDABILITY
Let $G$ be a CFG over alphabet $\{a, b, c\}$ with the restriction that every production must increase the total number of terminals in the string (i.e., whenever $\mathrm...
1 1 vote
2 2 answers
349
349 views
GO Classes asked Nov 20, 2025
349 views
GO Classes DPP | TOC|DECIDABILITY
A Paired Execution TM (PETM) takes input ( $\mathrm{M}, \mathrm{x}, \mathrm{k}$ ) and simulates $\mathbf{k}$ fresh independent runs of $\mathrm{M}$ on $\mathrm{x}$.Define...
5 5 votes
1 1 answer
255
255 views
GO Classes asked Nov 20, 2025
255 views
GO Classes DPP | TOC|CFG
Consider the CFG G:$\mathrm{S} \rightarrow \mathrm{aSb} \mid \mathrm{aTb}$$\mathrm{T} \rightarrow \mathrm{bT} \mid \varepsilon$Which of the following describes $\mathbf{L...
4 4 votes
1 1 answer
291
291 views
GO Classes asked Nov 20, 2025
291 views
GO Classes DPP | TOC|CFG
Consider the CFG:$\mathrm{S} \rightarrow \mathrm{aS}~|~\mathrm{Sb}~|~ \mathrm{aSb} ~|~ \mathrm{c}$Which of the following correctly describes a string in $\mathbf{L(G)}$ ?...