Question: Check if number of $a$ are prime with just two tapes in Tuning machine.

I'm not quite sure how to check it but what I've got so far is:

First tape will be the input. For example $aaaaa$

Second tape will be checking the numbers $2$ till $n-1$, meaning $4$ for this example.

We start checking them both from the beginning of the tapes, we write '$aa$' in the second tape, making some checks which I'm not sure, if we fail with these checks, start again but now with '$aaa$', and then lastly '$aaaa$'.

  • $\begingroup$ You can even do it with one tape. Check whether there exists $1 < i < p$ that divides $p$. $\endgroup$ – Yuval Filmus Feb 27 '18 at 13:17
  • $\begingroup$ @YuvalFilmus If I put for example the number 2 in the second tape, and I want to check it with the number 5 with the first tape, how is it possible from that point to check for division? Let's assume we counted 5 in the first tape, and 2 in the second tape, and now the 'head' is at the end of the first and second tape. How can I continue from here to check for arithmatic things. Btw, much appreciation for your answers. Thank you. $\endgroup$ – Ilan Aizelman WS Feb 27 '18 at 13:20
  • $\begingroup$ Use your imagination. The number $i$ divides $p$ if we can concatenate several copies of $a^i$ to eventually reach $a^p$. $\endgroup$ – Yuval Filmus Feb 27 '18 at 13:22
  • 1
    $\begingroup$ Converting to binary seems like a bad idea, since it will make everything more complicated. An approach like in your last comment seems the simplest option. $\endgroup$ – Yuval Filmus Feb 27 '18 at 13:52
  • 1
    $\begingroup$ @YuvalFilmus Well, you can do anything with a one-tape Turing machine, if you can do it at all, so I'm not sure that part of your comment is really helpful. Having two tapes is much easier, since you don't need to spend your entire life scanning back and forth and putting marker characters down to remind yourself where you used to be. $\endgroup$ – David Richerby Feb 27 '18 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.