Table of Contents
1. Quine
A code that prints itself.
2. Halting Problem
Does a program that tells whether the program will halt exists?
The code that passes itself to such program and negates the output result in contradiction, denying the existence.
3. Minimal Problem
Does program that tells whether a code is minimal, that is, there is no shorter code that outputs the same, exists?
Let us assume such program \( M \) exists. A program that generates codes longer than its own length and pass it to \( M \) until minimal program is found, then simulate the minimal program, is a shorter code then the alleged minimal program. Therefore \( M \) cannot exists.