[Ben Wiedermann] Using the technique we use in Example 3.8 to describe addition, describe exponentiation as a language recognition problem.

What will be an ideal response?

Problem: Given two nonnegative numbers n and m, compute nm.
Encoding of the problem: We transform the problem of computing nm into the problem of checking whether a third number p is the result of raising n to the m power. We can use the same encoding we used in Example 3.5.
The language to be decided: INTEGEREXP =
{w of the form: **= : each of the substrings ,
and is an element of [0 – 9]+ and integer3 = integer1integer2.