Low-level Description of a Turing Machine

A low-level (or formal) description of a Turing Machine (TM) to recognize a language involves defining all the elements in the -tuple



Consider the following language



Idea

Here is the idea behind building a TM to recognize the above language.

1. Scan the input tape to be sure that it contains a single . If not, reject.
2. Zig-zag across the tape to corresponding positions on either side of to check whether these positions contain the same symbol. If they do not, reject. Cross off the symbols as they are checked.
3. When all symbols to the left of have been crossed off, check for the remaining symbols to the right of . If any symbol remain, reject; otherwise accept.

When the idea explains in detail how the tape is modified, it is called a High-Level Description. This High-Level description can be converted into a formal description.

Alphabet

The input alphabet will be as defined in the language.

A new symbol () is needed to keep track of the crossed off symbols. Thus, the tape alphabet will be .

Transition Function

The transition state diagram for the above implementation is shown below. The red path matches the s on either side of the .. The blue path matches the s on either side of the .. The orange path brings the tape-head back to the first uncrossed symbol. The black path checks if the count of the crossed out symbols match.

A note about the reject state

The state is not shown here. It is assumed that all undefined transitions (to ensure that the transition function is a total function) go to . For example has no transition on the symbol in the diagram above. It goes to .

In essence, we only care about ensuring that the strings that are indeed accepted end up in . All other strings that do not match the pattern get rejected. There is no case where the machine will run forever.

Formal Description

Putting it all together, the low-level (formal) description of the TM to recognize the language will be



where the transition function can be extracted from the transition diagram above.