4 ms·
I would doubt it's possible, considering the methods that we use to detect primes come down to brute force. It's hard to build an algorithm when we don't have a
by burnte 9y ago
I would doubt it's possible, considering the methods that we use to detect primes come down to brute force. It's hard to build an algorithm when we don't have a formal proof of how primes work/can be detected.
- ecma 9y agoWell it's definitely possible unless I'm a moron (correct me if I am). If you have the primes up to √n you can find all primes up to n because everything else will be composite of the primes you know already. This is basically what TFA is doing. What I was suggesting is that it would be cool if you could avoid defining rules explicitly for (3n+6), (5n+10), etc and have them appear from some feedback loop where we go from a sequence of primes up to n, to n^2, to n^4... CSS4, let's do it.
- gvx 9y agoI don't know if CSS is Turing complete already, but I'm pretty sure it would have to be if it allowed you to implement something like that...
- dkbrk 9y agoNo, it would only need to be primitive recursive [0] because you can bound its runtime. There's actually a lot you can do without Turing completeness. [0]: https://en.wikipedia.org/wiki/Primitive_recursive_function#Computer_language_definition https://en.wikipedia.org/wiki/Primitive_recursive_function#C...
- __s 9y agoPure CSS game: https://codepen.io/elad2412/pen/hBaqo https://codepen.io/elad2412/pen/hBaqo Rule110 (After setting first row requires alternation of tab/space to run): https://codepen.io/elrumordelaluz/pen/wqLyH?editors=010 https://codepen.io/elrumordelaluz/pen/wqLyH?editors=010 stackoverflow discussion: https://stackoverflow.com/questions/2497146/is-css-turing-complete https://stackoverflow.com/questions/2497146/is-css-turing-co...
- nimih 9y agoModern prime testing is quite far from brute force. Tests such as AKS[1], ECPP[2], and APR[3] can determine whether a number is prime in polynomial time (in the number of bits/digits), whereas a true brute force search would be exponential. [1]https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test [2]https://en.wikipedia.org/wiki/Elliptic_curve_primality_proving https://en.wikipedia.org/wiki/Elliptic_curve_primality_provi... [3]https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%8...
- burnte 9y agoYou're right, I misspoke I should have been more precise and said that out way of finding primes isn't based on a specific theorem or algorithm in that we still have to take a number and demonstrate its primeness.