31
10
The ordinal number system is a system with infinite numbers. A lot of infinite numbers. So many infinite numbers that it literally does not have an infinity to represent its own infiniteness. The image above gives a little idea of how they work. An ordinal number (Von Neumann construction) is a set of previous ordinals. For example, 0 is the empty set, 1 is the set {0}, 2 is the set {0, 1} and etc. Then we get to ω, which is {0, 1, 2, 3 ...}. ω+1 is {0, 1, 2, 3 ... ω}, ω times two is {0, 1, 2 ... ω, ω + 1, ω + 2...} and you just keep going like that.
Your program will output a set of ordinals, such {0, 1, 4}. Your score will then be the least ordinal more than all the ordinal in your set. For {0, 1, 4} the score would be 5. For {0, 1, 2 ...}, the score would be ω.
How do you output your ordinals you ask. Code of course. Namely, your program will output a potentially infinite list of other programs, in quotes, one on each line (use the literal string "\n" to represent new lines). A program corresponds to its score as indicated above. For example, if you output
"A"
"B"
"C"
where A, B, and C are themselves valid answers and have scores {0, 1, 4}, the score of your program would be 5. Note that A, B, and C, have to be full programs, not fragments.
Based on the above rules, a program that outputs nothing has a score of 0 (the least ordinal greater than all {} is 0). Also, remember a set cannot contain itself, via the axiom of foundation. Namely, every set (and therefore ordinal) has a path down to zero. This means the a full-quine would be invalid as its not a set.
Also, no program is allowed to access outside resources (its own file, the internet etc...). Also, when you list your score, put the cantor normal form of the score alongside it if it isn't in cantor normal form already, if you can (if not, someone else can).
After taking all the above into account, the actual answer you post must be under 1,000,000 bytes (not counting comments). (This upper bound will likely only come into play for automatically generated code). Also, you get to increment your score for each byte you don't use (since we are dealing with infinities, this will probably only come into account when ordinals are very close or the same). Again, this paragraph only applies to the posted answer, not the generated ones, or the ones the generated ones generate, and so on.
This has the quine tag, because it may be helpful to generate at least part of the sources own code, for use in making large ordinals. It is by no means required though (for example, a submission with score 5 would probably not need its own source code).
For a worked out and annotated example, see here.
Does it mean it should not terminate to output infinite number of cardinals? And where is the restricted-source part? I think this tag isn't for code length limitations. Requiring both quoted and newlines converted to \n seemed redundant to me, should other built-in list formats be allowed? – jimmy23013 – 2015-04-17T01:43:23.823
@user23013 It may, at your option, never terminate to output an infinite number of ordinals. Although quoting and escaping newlines is redundant, many languages have built in facilities for just that task. What do you mean by other list formats? – PyRulez – 2015-04-17T01:48:10.637
I meant any list or array format recognizable by the used language. Or just make converting \n optional. A quick fix in many languages is to just not use any newlines, though. – jimmy23013 – 2015-04-17T01:53:55.997
@user23013 You mean storing the sources in arrays instead of outputting them? Unless your language doesn't write to stdout, probably not. Also, the quoting and escaping is meant to make it easier. Many languages have this facility, like pythons
string.repr
, and haskellsshow
. – PyRulez – 2015-04-17T01:59:04.490I meant the string
["...","..."]
in python, but now I think it is a bad idea because it is hard to output infinite number of strings. But at least for a single string, many language's that facility outputs a variant of this format, like using single quotes (I think Python does so), or doesn't escape newlines (CJam), or use two consecutive quotes to represent the quote character, or escape many more characters (Bash and Tcl, etc). Should we only use your format? – jimmy23013 – 2015-04-17T02:12:20.940@user23013 Unless you can't, yes. Besides, unless you want a finite answer, you need infinite outputs, which most languages don't support for lists or arrays. – PyRulez – 2015-04-17T02:14:49.380
Should
\
be always escaped like\\
, or are they only needed to be escaped if the next character is"
orn
or\
? – jimmy23013 – 2015-04-17T02:38:58.2503Image is broken. What does "set cannot can it" mean? "the actual answer you post must be under 1,000,000 bytes" is far weaker than the actual limit, because StackExchange won't allow an answer of more than 30000 characters. – Peter Taylor – 2015-04-17T07:54:07.307
I don't really understand the question, is it about generating programs which generate programs which generate programs etc.? – Mega Man – 2016-08-07T07:37:03.990
This kind of question makes me feel like we need a simple.codegolf.se for idiots like me that haven't ever taken above high school maths... – Connor Bell – 2017-11-07T13:26:07.213
Isn't this in some sense unwinnable? Whatever the current leader is, I can create a program that prints out her source code, and now I score one point more than her. Unless we run into the one-megabyte limit... so maybe this is really a Kolmogorov complexity problem in disguise. – Nate Eldredge – 2017-11-13T00:44:40.603
Incidentally, a nice little exercise: prove that the score of any program is necessarily a countable ordinal. This is not quite obvious because there are uncountable ordinals with countable cofinality. Hint: fhccbfr abg naq pbafvqre gur yrnfg hapbhagnoyr beqvany juvpu pna or fpberq. – Nate Eldredge – 2017-11-13T00:53:23.770
@NateEldredge simply printing it won't, since you get +1 points for characters not used. – PyRulez – 2017-11-13T00:55:37.613
@PyRulez: Ah, I missed that. But maybe I can quine it somehow to outscore the current leader by ω. Must think some more... – Nate Eldredge – 2017-11-13T00:59:45.077
@NateEldredge probably. I suspect that the best possible answer is 1,000,000 bytes and is also an incompressible string, and represents an insanely huge ordinal. – PyRulez – 2017-11-13T01:02:02.477
@NateEldredge The current leader has been outscored. – Simply Beautiful Art – 2017-11-13T21:51:41.770
1@NateEldredge Worded differently, prove that a computable ordinal must be countable. – Simply Beautiful Art – 2017-11-13T21:52:31.793
@NateEldredge While what you say is certainly possible, it is very unsportsman-like, and I will be quite unhappy if that's what you decide to try and do. – Simply Beautiful Art – 2017-11-13T22:05:56.187
@NateEldredge Also, they could do the same to your answer, until you hit the 1,000,000 byte limit. – PyRulez – 2017-11-14T01:06:34.390
Why the quine tag when quines are specifically not allowed? – Simply Beautiful Art – 2017-11-14T16:20:46.523