1

I would like to design a Turing machine that takes as input a tape with a sequence of As and counts them, writing the result in decimal at the end of computation. Example: initial tape: $AAAAAAAAAAA \to $ Final tape: $11$.

My problem, here, is actually how to handle the reminder after the number 9 is overpassed. If there're $27$ As on the tape, how can I write $27$ on the tape? I don't care about the transition function. I would like to know the idea that is behind.

TShiong
  • 1,257
banana23
  • 19
  • 1
    I'd start by building a Turing machine that can add one to numbers written in base 10. – TomKern Sep 19 '23 at 21:09
  • I'm able to do that. The problem is:what do you do when you reach 9, 19, 29,... – banana23 Sep 19 '23 at 23:09
  • 1
    If you were physically operating the Turing machine, what would you do? As a suggestion, I'd recommend writing the count to the left of the string of As so that there's a fixed location on the tape for the units digit, the tens digit, and so forth. – ConMan Sep 20 '23 at 00:05
  • You would do it exactly as you learned the decimal system: when you have reached 9, make it a 0, and add a 1 to the digit to the left of it. And ConMan's suggestion of writing the result to the left of the string of A's would solve the problem of having to shift your number – Bram28 Oct 03 '23 at 21:30

0 Answers0