Two approaches to computational universality

May 3, 2021

Motivation:

In spite of the immense success of dynamical systems theory in the physical sciences, all scientists ultimately use digital computers to simulate dynamical systems and not vice versa. The reason for this is that theoretical computer science has developed a powerful model of computational universality which is without peer.

There are two equivalent approaches to defining computational universality but both first require carefully defining the notion of a computable function. The only prior knowledge I shall assume is an understanding of proof-program equivalence in the natural sciences [1].

Computable function:

A function \(f\) is computable if \(\forall x \in \text{Dom}(f)\):

\begin{equation} f \circ x \end{equation}

may be evaluated by a Turing Machine. It follows that the space of computable functions is the space of functions whose behaviour may be simulated by Turing Machines.

Universal Turing Machines via an inductive argument:

Given that there are countably many computable functions, we may define:

\begin{equation} F = \{f_i\}_{i=1}^\infty \end{equation}

and we may use \(F\) to define another space of computable functions \(G \subset F\):

\begin{equation} g_1 = f_1 \end{equation}

\begin{equation} \forall n \geq 1, g_{n+1} = f_{n+1} \circ g_n \end{equation}

and since simulating each \(g_n \in G\) requires the ability to simulate the first \(n\) computable functions \(\{f_i\}_{i=1}^n\), we must conclude that for any \(N \in \mathbb{N}\) there exists a Turing Machine which can simulate \(N\) other Turing Machines.

By induction, there exists a Turing Machine that can simulate countably many Turing Machines. For concreteness, given that all theories in physics are computable we may identify the observable Universe with a Universal Turing Machine.

Another path to computational universality is via Turing completeness.

Turing completeness:

A programming language or formal system is Turing complete if it may be used to simulate any Turing Machine. Peano Arithmetic is a concrete example of a formal system that is Turing complete.

Discussions:

The two approaches differ in that a Universal Turing Machine may be thought of as demonstrating the possibility of a large piece of scientific software, that may be used to simulate any physical system known to physicists in 2020. This approach is constructive in the sense that this piece of software comes with the scientific programs which may be used to simulate each of these physical systems.

On the other hand, the approach of Turing Completeness involves specifying the programming language( or formal system) which may be used to design any particular scientific program.

References:

\(1.\) Pauli Space. Proof-Program equivalence in the natural sciences. 2021.

\(2.\) Ord, T. “Hypercomputation: Computing More Than the Turing Machine.” 25 Sep 2002. https://arxiv.org/abs/math.LO/0209332.

Two approaches to computational universality - May 3, 2021 - Pauli Space