developing a Turing Machine that checks for powers of 2

Question

I want to write a Turing machine which checks for unary powers of 2 but without the use 0s, only accepting as input a series of 1s and dashes. I do not know of a sequence of states which would allow me to demonstrate this. I worked out 1 of the 2 I started with, which is make a palindrome checker but as for this I'm clueless, any help would be appreciated, even just a description how to begin to develop such algorithm.

Basically it works like this: you insert a sequence of 1s such as 1111 and the algorithm checks whether the number is divisible by 2, by checking the length of the input - hope I'm being more descriptive here, sorry if I'm not.

Answer 1

When your input in unary system starts on the tape you have for example $11111111$
Now put terminator after input: $11111111#$

Now you have to put $2$ every second digit: $12121212$.
If the last digit is not $2$ after this operation - number was odd so you stop execution and reject, with one distinction: if length of number is 1 you are done ($2^0 = 1$).

After this phase you encode merging: replace last $2$ with $0$ and last $1$ with $0$ and first $2$ with $1$. It goes like this:
$11121200#$
$11110000#$
now shift guardian to the left:
$1111#$

Repeat steps. If during replacing phase you are about to change second $1$ with $2$ but you have guardian - you are done, number was power of two.

Answer 2

My approach to this problem was to use a two-tape Turing machine, using one read-only input tape and one working tape.

We will be using the working tape as a binary counter (with the least significant bit being the left-most one), so at the beginning we initialize it to $ 0 $ (or we can let it stay empty, but that adds a few special cases to our transition function). Then we start reading the characters from the input tape, one by one. After reading each character, we increment the binary counter by $ 1 $. This is done by the following process:

• Replace all leading $ 1 $s with $ 0 $s
• Replace the first $ 0 $ (or end of string) you encounter with a $ 1 $
• Return to the beginning of the counter

After reading all of the characters on the input tape, we check the number on the input tape. We need it to exactly match the regular expression $ 0^*1 $, which means "an arbitrary (can be zero) number of leading zeroes, then a single one, then end of string", since all powers of two look like this when expressed as a binary string. Since a deterministic finite automaton would suffice for this last part of the task, checking the pattern with a Turing machine shouldn't be a problem.