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?

Thank you for your answers!

  • 2
    $\begingroup$ (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.) $\endgroup$ Sep 28, 2010 at 10:26
  • 3
    $\begingroup$ 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? $\endgroup$ Sep 28, 2010 at 11:58

1 Answer 1


What is n here? Is it no .of digits or the value of the number?

If it is the value of the no,, then just convert each digit of base-9 no. in to its base-3 equivalent.


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.