I'm trying to write a Turing machine that can convert a number in binary representation to a number in decimal representation. For example if the input on the tape is 1101 the output should be be 13. Where should I start from?

  • $\begingroup$ This will be a very complicated machine. If you want an arbitrary number of digits, you will need to implement decimal addition and quote a lot of memory management functionality. $\endgroup$
    – Ben I.
    Jun 2 '17 at 15:30
  • 2
    $\begingroup$ And you know how to write a function that does the same in Python or some other language? $\endgroup$ Jun 2 '17 at 18:12
  • 5
    $\begingroup$ I think we need a compiler from some language to Turing machines os that we can answer these questions by showing the concrete Turing machines (thereby indicating the futility of these exercises). $\endgroup$ Jun 2 '17 at 18:13
  • $\begingroup$ @AndrejBauer binary = '1101' decimal = 0 for digit in binary: decimal = decimal*2 + int(digit) $\endgroup$
    – greps
    Jun 3 '17 at 8:18
  • $\begingroup$ @AndrejBauer There's actually a simple imperative language that does compile to TM descriptions: github.com/adamyedidia/parsimony $\endgroup$ Jan 4 '18 at 4:54

Since you don't have any questions in your post, it's hard to give any concrete tips.

Try to do the simpler binary to unary converter instead. And should also assume that you have as many working tapes as you need (say, one input tape, one counting tape and one work tape) and a separate output tape.

You should also pick that of LSB/MSB that suits you best (e.g. LSB).

The biggest task is probably computing $2^i$, so you should start making one machine that takes as input a number $n$ in unary, and outputs (on a separate tape) $2^n$.

  • $\begingroup$ Thank you, I edited the post. The question was: can someone help me giving ideas of a solution? However i solved the problem: the machine has one only tape and on in there will be the binary number. It loops subtracting to the binary one and then adding one to the decimal until the first is 0. $\endgroup$
    – greps
    Jun 7 '17 at 21:50

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.