15. TM Computations

What can we do with a TM? Consider only input strings w over the tape sub-alphabet
Σ0 ⊆ Σ – {#,>}
The Σ0 alphabet, such as our usual {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:

Decide a Language

According to the textbook a TM which decides a language has two dedicated halt states: Y and N. Suppose L is a language over Σ0. A TM, M, decides L if, for all strings w ∈ Σ0* , when placed on the tape in the starting configuration: In particular, the TM 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:
Σ = Σ0 ∪ { #, >, Y, N }
and that a TM decides L, if for all strings w, when placed on the string in the starting configuration: A language 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:
Σ0 = { a,b,c }
Σ = Σ0 ∪ {#,>,d,Y,N}
This is the diagram from the textbook:
Here's a sample of a successful run:
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:
Another failure is:
Unfortunately, it appears that the authors have made an error because this machine will say that
is in the language. After the first pass, it changes:
#abcabc  ⇒  #dddabc
It would then scan across the d's and proceed again:
#dddabc  ⇒  #dddddd
Now it scans across the 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:
Credit goes to my Csc520 student Pavan Lanka for catching and fixing this error.

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 Σ0 ⊆ Σ as the input alphabet, and we can also refer to Σ1 ⊆ Σ as the output alphabet. Using these, consider a function:
f: Σ0* → Σ1*
A TM computes f if, for all w ∈ Σ0*, when w is placed on the tape in the starting configuration,
the TM halts in a final configuration of the form:
Again, we could just as well prepend a blank before the input and output, expecting starting and final configurations to be:
the TM halts in a final configuration of the form:
In particular, we can say that deciding a language L is equivalent to computing the function:
f: Σ0* ⇾ {Y,N}*

f(w) = Y if w ∈ L
     = N if w ∉ L
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.

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.  ε = 0
The 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:
In unary, for example, the concatenation function
f(x,y) = xy
serves 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) = UNDEF
We can easily compensate for such an omission by adding a new dedicated "run forever" state, R:
δ(R,σ) = (R,σ) ∀ σ ∈ Σ
With this addition, simply send a missing transition to this state with no tape change, i.e.,
δ(non-halting-state, symbol) = (R, symbol)
The simplest machine that we can create which runs forever is this:
RunForever = ( {s,h}, Σ, {}, s, {h} )
There are start and halt states, but no transitions, implying that all transitions go to some "run forever" state.

Accepting a Language

A TM accepts or semidecides L if, for all w ∈ Σ0*, the machine halts when started with the initial tape configuration if and only if w ∈ L, i.e., If a TM uses is defined using a partial function, and it reaches an undefined transition δ(p,σ), then it also runs forever.

Notation: Write
Mw    if M halts on input w
Mw    if 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 in 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:
The question is are there recursively enumerable languages which are not recursive? The answer is yes.

© Robert M. Kline