​​A Quine is a (non-empty) program $P$ that takes no inputs and returns its own source code $\langle P\rangle$ as the only output. For a function $f$ (with appropriate domains and range) define an $f$-Quine as a program $P$ that takes an input $x$ and outputs $f(\langle P\rangle, x)$. Thus, with no inputs and when $f = id$ we recover the standard notion.

Given a source code $\langle f\rangle$ for $f$ in some programming language is it possible to efficiently compile it into an $f$-Quine in the same language? I think this would amount to making Kleene's recursion theorem very concrete.

  • 3
    $\begingroup$ The standard proof of the recursion theorem is perfectly constructive and explicit: let $Q$ be a program that takes as input the code $\langle R\rangle$ of a program with one input, and outputs the code of the program $f(\langle R(\langle R\rangle)\rangle,x)$ (that is, hardwire the input $\langle R\rangle$ into $R$, and hardwire the code of resulting program into $f$). Then put $P=Q(\langle Q\rangle)$. $\endgroup$ Commented Jun 10, 2023 at 10:17
  • $\begingroup$ Hi there! When I was a grad student, I implemented something like this for fun and it seems to still work. It makes self-referential webpages. If you're interested, see here: michaelwehar.com/quines/howto.html Maybe we could collaborate to make a more refined version of this in the future. :) $\endgroup$ Commented Jun 16, 2023 at 17:05
  • $\begingroup$ Here's the program that builds "f-Quines" for you: michaelwehar.com/quines/self_reference_made_easy.html $\endgroup$ Commented Jun 16, 2023 at 17:06
  • $\begingroup$ For more explanation, when you define G(x,y), x refers to the webpage's own source code and y refers to the input that will be put by the user into the generated webpage's textbox. It then outputs the code for a webpage with the textbox that takes in y as input and evaluates G(e,y) when you click the button where e is the webpage's own source code. $\endgroup$ Commented Jun 16, 2023 at 17:11
  • $\begingroup$ To better understand, as an example, you could type in "console.log(x);" and click generate. Then you could create a webpage with the generated code. This webpage will print its own source code to the console and ignore the input y. $\endgroup$ Commented Jun 16, 2023 at 17:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.