0
$\begingroup$

L = {w#x | w,x ∈{0,1}∗ and Turing Machine Mw with input x visits every non-end state at least once}

I believe this problem is undecidable.

My proof would consist of me reducing L to a Halting Problem; however, the structure of these proofs seem incosistent and inconclusive. I would appreciate if I could have some constructive feedback.

My understanding of the proof:

  1. Create R which decides L
  2. Construct algorithm S, which decides Atm (which we reduce to L)
  3. Contradiction because Atm is undecidable

This is the skeleton to most Turing Machine dicidibility related proofs I have read on the internet.

$\endgroup$
  • $\begingroup$ I suggest reviewing other similar proofs that were given in class. $\endgroup$ – Yuval Filmus Jun 26 '17 at 15:32
  • $\begingroup$ unfortunately as i said the structure of these proofs seem incosistent and inconclusive $\endgroup$ – Peter Bangert Jun 26 '17 at 15:53
  • 1
    $\begingroup$ You need to reduce the halting problem to $L$: you're saying that, if I could decide $L$, I could decide the halting problem for Turing machines. You seem to know what you need to do, so go ahead and do it: figure out a way of deciding the halting problem using a supposed ability to decide $L$. $\endgroup$ – David Richerby Jun 26 '17 at 17:44
  • $\begingroup$ "reducing L to a Halting Problem" does not allow you to state anything about the decidability of $L$. You need to reduce in the opposite direction. $\endgroup$ – chi Jun 26 '17 at 18:04
  • $\begingroup$ @chi, reduction to Halting problem leads to undecibility of initial problem, which is needed to be shown. $\endgroup$ – rus9384 Jun 26 '17 at 20:47
1
$\begingroup$

It's undecidable because you could use it to decide halting.

Because the number of states in a Turing machine is finite you can enumerate all $2^n$ combinations of possible non-end states. Run the algorithm against all of them.

If the algorithm returns yes for a group of states that includes an original end state then the machine halts.

Halting problem is undecidable so the algorithm cannot be executed by a Turing machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.