A true but useless theory of everything

Turing completeness allows and universe simulations

As for all we know today a Turing complete machine can compute all what is in principle computable. So by constructing all possible programs that a Turing machine can represent and executing all of them Any part what we observe in our universe will be simulated to arbitrary accuracy somewhere in all theses programs. Totally ignoring the maximized brute force computing ignoring computing inefficiency and the uber-astronomical scale of the task.

Turing completeness allows for all possible programs and, given one takes the simulation hypothesis seriously, allows for simulation of all possible universes.

Constructing and executing the program that constructs and executes all logically possible programs

Lambda calculus is Turing complete. Ignoring evaluation strategies (just as we ignore computing inefficiencies) lambda calculus is extremely simple. Just three sort of things combine into abstact syntax trees that can then be executed.

Lambda calculus provides a nice and straightforward way to construct all possible programs in a systematic way that does not leave any possible program out. Concretely one constructs all possible abstract syntax trees by going through all combinations. One gets an infinite list of all possible program starting states.

In parallel to the generation one can start executing all these programs. To execute a to infinity growing list op programs in parallel one can do do it in a Cantor diagonalization like fashion. After running one computation step on all proggrams that are running so fare run the first computation step on one more program.

Do not get confused here. Despite mentioning Georg Cantors diagonalization here this has nothing to do with proving the existence of the uncountable infinite set of the real numbers. Intuitionistic and constructivistic mathematics has problems accepting as real such numbers that are not constructible by a finite amount of steps. But that's a different story.

• The program described here can really be written and is surprisingly short.
• The execution of this program though is pretty much the very definition of inefficiency itself.

Termination, nontermination in simple loops, nonperiodic nontermination, uncecidable termination

Some of the programs should terminate or fall into a repeating loop pretty quickly.
For the programs that do neither terminate nor fall in a clearly nonterminating repeating loop there is the question whether there is a general algorithm that can decide if that program will ever halt or will certainly never terminate without running the program. This question is the the "entscheidungsproblem" in the formulation of the "halting problem". It turned out (meaning it was proven) that there fundamentally cannot be such an algorithm.

Instead termination behavior of seemingly non-terminating and nonperiodic programs needs to be proven in a program-case by program-case (or programm-class by program-class) manner. For some programs with unclear termination properties is fundamentally non-provable whether they are terminating or non-terminating. (Violating the law of the excluded middle?) and thus these myterious programs (in some sense) can be seen to be equivalent to new axioms.

It looks like it won't terminate, we can't prove that it does not terminate, so lets just say it won't terminate and go with it for now. Yes, that is a deadly sin for math, but then again every axiom is a deadly sin for math and with zero axioms there would be no such thing as math to begin with.

• So the core of math is a necessarily a deadly sin by its own judgement. Scary.
• So the very deepest core of math is Faith, Magic, Lies, call it what you want.

In the end it may all run down on practicability and how it matches our observed physical universe.

(Side-note – going meta: What about provability of our proving capability on a particular program? ...)

Is this good for anything or is this all a just giant brainBEEEP

Fractals are pretty.
Programs that neither terminate nor get into a clearly nonterminating repetitive loop are often of fractal nature. Well there are also clearly nonterminating nonrepetitive ones too. Maybe this "program of all programs" here can be used to discover some new pretty fractals that were till now undiscovered.

Challenges:

• For pictures there needs to be a mapping to 2D space. That would be pretty arbitrary.
• This program of all program is pretty much "the very definition of inefficiency". Almost all of these programs do nothing or almost noting.

Related

Nonterminating nonperiodic programs

An interecting clearly non-terminating non-periodic programs is the algorithm that generates the square-root of two in binary. It achieves never ending non-periodicity by taking as input ever longer sequences of bits from previously computed steps. This causes the algorithm to necessarily slow down with progression. Is this slowdown the case for all nonperiodic nonterminating programs? It certainly seems so from this example.

Another example is obviously pi. But we are already in higher math concepts here much more specific than general computation that falls out from the program of all programs described above.

Fractals

How do these relate to the program of all programs?

• Penrose tiling – a non-periodic non-terminating structure
• Mandelbrot set