patternMajor
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
Viewed 0 times
canthecomputationanynumberssubcompleteknownpreciselyturing
Problem
I wish there were more, but the subject pretty much captures my whole question.
Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is known to be able to enumerate the prime numbers, all of the prime numbers (well, til you pull the plug on the algorithm), and only the prime numbers?
To be clear, one of the criteria I'm imposing is that this algorithm would be non-halting, and so long as it is left running, it will continue intermittently outputting prime numbers. This seems to necessitate an unbounded working memory, which gets you a lot of the way towards Turing-complete already.
Furthermore, this must be a model with a finite description, meaning no cute "consider the system mapping the natural numbers to the primes" answers, please. Even if technically correct, what I'm really after is whether it seems probable that prime enumeration would be a strong indicator of Turing completeness.
Edit: As for the objection that Turing machines can't yield values at will, I consider that semantics and not relevant to the spirit of the question. A Turing machine could certainly record all prime numbers found thus far on its tape, which we could presumably examine at will.
Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is known to be able to enumerate the prime numbers, all of the prime numbers (well, til you pull the plug on the algorithm), and only the prime numbers?
To be clear, one of the criteria I'm imposing is that this algorithm would be non-halting, and so long as it is left running, it will continue intermittently outputting prime numbers. This seems to necessitate an unbounded working memory, which gets you a lot of the way towards Turing-complete already.
Furthermore, this must be a model with a finite description, meaning no cute "consider the system mapping the natural numbers to the primes" answers, please. Even if technically correct, what I'm really after is whether it seems probable that prime enumeration would be a strong indicator of Turing completeness.
Edit: As for the objection that Turing machines can't yield values at will, I consider that semantics and not relevant to the spirit of the question. A Turing machine could certainly record all prime numbers found thus far on its tape, which we could presumably examine at will.
Solution
There is an important class of primitive recursive functions. Citing Wikipedia,
[P]rimitive recursive function is roughly speaking a function that can
be computed by a computer program whose loops are all "for" loops
(that is, an upper bound of the number of iterations of every loop can
be determined before entering the loop).
They are powerful enough to check primality: to check primality of $n$ it suffices to loop from $1$ to $n$, where $n$ is a known upper bound. Then you can define the function "$i$-th prime": it can be bounded by, say, $2^i$ due to Bertrand's postulate, then you can check all numbers from $1$ to $2^i$ and find the $i$-th.
On the other hand, they are less powerful than Turing machines, the separating example being the Ackermann function.
Wiki page on primitive recursive functions is quite comprehensive for the introduction.
[P]rimitive recursive function is roughly speaking a function that can
be computed by a computer program whose loops are all "for" loops
(that is, an upper bound of the number of iterations of every loop can
be determined before entering the loop).
They are powerful enough to check primality: to check primality of $n$ it suffices to loop from $1$ to $n$, where $n$ is a known upper bound. Then you can define the function "$i$-th prime": it can be bounded by, say, $2^i$ due to Bertrand's postulate, then you can check all numbers from $1$ to $2^i$ and find the $i$-th.
On the other hand, they are less powerful than Turing machines, the separating example being the Ackermann function.
Wiki page on primitive recursive functions is quite comprehensive for the introduction.
Context
StackExchange Computer Science Q#144969, answer score: 24
Revisions (0)
No revisions yet.