High-level Description of a Turing Machine

Defining a Turing Machine by its formal description can be quite cumbersome. To improve our understanding, higher-level descriptions are used. It is a precise and compact version of the formal description.

Consider the following language

    \begin{equation*} L = \{ 0^{2^n} | n \geq 0 \} \end{equation*}

Description

Here is a High-Level description of a TM that recognizes the language

  1. Sweep left to right across the tape crossing off every other 0.
  2. If during step 1, tape contains a single 0, accept.
  3. If during step 1, tape contains more than a single 0 and the number of 0s is odd, reject.
  4. Return tape-head to the start of the tape
  5. Repeat

Analysis

At each iteration, step 1 cuts the number of 0s in half.

If the resulting number of 0s is odd and greater than one, the original number could not have been a power of 2reject.

If the resulting number of 0s is one than the original number of zeros must have been a power of 2accept.

References

Leave a Reply

Your email address will not be published. Required fields are marked *