scanning 1, then all possible matches between the two groups of Os on the tape have been made, and M goes to state 95 to make the tape blank.

qi: In this state, M searches right, through the initial block of Os, looking for the leftmost 1. When found, M goes to state q2.

qi: M moves right, skipping over Is, until it finds a 0. It changes that 0 to a 1, turns leftward, and enters state q-. However, it is also possible that there are no more Os left after the block of Is. In that case, Л/ in state q-2. encounters a blank. We have case (1) described above, where n Os in the second block of Os have been used to cancel n of the m Os in the first block, and the subtraction is complete. M enters state qi, whose purpose is to convert the Is on the tape to blanks.

q3; Л/ moves left, skipping over Os and Is, until it hnds a blank. When it finds B, it moves right and returns to state q, beginning the cycle again.

q/: Here, the subtraction is complete, but one unmatched 0 in the first block was incorrectly changed to a B. M therefore moves left, changing Is to 5s, until it encounters a F on the tape. It changes that В back to 0, and enters state q%, wherein M halts.

95: State gs is entered from qa when it is found that all Os in the first block have been changed to B. In this case, described in (2) above, the result of the proper subtraction is 0. M changes all remaining Os and Is to S and enters state q.

qa: The sole purpose of this state is to allow M to halt when it has finished its task. If the subtraction had been a subroutine of some more complex function, then qe would initiate the next step of that larger computation.

□

8.2.5 The Language of a Turing Machine

We have intuitively suggested the way that a Turing macliine accepts a language. The input string is placed on the tape, and the tape head begins at the leftmost input symbol. If the TM eventually enters an accepting state, then the input is accepted, and otherwise not.

More formally, let M = {Q,E,r,S,qQ,B,F) be a Turing macliine. Then L{M) is the set of strings w in S* such that qaw \- ap0 for some state p in P and any tape strings a and /3. This definition was assumed when we discussed the Turing macliine of Example 8.2, which accepts strings of the form 0 1 .

The set of languages we can accept using a Turing machine is often called the recursively enumerable languages or RE languages. The term recursively enumerable comes from computational formalisms that predate the Turing macliine but that define the same class of languages or arithmetic functions. We discuss the origins of the term as an aside (box) in Section 9.2.1.

Notational Conventions for Turing Machines

The symbols we normally use for Turing machines resemble those for the other kinds of automata we have seen,

1. Lower-case letters at the beginning of the alphabet stand for input symbols.

2. Capital letters, typically near the end of the alphabet, are used for tape symbols that may or may not be input symbols. However, В is generally used for the blank symbol.

3. Lower-case letters near the end of the alphabet are strings of input symbols.

4. Greek letters are strings of tape symbols.

5. Letters such as q, p, and nearby letters are states.

8.2.6 Turing Machines and Halting

There is another notion of acceptance that is commonly used for Turing machines: acceptance by halting. We say a TM halts if it enters a state q, scanning a tape symbol X, and there is no move in this situation; i.e., 6{q, X) is undefined.

Example 8.5: The Turing machine M of Example 8.4 was not designed to accept a language; rather we viewed it as computing an arithmetic function. Note, however, that M halts on all strings of Os and Is, since no matter what string M finds on its tape, it will eventually cancel its second group of Os, if it can find such a group, against its first group of Os, and thus must reach state qs and halt. □

We can always assume that a TM halts if it accepts. That is, without changing the language accepted, we can make 6{q,X) undefined whenever q is an accepting state. In general, without otherwise stating so:

We assume that a TM always halts when it is in an accepting state.

Unfortunately, it is not always possible to require that a TM halts even if it does not accept. Those languages with Turing machines that do halt eventually, regardless of whether or not they accept, are called recursive, and we shall consider their important properties starting in Section 9.2.1. Turing machines that always halt, regardless of whether or not they accept, are a good model of an algorithm. If an algorithm to solve a given problem exists, then

we say the problem is decidable, so TMs that always halt figure importantly into decidability theory in Chapter 9.

8.2.7 Exercises for Section 8.2

Exercise 8.2.1: Show the IDs of the Turing machine of Fig. 8.9 if the input tape contains:

* a) 00.

b) 000111.

c) 00111.

! Exercise 8.2.2: Design Turing machines for the following languages:

a) The set of strings with an equal number of Os and Is,

b) {a b c I n > 1}.

c) {ww I VJ is any string of Os and Is}.

Exercise 8.2.3: Design a Turing machine that takes as input a number Л and adds 1 to it in binary. To be precise, the tape initially contains a $ followed by in binary. The tape head is initially scanning the $ in state qo- Your TM should halt with N+l, in binary, on its tape, scanning the leftmost symbol of Л + 1, in state qf. You may destroy the $ in creating N + l, if necessary. For instance, golOOll 1 $/10100, and goSlHH 1 9/100000.

a) Give the transitions of your Turing machine, and explain the purpose of each state,

b) Show the sequence of IDs of your TM w-hen given input $111.

*! Exercise 8.2.4: In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions from nonnegative integers to nonnegative integers, but the ideas of this problem apply to any computable functions. Here are the two central definitions:

Define the graph of a function / to be the set of all strings of the form [x,f{x)], where a; is a nonnegative integer in binary, and f{x) is the value of function / with argument x, also written in binary.

A Turing machine is said to compute function / if, started with any non-negative integer x on its tape, in binary, it halts (in any state) with f{x), in binary, on its tape.

Answer the following, with informal, but clear constructions.