2

I know there are infinite number of topics on here asking about how to prove decidability, but I have been reading a lot of them, as well as reading proofs from a book, trying to understand how to approach this problem, but I'm struggling quite a lot. My question is - is there a general approach for proving decidability/undecidability or does it come with practice of reading a lot of those proofs? To me, it looks like a trivial problem, but whenever I try to prove something myself, I get stuck.

A Val
  • 23

1 Answers1

0

We will use the following language L as an example:

$L=\{⟨M,w⟩:M$ is a Turing Machine that accepts w reversed whenever it accepts w$\}$
The general approach would be to construct the following Turing Machine (TM) H assuming that D is a decider for L. 

H = "On input <A, x> an encoding of a TM A and a string x
    1. Construct the following TM M
       M = "On input w:
            10. Run A on x
            20. if w = '01' or w = '10'
            30.     accept
            40. else
            50.     reject"

    2. if D accepts <M, '01'>
    3.     accept  (since A halts on x)
    4. else
    5.     reject  (since A loops on x)"

If D decides L then H would be a decider for the Halting Problem.
This would be a contradiction that the Halting problem is undecidable.
This means that L must be undecidable.

The parts of the proof that need to be modified depending on the language would be lines 20 and line 2.
In Line 20, you basically pick a 'w' so that is in L.

Hope that helps.

user137481
  • 2,605