Description

Have you ever heard of the recursion theorem? What about quines? If you've taken a course on the theory of computation, it was probably the topic that seemed mysterious and out of place. Maybe it didn't make sense or seemed pointless. The goal here is to provide a simplified recursion theorem with motivation and working examples. I hope you enjoy and have a great day!

Contents

What is self-reference and why does it matter? - (General)
What does self-reference have to do with recursion? - (Theory)
How do you make quines and self-referential programs? - (Programming)
A connection between self-reference and Turing-completeness. - (More Theory)

Examples

A Simple Quine
A Simpler Quine
A Shorter Quine

What's the string length of my source code?
Print a C program that prints my source code?
Draw my source code one byte at a time or have fun. :)

A Simple Application of the Recursion Theorem
A Self-Referential Program Generator