12
0
Writing quines is hard. Why not have your computer write them for you!
Your program will take as input an interpreter (in a Turing complete language of your choosing) for a language X, and you will output a quine in language X.
Notes:
- Language X is guaranteed to be Turing complete (you do not need to check this (it would be impossible to do so anyways)).
- Due to some issues that jimmy23013 raised in the comments, I'll also guarantee that the language has a quine.
- A quine for the purposes of this challenge is a program that outputs its own source code when given no input.
- The interpreter might throw errors if the program it is running has errors, so be prepared! (A quine shouldn't throw errors.)
Here is an example algorithm you can use. I am only putting it here so people don't claim this challenge is impossible:
Go through every possible program, running them all in parallel or via Dovetailing. Throw out programs that cause errors. Whenever a program outputs its own source code, you are done. Since every Turing complete language has at least one quine, this is guaranteed to eventually return a result.
This is code golf, so the shortest answer wins!
PyRulez
Posted 2017-06-01T03:23:53.763
Reputation: 6 547
1This seems like a fun one. But to be clear the program should take the interpreter as input? How on earth are we going to parse that?? – MD XF – 2017-06-01T03:55:33.507
evalmight help :P Or maybe just use system commands to run the interpreter. – CalculatorFeline – 2017-06-01T03:56:30.970@MDXF You could use a universal turing machine. Javascript would also work, but that sounds like it would be more trouble than its worth. – PyRulez – 2017-06-01T04:03:43.690
1It's possible to write quines in some languages that is not Turing complete. And someone can design a Turing complete language that a quine is impossible. – jimmy23013 – 2017-06-01T04:05:02.753
3Go through every possible program, running them all - I'm not convinced this is possible in general. It is quite likely you'll get
rm -rf /orshutdown -h now(or equivalents in the given language) before you get to a valid quine. Oh and there is also the thing with the halting problem -while(true)may well be generated before a quine. – Digital Trauma – 2017-06-01T06:16:36.110@DigitalTrauma The
while(True)can be evaded by using dovetailing as suggested in the post, as for the others, you might have trouble with that. – Post Rock Garf Hunter – 2017-06-01T06:22:28.667Can we create our own TC language in which to take input interpreters? – Esolanging Fruit – 2017-06-01T06:29:08.527
1"Since every Turing complete language has at least one quine, this is guaranteed to eventually return a result." There are some caveats to this. I can easily design a Turing-complete language that cannot output its own source code (consider a language whose source code is written entirely with letters, but which can only output 0s and 1s). Some TC languages don't have traditional output at all. The statement is only true if you define some encoding for arbitrary strings on whatever the language's output is. Then you can always find a program which produces output that encodes the source. – Martin Ender – 2017-06-01T06:41:11.260
2However, you can't let people choose an arbitrary encoding, because then they could always choose a suitable encoding to trivialise the challenge. So I'd suggest guaranteeing that the language is capable of producing arbitrary strings as output to begin with, so that the source code can always be matched exactly. – Martin Ender – 2017-06-01T06:42:37.000
I'm also not sure how dovetailing would be an option if we're only given a black box interpreter. Spawning separate threads and suspending them each in turn to ensure each thread gets arbitrary amounts of computation time should work though, I think. – Martin Ender – 2017-06-01T06:46:13.017
@MartinEnder Just found the problem. The proof on Wikipedia requires the programming language to be an admissible numbering. Someone can design a language that prints some extra characters if the input is empty, and the output is the same as the source code when it ends. It is still possible to write every computable function in it. Just write the program normally, and add a nop if it happens to print itself when the input is empty. But we may not know if it doesn't halt. It is still Turing-complete as how I understand the definition. But it is not an admissible numbering and the proof fails. – jimmy23013 – 2017-06-01T10:39:47.813
@MartinEnder Sorry I forgot to say what is "the problem". I mean I can design a language that is impossible to quine, even if it uses the complete character set and can compute every computable function mapping any input to any output. It's just the case we don't know how to translate arbitrary programs into it without solving the halting problem. – jimmy23013 – 2017-06-01T10:56:56.537
Wait if you get to the program that does
rm -rf /before the quine? – Erik the Outgolfer – 2017-06-01T11:25:38.800@jimmy23013 I'll just add that it has a quine. – PyRulez – 2017-06-01T11:40:58.583
@EriktheOutgolfer Side effects are okay, but you are not required to execute anything, just find a quine. The hint box is just a suggestion. – PyRulez – 2017-06-01T11:41:46.873
But ANY interpreter? – Christopher – 2017-06-01T12:04:38.153
@Christopher Only ones for Turing complete languages (with quines). – PyRulez – 2017-06-01T12:26:53.260
@PyRulez that is crazy. Assume ASCII only codebase? – Christopher – 2017-06-01T12:31:15.530
@Christopher Sure – PyRulez – 2017-06-01T12:31:47.977
Unless I'm reading this wrong, wouldn't this require solving the halting problem?
while(true)would break stuff, I think – Stephen – 2017-06-01T12:53:34.310@StephenS The hint describes a way around this. – PyRulez – 2017-06-01T13:06:54.927
Does the desired quine program have to halt after printing its source code? – pppery – 2017-08-01T01:44:39.167
@ppperry yes, it does – PyRulez – 2017-08-01T01:45:52.643
Can the program take longer than the age of the universe to execute? (This question applies to both the quine-maker and its produced quine) – pppery – 2017-08-01T01:50:35.767
@ppperry sure thing – PyRulez – 2017-08-01T01:53:47.860
@ppperry yep, no runtime requirements – PyRulez – 2017-08-01T12:49:14.000
From the challenge description, couldn't someone just hardcode the output for the quine in language X, not using the input? – mbomb007 – 2017-08-16T14:04:18.497
@mbomb007 Your program must work for every language. You don't pick language X, language X is determined by the interpreter given. – PyRulez – 2017-08-16T14:29:23.280
"take as input an interpreter (in a Turing complete language of your choosing)" – mbomb007 – 2017-08-16T14:41:04.967
Is outputting a trailing newline acceptable? – mbomb007 – 2017-08-16T15:39:32.167
@mbomb007 if it's only one – PyRulez – 2017-08-16T15:55:58.007
Well, I'm trying, but I may not know enough about how shell commands work. It's not easy to test this on TIO. – mbomb007 – 2017-08-16T22:06:40.953
@mbomb007 why not just require the interpreters to be given in BF or something? – PyRulez – 2017-08-17T01:59:10.220
1I'm voting to close this question as off-topic because any answer would be simply outdated too quickly. new languages pop up every month, and there is no way to future proof it without first solving the halting problem. Aditionally, an 'interpreter' is not defined well enough to mean much. Is it the path to the intepreter, the command to interpret the program, a link to download the interpreter? – tuskiomi – 2017-08-18T15:59:12.680
It is possible to make a turing complete language not have a quine. It's as simple as going to the interpreter and typing something like "if(print.msg == src){print.cancel();}". What should happen if such a language were to be made, and handed to a 'Valid' entry? – tuskiomi – 2017-08-18T16:06:44.710
@tuskiomi I took it to mean that you take the command to execute the code. For Python on TIO, I was using
python -c, and then using each possible code string as the following argument. You don't have to update for languages, you simply run the interpreter executable with the code as an argument, then poll for output. – mbomb007 – 2017-08-18T16:53:27.0401I don't think this is off-topic. It might be "unclear" though. – mbomb007 – 2017-08-18T16:55:18.367
Here's a simplified Python example, from what I'm working on.
– mbomb007 – 2017-08-18T16:57:33.243@tuskiomi I gave the algorithm as a hint. – PyRulez – 2017-08-18T20:20:49.297