I will be leading a project to construct a pattern that factorizes a given integer N. However, this project is just for recreational purposes because such a pattern wouldn't be efficient at factorizing integers, let alone large semiprimes. If completed, it could probably end up in POTY 2021.mniemiec wrote: ↑March 4th, 2021, 12:08 amSince Life has been proven to be computationally universal, it is possible to construct a Life pattern that can emulate a Turing machine (which has actually been done), and it's possible to program a Turing machine to compute any computible function (e.g. factorization of any finite integer). This doesn't mean that doing it by emulating a Turing machine would be particularly efficient; only that it's theoretically possible.creeperman7002 wrote: ↑March 3rd, 2021, 7:49 pmCould a pattern that factorizes arbitrary integers and displays their output be constructed?
It could probably be a similar design to the pi calculator, but it would have to be able to solve polynomials if it were using a fast algorithm like the elliptic curve method, quadratic sieve, or general number field sieve.
Obviously it would be useless in factorizing large integers because of a combination of the long time taken to factorize sufficiently large integers and the fact that it's in CGOL.
(In a similar fashion, it's possible to construct any glider-constructible pattern from 17 gliders via constructor technology, but that doesn't mean that it's easy to describe the particular coordinates of those gliders. The entire program is deduced from the position of one remote glider - and its position is necessarily very far away, even for the simplest of constructions.)
Prime factorization project
- creeperman7002
- Posts: 301
- Joined: December 4th, 2018, 11:52 pm
Prime factorization project
Quoting these posts from Thread for basic questions:
B2n3-jn/S1c23-y is an interesting rule. It has a replicator, a fake glider, an OMOS and SMOS, a wide variety of oscillators, and some signals. Also this rule is omniperiodic.
viewtopic.php?f=11&t=4856
viewtopic.php?f=11&t=4856
Re: Prime factorization project
You may find that that task is easier than you think, these days. All that you'll have to do is code up a factorization algorithm in APGsembly, compile it into a Life pattern with the existing script, and figure out how you want to handle inputting the value for N and getting the factors out as output -- probably print the factors the same way the pi calculator prints pi?creeperman7002 wrote: ↑March 5th, 2021, 7:43 pmI will be leading a project to construct a pattern that factorizes a given integer N. However, this project is just for recreational purposes because such a pattern wouldn't be efficient at factorizing integers, let alone large semiprimes. If completed, it could probably end up in POTY 2021.
Last year Rei wrote an online APGsembly emulator -- definitely worth checking out.