# Turing machine to convert base-9 number to base-3 in O(log(n))

Greetings, dear Mathematicians!

How to implement base-9 to base-3 conversion in O(log(n)) on 4-tuple ((stateFrom, encounterWhat, Command, StateTo), where Command can be < (turn left), > (turn right), # (stop execution), or symbol from an alphabet) Turing machine, finite from the left side and infinite from the right side?

-
(1) Looks like an exercise in a book. If this is the case, it is better to state the source. (2) What is n? (Well, I know what n is but you should make it clear in the question.) –  Tsuyoshi Ito Sep 28 '10 at 10:26
There's a bit of overlap into math, but I suspect this question might be even more interesting to the folks over at Stack Overflow. Have you tried asking there yet? –  Carl Smotricz Sep 28 '10 at 11:58