I am designing some turing machines, so far I have made Binary Addition and subtraction. Now I've been thinking that what if turing machine can check if the number is prime or not. Lets suppose we have a tape
Blank|1|1|1|1|1|Blank
Now we have to check whether this number 5 is prime or not by designing a turing machine.
What I've done so far is that, we will check by making pairs, For example,
First we divide by 2, 2 = 11.11.1 = Not divisible by 2
Then divide by 3, 3 = 111.11 = Not divisible by 3
Then divide by 4, 4 = 1111.1 = Not divisible by 4
Then divide by 5, 5 = 11111 = divisible by 5(Prime)
Please help me design turing machine for this. I did make this logic, but I don't know how to implement this in turing machine. Please help me!! Thanks.
Best Answer
Firstly, your intuition about how such a program would work is absolutely correct, and for all effective purposes would be completely satisfactory (in my view).
Secondly, as you probably know, prime numbers must be defined in terms of multiplication/division because prime numbers have exactly 2 factors (factorization being a concept developed from multiplication/division).
Thirdly, before trying to make a turing machine that identifies prime numbers, I would focus on making a turing machine that multiplies or divides.
Lastly, have you ever seen the code for a turing machine that multiplies or divides? The codes themselves are pretty non-trivial, especially if you want to limit your turing machine to simply using 1s and 0s. I would imagine that a program for identifying primes would be even more impressive, being that the program must contain the concepts of multiplication/division and then expand on them.
Good luck!