Turing machine for $0^{3^k} 1^{p}$
This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly &quot;dividing&quot; the string by $3$, and storing how many times this was repeated. For example, each &quot;division&quot; will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a &quot;1&quot;, as an indicator that you performed one division (since after erasing the first triplet you will have the space to store this &quot;1&quot;). Then you have to bring all the new zeros together and repeat the procedure. The number of ones you have written will be equal to $k$ (and if at some point you cannot perform the division, that is you don't have a power of three - you reject the language).
Next, you begin erasing the ones that come after zeros. Each turn will consist of wiping out exactly $k$ ones - for example the $k$ ones that you have on the left can be replaced by zeros in order to indicate that a one on the right has been erased. At the end of the turn, you replace all the zeros by ones again. Again, if you cannot perform the whole round, you must reject the language.