# Writing a Turing Machine that convers a number from binary to decimal

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?

• 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. Jun 2 '17 at 15:30
• And you know how to write a function that does the same in Python or some other language? Jun 2 '17 at 18:12
• 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). Jun 2 '17 at 18:13
• @AndrejBauer binary = '1101' decimal = 0 for digit in binary: decimal = decimal*2 + int(digit) Jun 3 '17 at 8:18
• @AndrejBauer There's actually a simple imperative language that does compile to TM descriptions: github.com/adamyedidia/parsimony Jan 4 '18 at 4:54

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$.