18
2
Your job is to create the longest period iterating quine, where the length of each program in the sequence is bounded by 500 bytes.
That is, if you repeat the following steps:
- Start with your initial program
- Run the current program
- Go back to step 2
You will eventually get back to your original program. The number of programs in the cycle is your score, which you are trying to maximize.
None of the programs may raise any errors. Each program must be run the same way as well (e.g. no different versions, implementations, compiler options, platforms, etc...) (EDIT: Yes, any external state such as that of a pseudo random number generator was included in the last statement. The external state must be "reset" after each run. If you use true random numbers, worst case is assumed.)
What separates this challenge from The longest period iterating quine (other than 100 v.s. 500) is that every program in the cycle must also be 500 bytes or less. This means that the longest possible cycle is (256^501 - 1)/255 or less. That of course is a big number, but not that big in terms of how much code it takes to calculate. So the challenge is about using as many of the (256^501 - 1)/255 possibilities as you can, not a busy beaver challenge.
The programs are not permitted to access its own source code. However an empty program is permitted if you want (as long as you follow the other rules).
Since checking the programs manually would be hard, you may figure out the score using theoretical methods. You must include an explanation of the score and correctness with your program. If you can not figure out the score, you may instead use a lower bound of the number of programs in the cycle as a defacto score. You are allowed to update this as you find better lower bounds, or if you find the exact actual score.
This is code-challenge, so highest score wins!
EDIT: It is recommended that you write what your score is in scientific notation, so that answers are more easily comparable. It is perfectly fine to have other forms of the score as well, especially if they are connected to your program more clearly. Also, readers are encouraged to edit previous answers to comply with this.
2"the longest possible cycle is (256^501 - 1)/255 or less" --- this isn't necessarily true, the program may pass through the same state multiple times before returning to the original if it manipulates an external object (such as the RNG state or seed) – JDL – 2019-02-11T09:02:25.647
I attempted to write one in Python that cycles through every possible sequence of bytes of a certain length, using
try
andtokenize
to skip the ones that can't be parsed as a string. Since the source is unicode, this should result in a greater cycle length than if it simply excluded bytes 34 and 92 (ASCII " and \ ). However, this turned out to be quite involved - I've officially given up on it for now, so I'm posting the idea in case someone else wants to try it. – Nathaniel – 2019-02-11T09:11:05.2802@JDL that should be against the rules, IMHO - if it stores state elsewhere than in the source code, then it's not an a proper iterating quine. – Nathaniel – 2019-02-11T09:15:10.667
1@Nathaniel I wouldn't categorise it as storing state elsewhere, it is simply using entry points which are a valid part of the programming language it's implemented in. Arguably, anything which calls another function in the programming language is accessing states which are held outside its own source code. – JDL – 2019-02-11T09:17:59.573
1@JDL no, those are different things. Any program in any language obviously has to rely on things that are implemented outside the source code, but storing state outside the source code is different. That would mean the output of the program is not a deterministic function of its source code, but instead depends on some other external context that has been changed by previous runs. That should not be allowed in a quine challenge, IMHO, and the OP's statement about the maximum cycle length indicates that it was intended to be disallowed here. – Nathaniel – 2019-02-11T09:22:33.510
1@Nathaniel, I disagree. (Your suggestion would also disqualify any language in which the instruction pointer has not just a location but a direction, such as lost as using your definition the instruction pointer stores state.) For example, a 5-state program that iterates 2-1-3-1-4-1-5-1-2-1-3-1-4-1-5-1 ... has a period of 8 despite using only five symbols and such a program is certainly possible, even as a quine. – JDL – 2019-02-11T13:50:52.663
1Have posted a straw-man example using a made-up language to elicit other comments on this topic. – JDL – 2019-02-11T14:05:05.863
3@JDL as I'm certain you're aware, in a deterministic language the instruction pointer only stores state during the execution of a program, and not between invocations of it. Your 5-state example isn't possible if the program's output is a deterministic function of its source. – Nathaniel – 2019-02-11T14:21:52.917
1@Nathaniel, see my "five-eight" example below. It is certainly possible. The key features of the language that make it possible are that commands are interpreted differently (but nonrandomly) based on the command history to date, and the the instruction pointer has some "momentum" so that the state-space is, in effect, larger than the number of characters. – JDL – 2019-02-11T14:36:23.207
1@JDL One of the conditions is you have to run all the programs the same way. This includes external state. – PyRulez – 2019-02-11T18:33:40.523
1Reading the source is not allowed, but are we allowed to access the memory location the program resides in? – None – 2019-02-11T21:11:38.480
1@Rogem If you don't read the source, I suppose so. Also keep in mind that the external state must be the same for every invocation. – PyRulez – 2019-02-11T21:12:40.640
If each program must be run in the exact same way, may we specify that each program must be given a specific input? – Embodiment of Ignorance – 2019-02-11T21:23:40.737
@EmbodimentofIgnorance No, since code could be stored in the input. – PyRulez – 2019-02-11T21:24:27.290