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

- Sweep left to right across the tape crossing off every other .
- If during step 1, tape contains a single ,
*accept*. - If during step 1, tape contains more than a single and the number of s is odd,
*reject*. - Return tape-head to the start of the tape
- 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*.