View source for A true but useless theory of everything


Or: "The program that executes all programs" <br>
Or: "The program that constructs and executes in parallel all programs that are constructible"

== Claim: Turing completeness allows for simulating all possible universes ==

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 abstract 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. <br>
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 mysterious 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 even good for anything? ==

=== Art as an eventual application case ===

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 non-terminating non-repetitive 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". <br>Almost all of these programs do nothing or almost noting.

== Related ==

* [[Philosophical topics]]
* [[Big bang as spontaneous demixing event]]
* [[Foundations of mathematics]]
* [[The limits and guesses in math]]

[[Category:Philosophical]]

=== Nonterminating nonperiodic programs ===

An interesting 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