<p>I am interested in Turing machines that can decide primality using only two symbols and, hence, unary encoding for the input. Currently I have a solution that has 29 useful states (not counting the halting states for accepting or rejecting).</p>
<p>How does this number of states compare to previous results? I have tried to find this information online but could not find an answer.</p>

CC BY-SA 4.0
2024-07-26T12:50:26.247Z
What makes you think that there are previous results?  I am nor sure that there are many people working on minimizing the number of states of a Turing machine solving a particular problem (primality or other)...  But I may be wrong of course.  Maybe you are aware of previous literature on a similar topic?  What is the main motivation for studying this?  (Apart from curiosity of course).
Damiano Mazza
CC BY-SA 4.0
2024-07-26T13:33:36.770Z
It's just curiosity. What triggered me was the Wikipedia page about busy beavers where they mention for example that there exists a Turing machine with 43 states that halts if and only if the Goldbach conjecture is false. Also, Gemini told me I'd need hundreds or thousands of states to check primality using unary encoding.
Cristian Gratie
CC BY-SA 4.0
2024-07-30T16:05:24.957Z
Out of curiosity, I tried to write such a Turing machine myself, and the first working solution I came up with has 26 states. I’m sure even less is possible.
Emil Jeřábek
CC BY-SA 4.0
2024-07-31T08:06:38.203Z
Actually, two of my states were completely useless. So I have 24: http://turingmachinesimulator.com/shared/gdpxrflryb
Emil Jeřábek
<turing-machines><primes>
Smallest 2-symbols Turing machine that can decide primality using unary encoding
Cristian Gratie
# Smallest 2-symbols Turing machine that can decide primality using unary encoding

(Asked by: username_0 on 2024-07-25)

I am interested in Turing machines that can decide primality using only two symbols and, hence, unary encoding for the input. Currently I have a solution that has 29 useful states (not counting the halting states for accepting or rejecting).

How does this number of states compare to previous results? I have tried to find this information online but could not find an answer.

**Tags:** turing-machines, primes

> **Comments:**
> **username_1**: What makes you think that there are previous results?  I am nor sure that there are many people working on minimizing the number of states of a Turing machine solving a particular problem (primality or other)...  But I may be wrong of course.  Maybe you are aware of previous literature on a similar topic?  What is the main motivation for studying this?  (Apart from curiosity of course).  
> **username_0**: It's just curiosity. What triggered me was the Wikipedia page about busy beavers where they mention for example that there exists a Turing machine with 43 states that halts if and only if the Goldbach conjecture is false. Also, Gemini told me I'd need hundreds or thousands of states to check primality using unary encoding.  
> **username_2**: Out of curiosity, I tried to write such a Turing machine myself, and the first working solution I came up with has 26 states. I’m sure even less is possible.  
> **username_2**: Actually, two of my states were completely useless. So I have 24: http://turingmachinesimulator.com/shared/gdpxrflryb  

---

## 0 answers

