`w`over the tape sub-alphabet

ΣThe_{0}⊆ Σ – {#,>}

`Σ`alphabet, such as our usual

_{0}`{a,b}`is considered the acceptable alphabet for input strings and is meant to avoid other "special purpose" symbols, such as the obvious blank symbol,

`,`

**#**`as well as others we may want to add. The various operations that a TM can do with an input string require a certain standard starting configuration with`

**>**`w`on the tape. We can use either this one

or this one:>w

>#w

### Decide a Language

According to the textbook a TM which decides a language has two dedicated halt states:`and`

**Y**`. Suppose`

**N**`L`is a language over

`Σ`. A TM,

_{0}`M`,

*decides*

`L`if, for all strings

`w ∈ Σ`, when placed on the tape in the starting configuration:

_{0}*- if
`w ∈ L`,`M`halts in state**y** - if
`w ∉ L`,`M`halts in state**n**

**always halts**from a legitimate starting configuration. An alternative is to not assume anything about the halt states, just let the final tape contents decide the string. In this case, one would assume that the tape alphabet has two other special characters:

Σ = Σand that a TM decides_{0}∪ { #, >, Y, N }

`L`, if for all strings

`w`, when placed on the string in the starting configuration:

- if
`w ∈ L`, the TM halts with configuration**>**Y - if
`w ∉ L`, the TM halts with configuration**>**N

`L`is said to be

*recursive*if there is a TM which decides

`L`.

#### Closure of recursive languages under complementation

We can also easily see that if`L`is recursive, then so is the complement of

`L`. From a TM,

`M`which decides

`L`, we can create a machine deciding its complement:

### Deciding AnBnCn

Here we're going to add a marker symbol:ΣThis is the diagram from the textbook:_{0}= { a,b,c } Σ = Σ_{0}∪ {#,>,d,Y,N}

Here's a sample of a unsuccessful run. On the second "R loop" it goes all the way to the end, where it sees a blank and fails:#aaabbbccc#daadbbdcc#ddaddbddc#ddddddddd #ddddddddd#

Another failure is:#aaabbcc#daadbdc#ddadddd #ddddddd#

Unfortunately, it appears that the authors have made an error because this machine will say that#accc #dccc

abcabcis in the language. After the first pass, it changes:

It would then scan across the#abcabc ⇒#dddabc

`d`'s and proceed again:

Now it scans across the#abcabc ⇒#dddddd

`d`'s, sees a blank and terminates in the yes state. The following modification is a suggested fix, forcing the machine to move past the final

`c`group, in which case it must see a blank:

#### Make it write Y/N

If you wanted to make it "write Y/N" instead of just entering the y/n state what would be different?### Compute a Function

We have the`Σ`as the input alphabet, and we can also refer to

_{0}⊆ Σ`Σ`as the output alphabet. Using these, consider a function:

_{1}⊆ Σf: ΣA TM_{0}* → Σ_{1}*

*computes*

`f`if, for all

`w ∈ Σ`, when

_{0}*`w`is placed on the tape in the starting configuration,

the TM halts in a final configuration of the form:>w

Again, we could just as well prepend a blank before the input and output, expecting starting and final configurations to be:>f(w)

>the TM halts in a final configuration of the form:#w

>In particular, we can say that deciding a language#f(w)

`L`is equivalent to computing the function:

f: ΣThus, using the Y/N write method for deciding a language is, in some sense, preferable to the y/n halt state method, because it makes deciding a language simply computing a specific function._{0}* ⇾ {Y,N}* f(w) = Y if w ∈ L = N if w ∉ L

#### Numeric Computation

The textbook goes immediately to binary notation for numbers, which matches computer arithmetic, but this is usually not presented as the initial notion of a number. Traditionally, one starts with unary notation:1111 = 4, etc. ε = 0The authors present the

**binary**version of increment in Example 4.2.3, which is simply the standard ripple-carry adder. We can also talk about computing a function of more than one argument,

`f(x,y)`. Once again, assume a standard starting configuration like:

>It means that we must halt in a final configuration:#x#y

>In unary, for example, the concatenation function#f(x,y)

f(x,y) = xyserves as the addition function.

#### A TM can use a partial function

A TM transition function being a*partial*function means that there are input pairs for which the transition function is not defined.

δ(non-halting-state, symbol) = UNDEFWe can easily compensate for such an omission by adding a new dedicated "run forever" state,

`:`

**R**δ(With this addition, simply send a missing transition to this state with no tape change, i.e.,R,σ) = (R,σ) ∀ σ ∈ Σ

δ(non-halting-state, symbol) = (The simplest machine that we can create which runs forever is this:R, symbol)

There is a start state, but no transitions and no halt state, i.e.,RunForever= ( {s}, Σ, {}, s, {} )

`δ = ∅`and

`H = ∅`.

### Accepting a Language

A TM*accepts*or

*semidecides*

`L`if, for all

`w ∈ Σ`, the machine halts when started with the initial tape configuration

_{0}*

**#**w**if and only if**

`w ∈ L`. The implication is:

if

The term used is that the TM M `w ∉ L`, then the TM "runs forever," i.e., it**never reaches**a halt state from the starting configuration.*runs forever*if it never reaches a halt state because it can always keep going. If a TM uses a partial function, and it reaches an undefined transition

`δ(p,σ)`, then it also runs forever.

**Notation**: Write

`M`if

**↓**w`M`halts on input

`w`

`M`if

**↑**w`M`runs forever on input

`w`

#### Recursively enumerable

If`L`is accepted by a TM then it is said to be

*recursively enumerable*. It is hard to believe this is a useful concept, but it turns out to be crucial for the theory of Turing Machines. It is easy to see that a recursive language, L, is recursively enumerable. Take a machine which decides L, i.e., it say Y/N to every string Create a new TM which is a simple modification of M so that it runs forever whenever M "says no" to a string

`w ∉ L`: