# developing a Turing Machine that checks for powers of 2

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.

• Please rewrite to make full question. I am sorry that you are lost, but still it is unclear what you want. Power of two means that number is divisible by 2 n times, right? So divide? Try putting "2" every second number, and then merge "1" getting rid of "2"? This will check if number is even and then divide by two. – Evil Dec 11 '15 at 18:55
• Bargrps/Bargros, you seem to have accidentally created two accounts please see the help center to merge them. @EvilJS Bargrps says “that is exactly what I am trying to develop”. – Gilles 'SO- stop being evil' Dec 11 '15 at 22:07

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.

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$
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.