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

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 .
2. If during step 1, tape contains a single , accept.
3. If during step 1, tape contains more than a single and the number of s 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 s in half.

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

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

References

• https://www.ics.uci.edu/~goodrich/teach/cs162/notes/turing2.pdf