For this discussion, I created a program that can generate all possible Python programs and then run them. We’ll call it a metaprogram—that is, a sort of “super-program.” It can be described simply by the following rules:
- Create a list of all characters used by the Python programming language.
- n = 1
- From this list, generate all possible permutations of n symbols
- Run each of these permutations as a program, and if no error occurs, save that permutation
- n = n + 1
- Return to step 3
If I had to describe what it does in words, I’d say that the program creates a folder containing all possible programs that can be run without an error message. It starts with the shortest program consisting of a single symbol (hence n = 1) and generates all permutations. It then runs them and saves the programs that do not produce an error message. An error message can occur very easily if a character permutation is run that doesn’t make sense in Python. For example, a program whose content is `print('Hello')` makes sense in Python, so this program will run without an error message and its output will be the word “Hello.” However, if the program’s content is, say, YFag##A7, the program’s output will be an error message (most likely of the type “SYNTAX ERROR”).
This program should therefore be able to systematically generate and run all programs. Of course, there are an infinite number of such programs, so this metaprogram will never generate them all in finite time. It’s interesting to take a moment to think about what these programs can do and what the consequences will be.
Such programs may be capable of producing text output. It follows that the metaprogram (assuming it runs for an infinitely long time) will create an infinite number of programs with text outputs. These programs can therefore generate anything written—the word “Hello,” my phone number, the exact date of my death, this reflection, a work by Shakespeare, Einstein’s equation E = mc², several valid digits of π, and even the code for this program itself.
Another possible output is visual. The program can thus generate vector or bitmap graphics. Consequently, these programs can create the Mona Lisa, a photo of the Milky Way, the Facebook logo, or a photograph of me writing this essay—a photo that no one has ever actually taken.
Audio output is, of course, also possible. The program can play the song “Lucy in the Sky with Diamonds” by The Beatles, J. S. Bach’s “Crab Canon,” a radio broadcast from December 29, 1989, and so on. Of course, we have an infinite number of possibilities here as well.
But the most interesting thing is that Python can even control the computer’s operating system. It can, for example, shut down the computer, delete certain files, and so on. Theoretically, it should therefore be capable of creating and spreading a computer virus worldwide, hacking the government, or manipulating elections. These are admittedly somewhat exaggerated examples, but they are based on the assumption that the metaprogram will one day create and run every possible program. Here, however, a problem arises. From the beginning, we have somehow intuitively assumed that the metaprogram will never stop. After all, that was a prerequisite for claiming that it would indeed create every possible program. Since the Python language can control the operating system in this way, it can also create a program that shuts down or restarts the computer, deletes the original metaprogram file, or corrupts it in some way. It can also damage the entire operating system. If any of this happens, the metaprogram will stop. This, however, implies that this metaprogram will eventually stop at some finite time and that it can therefore never truly create all programs for the Python language. It reminds me of the “God paradox”: If God is omnipotent, can He create a rock that He Himself cannot lift? If He can create such a rock but cannot lift it, He is not omnipotent. If He cannot create such a rock, He is not omnipotent either.
A logical step would be to create a rule in the program that would exclude any program capable of causing the metaprogram to halt. For example, this program would be able to shut down the computer:
import os
os.system('shutdown /s /t 1')
The first line of the program specifies that commands from the `os` package will be used. Using this package—or module—the program can then execute commands that interact with the computer’s operating system. The second line of the program then shuts down the computer. So why not simply create a rule in the metaprogram that prevents the use of the `import os` command? Although our infinite list of all possible programs would then be incomplete, it would circumvent this pitfall. But of course, that’s not how it works. Even if we added this rule to the metaprogram, the metaprogram would eventually create its own copy that does not contain this rule—that is, it would create our original program without the new rule. Nothing would then prevent this incomplete copy from creating programs in which the `import os` statement would be used. And it is precisely this statement that would ultimately terminate our original metaprogram. Another option is not to run the individual programs at all, but simply to save them; however, this would prevent our metaprogram from doing everything that can be programmed in Python. I can’t think of any way to get around this problem. Theoretically, it would be possible to use a “weaker” programming language that cannot shut down the computer or otherwise stop the metaprogram.
Here is the source code for this program:
import string
import os
from itertools import product
symbols = string.printable
index = 1
lenght = 1
program = ""
while True:
# create variations with repetitions of symbols used in python
perm = product(symbols, repeat=lenght)
for one_perm in perm:
for x in one_perm:
program += x
# white a file.py
f = open("program_{}.py".format(index), "w")
f.write(program)
f.close()
# execute file.py and decide if it can run
try:
exec(compile(open("program_{}.py".format(index), "rb").read(), "program_{}.py".format(index), 'exec'), {}) # {} is for not using variables declered in this .py file
except Exception:
print(program, "ERROR")
else:
f = open("running_program_{}.py".format(index), "w")
f.write(program)
f.close()
print(program, "RUNNING")
# delete file.py, reset everything to default
os.remove("program_{}.py".format(index))
program = ""
index += 1
lenght += 1
Technical Note (2026): The original program code above has a fundamental flaw. If it generates a program with an infinite loop, its execution will hang, and it will no longer generate any further programs. This problem can theoretically be solved using the dovetailing method (see Universal Dovetailer), which interleaves individual computations so that no program can block the others. I am leaving the original code unchanged.