Skip to main content
Computer Science

Return to Answer

added 73 characters in body
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

For the purposes of this proof we will assume that $USELESS_{TM}$$\mathrm{USELESS}_{\mathrm{TM}}$ is decidable to display a contradiction.

Create TM $R$ that does the following:

  • Converts TM $M$ to a pushdown automata $P$ with a relaxed stack (ie. no LIFO requirement). This is equivalent to a directed graph detailing the transition between $M$'s states.
  • Mark the start state of $P$.
  • From the start state commence a breadth-first search along each outbound edge marking each unmarked node.
  • When the search terminates, if there are any unmarked nodes which match $q$, accept; otherwise reject.

Then create TM $S$ = "On input $<$$M$, $q$$>$

  1. Create TM $R$ as shown above.
  2. Run $q$ on $R$.
  3. If $R$ returns accept, accept; if $R$ rejects, reject"

Thus, if $R$ is a decider for $USELESS_{TM}$$\mathrm{USELESS}_{\mathrm{TM}}$ then $S$ is a decider for $A_{TM}$$A_{\mathrm{TM}}$ (the acceptance problem). Since $A_{TM}$$A_{\mathrm{TM}}$ is proven to be undecidable (see Michael Sipser Theory of Computation Theorem 4.11 on page 174), we have reached a contradiction. Therefore, the original hypothesis is incorrect and $USLESS_{TM}$$\mathrm{USELESS}_{\mathrm{TM}}$ is undecidable.

For the purposes of this proof we will assume that $USELESS_{TM}$ is decidable to display a contradiction.

Create TM $R$ that does the following:

  • Converts TM $M$ to a pushdown automata $P$ with a relaxed stack (ie. no LIFO requirement). This is equivalent to a directed graph detailing the transition between $M$'s states.
  • Mark the start state of $P$.
  • From the start state commence a breadth-first search along each outbound edge marking each unmarked node.
  • When the search terminates, if there are any unmarked nodes which match $q$, accept; otherwise reject.

Then create TM $S$ = "On input $<$$M$, $q$$>$

  1. Create TM $R$ as shown above.
  2. Run $q$ on $R$.
  3. If $R$ returns accept, accept; if $R$ rejects, reject"

Thus, if $R$ is a decider for $USELESS_{TM}$ then $S$ is a decider for $A_{TM}$ (the acceptance problem). Since $A_{TM}$ is proven to be undecidable (see Michael Sipser Theory of Computation Theorem 4.11 on page 174), we have reached a contradiction. Therefore, the original hypothesis is incorrect and $USLESS_{TM}$ is undecidable.

For the purposes of this proof we will assume that $\mathrm{USELESS}_{\mathrm{TM}}$ is decidable to display a contradiction.

Create TM $R$ that does the following:

  • Converts TM $M$ to a pushdown automata $P$ with a relaxed stack (ie. no LIFO requirement). This is equivalent to a directed graph detailing the transition between $M$'s states.
  • Mark the start state of $P$.
  • From the start state commence a breadth-first search along each outbound edge marking each unmarked node.
  • When the search terminates, if there are any unmarked nodes which match $q$, accept; otherwise reject.

Then create TM $S$ = "On input $<$$M$, $q$$>$

  1. Create TM $R$ as shown above.
  2. Run $q$ on $R$.
  3. If $R$ returns accept, accept; if $R$ rejects, reject"

Thus, if $R$ is a decider for $\mathrm{USELESS}_{\mathrm{TM}}$ then $S$ is a decider for $A_{\mathrm{TM}}$ (the acceptance problem). Since $A_{\mathrm{TM}}$ is proven to be undecidable (see Michael Sipser Theory of Computation Theorem 4.11 on page 174), we have reached a contradiction. Therefore, the original hypothesis is incorrect and $\mathrm{USELESS}_{\mathrm{TM}}$ is undecidable.

Source Link
BrotherJack
BrotherJack
  • 1.1k
  • 1
  • 10
  • 23

For the purposes of this proof we will assume that $USELESS_{TM}$ is decidable to display a contradiction.

Create TM $R$ that does the following:

  • Converts TM $M$ to a pushdown automata $P$ with a relaxed stack (ie. no LIFO requirement). This is equivalent to a directed graph detailing the transition between $M$'s states.
  • Mark the start state of $P$.
  • From the start state commence a breadth-first search along each outbound edge marking each unmarked node.
  • When the search terminates, if there are any unmarked nodes which match $q$, accept; otherwise reject.

Then create TM $S$ = "On input $<$$M$, $q$$>$

  1. Create TM $R$ as shown above.
  2. Run $q$ on $R$.
  3. If $R$ returns accept, accept; if $R$ rejects, reject"

Thus, if $R$ is a decider for $USELESS_{TM}$ then $S$ is a decider for $A_{TM}$ (the acceptance problem). Since $A_{TM}$ is proven to be undecidable (see Michael Sipser Theory of Computation Theorem 4.11 on page 174), we have reached a contradiction. Therefore, the original hypothesis is incorrect and $USLESS_{TM}$ is undecidable.