# How to construct a Turing machine for a language

I have proved that language $$L$$ is not regular and think that it is recognizable by a Turing machine. I want to prove it by constructing a Turing machine for it.

$$L=\{0^n|n \in A\}$$ where $$A$$ is set of all numbers that do not contain 1 in their base 3 representation. However, n is in base 10.

What I have done so far:
When I was proving that the language is not regular, I used the fact that there cannot be any arithmetic sequences in $$A$$. I think if I work on the number of 1 in base three, I may get somewhere.

• If it is recognizable at all, it is recognizable by some Turing machine, so you're not proving anything. On the other hand, if it is context-free, you might want to prove it is, i.e., recognizable by a pushdown automaton. – Mike Dunlavey Dec 6 '14 at 20:59

Try to come up with an algorithm, and then write the simplest possible program in some usual programming language for recognizing L. Then translate that program to a Turing machine.

N is not "in base 10" - it's just a number in your computer's memory, which is probably internally represented in base 2, but your program shouldn't care.

To check if a number contains 1 in base 3 representation, try to build the base-3 representation using the usual base conversion algorithm (digit = x mod 3, proceed with x div 3), and stop when you see a 1.

• you mean for input 12, I have to first write 12 on tape. then convert it to base 3 and if I encountered 1, then reject ? – binamu Dec 6 '14 at 21:16
• The original problem statement is, AFAIU, to write a recognizer. So the tape should initially contain a number of repetitions of the "0" character. For 12, it'd be 000000000000. – jkff Dec 6 '14 at 22:57

As remarked already by jkff, a number is a number in whatever representation. Actually you get your number $n$ in unary representation as a sequence of $n$ $0$'s.

Checking whether the base 3 representation includes a $1$ is extremely easy. You scan the input, and for every three $0$'s, you replace each of the last two by a $+$ (just some symbol). This is like dividing by 3. When you reach the end, if there has been only a single $0$ read since the last replacement, you reject the input, else you replace each of the remainig $0$'s, if any, by $+$. Then you repeat a new scan, until you have less than three $0$'s left. If there is only one $0$ left then the input string is rejected, else it is accepted.

This is easily implemented with a Linear Bounded Automaton (LBA). Hence the language is Context Sensitive (but that does not usually say much more than recognizing it with a terminating Turing Machine). It is probably not too hard to write a CS grammar for it.