3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Mike Dunlavey Dec 6 '14 at 20:59
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$ – binamu Dec 6 '14 at 21:16
  • $\begingroup$ 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. $\endgroup$ – jkff Dec 6 '14 at 22:57
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.