- In order to prove that a number N is composite, we need to prove that it has more than 2 factors i.e 1 and itself.
- This cannot be done with a fixed amount of memory as the number of cases to check increases as N increases
- As regular language has a finite amount of memory, proving that number N is composite is not regular
- The language can be recognised by a Turing machine.