"$M$ accepts language $L$" and "$M$ halts on string $w$" are different things, because $w$ and $L$ are different things. Acceptance is about $M$'s behavior on arbitrary strings.
While this is a trivial answer to a trivial question, you also (implicitly or explicitly) ask some nontrivial questions:
- Can acceptance be defined in terms of halting?
- Why doesn't it seem to happen in this textbook?
- Do different textbooks disagree on these matters?
- Are accepting a language and recognizing a language the same thing?
Let's take them in turn.
1. Can acceptance be defined in terms of halting?
Yes, it can. My textbook (Elements of the Theory of Computation, by Lewis & Papadimitriou) does so (p. 179):
We say that a Turing Machine $M$ accepts a string $w$ if $M$ halts on input $w$. Thus $M$ accepts a language $L$ if and only if $L = \{w \mid M$ accepts $w \}$.
2. Why doesn't it seem to happen in this textbook?
We'd have to ask the author, but I fear the answer is: this particular set of definitions doesn't happen to do so, and it does the job. More on that below.
3. Do different textbooks disagree on these matters?
Absolutely. Different articles and textbooks use may different definitions, to the extent that the same statement may be true according to one textbook and false according to another.
So in this case, we need to know exactly what is meant by a Turing Machine and halting.
Generally speaking, halting is either defined as
- reaching a configuration in which no further transition is possible, or
- reaching a configuration in which the state belongs to one or more states specially marked as "final"
In my textbook, a Turing Machine has a total transition function that relates each possible (state, tape symbol) pair to exactly one (state, action) pair, where an action either specifies a tape symbol to write, or to move left, or to move right.
Because the transition function is total, the first notion of halting cannot be used: the machine would never halt on any input. Consequently, the definition includes a special halting state, $h$, outside the domain of the transition function: while it can be a destination state of transitions, no transitions are defined for it. Halting is defined as reaching a configuration in which the current state is $h$. With this definition, this is equivalent to defining halting as reaching a configuration in which no further transitions are possible.
In your textbook, a Turing Machine has a partial transition function that relates each possible (state, tape symbol) pair to at most one (state, symbol, action) triplet, where the symbol is written, and the action is to move left, or to move right.
The function is partial, so the first notion of halting could be used. Is it?
This is where your textbook starts to confuse me. It still includes a set of "final states" $F$ into the definition of a Turing Machine. Then, it says:
Eventually, the whole process may terminate, which we achieve in a Turing machine by putting it into a halt state. A Turing machine is said to halt whenever it reaches a configuration for which δ is not defined; this is possible because δ is a partial function. In fact, we will assume that no transitions are defined for any final state, so the Turing machine will halt whenever it enters a final state.
But, professor ...
- You say you assume this, but your definition doesn't.
- Even when you assume this, your Turing machines may still halt in non-final states, unless your transition function is required to be total on non-final states. But you never mention or require this.
As we shall see, this is intentional.
So final states and halt states are not the same thing:
- halt states are states in which the Turing machine may possibly halt;
- in some (or all) of them, it will always halt;
- some (or all) of those are "final states".
This is a consistent definition, but an abuse of language. We would expect the set of final states to be the set of states in which the machine may, and will, halt. It isn't always, in this case. Hence my confusion, and yours.
Definition 9.2 (above) then goes on to define a machine accepting a string as the machine reaching a final state with that string as input. As we've seen, with these definitions, this is not the same thing as the machine halting on that string.
While this definition of acceptance is horribly confusing and inconsistent with other textbooks, it is internally consistent. However, I feel the textbook goes off the rails when discussing loops.
First, it introduces the concept, suggesting that an infinite loop is a sequence of transitions in which the exact same configuration is reached for a second time, causing the exact same sequence of transitions to repeat infinitely often.
It reinforces this by saying:
Example 9.3 shows the possibility that a Turing machine will never
halt, proceeding in an endless loop from which it cannot escape. This situation plays a fundamental role in the discussion of Turing machines, so we use a special notation for it. We will represent it by indicating that, starting from the initial configuration $x_1 q x_2$, the machine goes into a loop and never halts.
It then adds:
Definition 9.3 tells us what must happen when w ∈ L(M). It says
nothing about the outcome for any other input. When w is not in L(M), one of two things can happen: The machine can halt in a nonfinal state or it can enter an infinite loop and never halt. Any string for which M does not halt is by definition not in L(M).
We've already seen that this definition of acceptance is needlessly confusing; but what it says about infinite loops is plainly wrong.
It is not the case that all Turing machines will either halt or enter into an infinite loop on every input. It is fundamental to the computational power of Turing machines that many of them do neither, and instead, proceed endlessly without ever going into an infinite loop.
The author can weasel his way out of this by saying that he never actually provides a definition of what it means for a machine to loop on a given input. He can say: what I meant to say is that the machine doesn't halt on that input.
(I'm not picking on this because prof. Linz is particularly bad in this regard; I am because he is not. Nonstandard definitions and sloppy wording are very common in computer science. The field is rife with mathematicians in the best Von Neumann tradition: you're not supposed to make sense of the words they use, you're supposed to follow the definitions and make sense of the math. Plenty of mathematicians and IT persons consider words to be arbitrary placeholders; as long as the math makes sense, or the story makes sense, they don't care what things are called. It pays to bear this in mind when studying computer science related topics. Always look at the definitions. Never trust stories without definitions. Also bear in mind that definitions for terms may not actually correspond to the way the same words are used in the text.
In this particular case, Linz acceptance makes sense because it is equivalent to Lewis & Papademetriou acceptance: given a Linz TM Linz-accepting a language, one can construct an L&P TM L&P-accepting the same language, and vice versa.)
4. Are accepting a language and recognizing a language the same thing?
It depends on one's definition of recognizing. What ultimately matters is the fundamental difference between a Turing machine merely accepting a language and a Turing machine deciding a language.
As prof. Linz emphasizes, when a Turing machine accepts a language, it halts on every input belonging to that language, but it may not halt on input that doesn't. A language for which such a Turing machine exists is called semi-decidable.
When a Turing machine decides a language, it halts on every input, and somehow points out whether or not it belongs to the language. A language for which such a Turing machine exists is called decidable, or recursive. Not all semi-decidable languages are decidable.
The Linz and L&P textbooks have different ways of formalizing this difference; what matters is that they make the distinction clear.
