Accepting/rejecting states in Turing Machine

Question

In language decidability problems, a TM halts with a halting state, an accepting state or a rejecting state. My understanding is that when a TM machines halts on accepting state, it removes everything from the tape, writes "YES" and halts. In rejecting state, it does the same, but writes "NO". My reason for this is that the output is supposed to be given on the tape, not encoded in the logic. Am I wrong? Should halting on an accepting/rejecting state be a sufficient enough condition that there is no need to output anything on the tape?

Answer 1

The details of how the response is encoded vary a bit between authors and textbooks. The possibilities include at least the following:

1. The Turing machine is defined to have separate accepting or rejecting halting states. When it reaches either of these, the content of the tape is irrelevant and all we care about is which kind of halting state was reached.

2. The Turing machine is supposed to clear its entire input tape before halting, such that there's either "YES" or "NO" (or some other canonical representation of the answers, such as 1 and 0) and nothing else on the tape.

3. The Turing machine must halt with the reading head pointing to a 1 to accept the input, and must halt with the reading head point to a 0 to reject. The content of the tape in cells that are not being pointed to is irrelevant.

Usually we don't care much about which of these formalisms we use, because it is easy to see that if we have a Turing machine that recognizes some language according to any of these conventions, it is easy (and trivial) to rewrite it into one that works by another convention.

And when we're talking about Turing machines at all, all we're usually interested is just whether a machine that solves such-and-such problem exists -- exactly what it is is less important.

Convention (1) is convenient for thinking about how one would recognize such-and-such language. Convention (2) is convenient if we want to use the recognizing machine as a subroutine in a larger machine. Convention (3) is a compromise that frees us from having to define a special kind of Turing machine for language recognition purposes (with special kinds of halting states), but is nevertheless nearly as easy to handle as (1).