2
$\begingroup$

I have a doubt on my solution of the following: Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all and only the Turing machines that write "a" on the tape for every possible input w prove that this language is undecidable.

Formalization: A={<M, a> | M is a Turing machine and M writes a for every input string w}

Proof of undecidability: Assume that A is decidable and H is it's decider, we can prove that there must exist a decider for ATM reaching a contraddiction.

On input <M, w>:

  1. Build a Turing machine N as will follow
  2. Run H on input <N, a>
  3. Return the output

N=On input x:

  1. Run M on w
  2. If M accepts, write "a" on the tape and accept
  3. If M rejects, write "a" on the tape and reject
  4. If M loops, write "a" on the tape and reject

Is this correct? I am not sure if the construction of N is ok specifically in the point 4.

$\endgroup$

1 Answer 1

2
$\begingroup$

Your suspicion is well-founded. The point 4 is invalid.

Imagine the exact moment N "writes 'a' on the tape and reject" in the point 4. That means at that moment, it is known that M loops. However, all the algorithm has done is running M on w for some steps without acceptance nor rejection. It is possible that if we run M one step more, it will halt to accept or reject. So, it cannot be certain that M loops.

In fact, had point 4 been valid, we would have solved the halting problem by the simple Turing machine below.

On input <M, w>:

  1. Run M on w
  2. If M accepts or rejects, accept
  3. If M loops, reject

Here is a proof of undecidability of A.

Assume that A is decidable and H is it's decider, the following will be a specification of a decider for ATM, which is known to be impossible, however.

On input <M, w>:

  1. Build a Turing machine N as below.
  2. Run H on input <N, a>
  3. Return the output

N=On input x:

  1. Run M on w
  2. If M accepts, write "a" on the tape and accept
  3. If M rejects, reject.

The section above interprets "M writes a" in the definition of A as "M writes 'a' and accept, leaving all other cells blank.". i.e., M returns "a".

Another interpretation of "M writes a" is that "M will write 'a' at least once during its execution". Then the construction of N will be more complex.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you sooo much! I was also uncertain of whetever it was correct to write "a" only when M accepts w so that got me confused, but now I see it's the only way! $\endgroup$
    – DRE
    Commented Jun 10, 2022 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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