Metaprogram

For this discussion, I created a program that can generate all possible Python programs and then run them. We will call it a metaprogram—that is, a kind of “super-program.” It can be described simply by the following rules:

1. Create a list of all characters used by the Python programming language.
2. n = 1
3. From this list, create all possible permutations of n symbols
4. Run each of these permutations as a program, and if no error occurs, save that permutation
5. n = n + 1
6. Return to step 3

If I had to describe what it does in words, I would 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. Such an error message can occur very easily if a character permutation is run that does not make sense in the Python language. For example, a program whose content is print('Hello') makes sense in Python, so this program runs without an error message and its output is 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 "SYNTAX ERROR" type).

This program should therefore be able to systematically create and run all programs. Of course, there are infinitely many such programs, so this metaprogram will never generate them all in finite time. It is interesting to pause for a moment and consider what these programs can do and what the consequences will be.
Such programs may be capable of 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 create anything written—the word “Hello,” my phone number, the exact date of my death, this essay, a work by Shakespeare, Einstein’s equation E = mc², several valid digits of π, and even the code of 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 thus 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 again have an infinite number of possibilities.

But the most interesting thing is that Python can also 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 eventually create and run every possible program. Here, however, a problem arises. From the start, we have somehow intuitively assumed that the metaprogram will never stop. After all, that was a condition for the claim that it would truly create all possible programs. 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 damages it in some way. It can also damage the entire operating system. If any of this happens, the metaprogram will stop. It follows, however, that this metaprogram will eventually stop at some finite time and that it therefore can never truly create all programs for the Python language. It reminds me of the “God paradox”: If God is omnipotent, can he create a stone that he himself cannot lift? If he can create such a stone but cannot lift it, he is not omnipotent. If he cannot create such a rock, he is also not omnipotent.
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? While our infinite list of all possible programs would then be incomplete, it would circumvent this pitfall. But 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` command would be used. And it is precisely this command that would ultimately terminate our original metaprogram. Another option is not to run the individual programs at all, but only to save them; however, this would prevent our metaprogram from doing everything that is programmable in Python. I can’t think of any way to work around this problem. Theoretically, it would be possible to use a “weaker” programming language that cannot shut down the computer or stop the metaprogram in any other way.

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