Universality

Constructor Theory and Universal Constructors

Constructor Theory reframes physics entirely in terms of which transformations are possible in the universe vs which are not.

Where transformations refer to changes in the state of a system.

Constructor Theory, posits that the set of all transformations that can be achieved in the universe are precisely all the ones that are not prohibited by the laws of physics.

A constructor is anything that can bring about a transformation, and more crucially, retain the ability to bring about that transformation once more.

If a given transformation is possible, then it is also always possible to build a constructor that can bring about that transformation, with arbitrary accuracy and reliability dependent on the resources available to build the constructor.

A constructor that can bring about any transformation that exists can be referred to as a Universal Constructor, done through constructing specialized constructors to construct specialized tasks.

We can say that Universality has been satisfied when there exists a Universal Constructor.

The Church-Turing Thesis and Classical Computation

Now let's consider the Church-Turing Thesis, which states that a function can be computed by an effective method if and only if it is computable by a Turing machine.

Meaning anything that is computable can be computed by a Turing Machine that is specialized to compute that function.

A Turing Machine can be defined as,

$$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$$

where:

• $Q$ is a finite set of states.
• $\Sigma$ is the finite input alphabet, not containing the blank symbol $\sqcup$.
• $\Gamma$ is the finite tape, where $\Sigma \subseteq \Gamma$ and $\sqcup \in \Gamma$.
• $\delta \colon Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function.
  • It tells the machine, given a current state and tape symbol, what state to move to, what symbol to write, and whether to move left or right.
• $q_0 \in Q$ is the start state.
• $q_{\text{accept}} \in Q$ is the accept state.
• $q_{\text{reject}} \in Q$ is the reject state, and $q_{\text{reject}} \ne q_{\text{accept}}$.

The machine begins in a start state $q_0$, reads the symbol $\sigma \in \Sigma$ under the tape head, and based on the current state $q \in Q$ and $\sigma$, the transition function $\delta(q, \sigma)$ determines the next state $q'$, the symbol to write on the tape, and the direction to move the head in, left or right.

This process repeats until the machine enters a state $q_n = q_{\text{accept}}$ or $q_n = q_{\text{reject}}$, where then the Turing machine halts its computation.

If we define a computational process or function as $\tau$, then a deterministic Turing machine can compute any function $\tau$ that belongs to the complexity class $\mathrm{P}$, that is, any function computable in polynomial time.

The Turing Machine is not considered to be a Universal Constructor but under the concept of a Universal Turing Machine, a Turing Machine that can simulate any other Turing Machine, it can be considered to be a Universal Computer for all problems that can be computable in polynomial time and beyond ( though inefficiently ).

Let's now consider the Church-Turing-Deutsch Principle (CTD), which states that any physical process can be simulated by a universal computing device, under any physical theory.

Moreover, this is derived from the physical version of the Church-Turing principle, "Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means".

Under the theory of Newtonian mechanics, the CTD is found to be true, such that we can construct a universal computing device that simulates any physical process, purely through Turing Machines.

Quantum Computation and the Church-Turing-Deutsch Principle

Of course, our physical laws operate not only on Newtonian mechanics, but also on quantum mechanics, relativity, and beyond.

The CTD proposes the concept of a Quantum Turing Machine (QTM), which is the model of computation that extends the capabilities of a classical Turing machine to simulate quantum processes such as superposition, entanglement, and quantum measurement.

We can define the Quantum Turing Machine as:

$$\mathcal{Q} = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$$

where

• $Q$ is a finite set of states.
• $\Sigma$ is the finite input alphabet, not containing the blank symbol $\sqcup$.
• $\Gamma$ is the infinite tape alphabet, where $\Sigma \subseteq \Gamma$ and $\sqcup \in \Gamma$, indexed by integers $i \in \mathbb{Z}$.
• $q_0 \in Q$ is the start state.
• $q_{\text{accept}} \in Q$ is the accept state.
• $q_{\text{reject}} \in Q$ is the reject state, and $q_{\text{reject}} \ne q_{\text{accept}}$.
• $\delta \colon Q \times \Gamma \times Q \times \Gamma \times \{L, R\} \rightarrow \mathbb{C}$ is the transition amplitude function, assigning a complex amplitude to each possible transition $\vert c \rangle$.

The difference between the classical Turing Machine and the Quantum Turing Machine is that the QTM can be in a superposition of configurations, e.g.,

$$\vert \psi \rangle = \sum_{c\in\mathcal{C}} \alpha_c \vert c \rangle, \hspace{2mm} \sum_c \vert \alpha_c \vert^2 = 1$$

a linear combination of all $\vert c \rangle$ with $\alpha_c$, where:

• $\vert c \rangle$ is a basis state in the set $\left\{\vert c \rangle : c \in \mathcal{C}\right\}$, where $\mathcal{C}$ is the set of all possible classical configurations, $c = (q, t, h)$ (SEE DEF., 1.0)
  • $t$ is the tape content at the current step
  • $h \in \mathbb{Z}$ is the tape head position
• $\alpha_c \in \mathbb{C}$ is the amplitude of the basis state $\vert c \rangle$.
• $\vert \psi \rangle$ is the quantum state vector of the QTM.

The transition amplitude function of the Quantum Turing Machine, $\delta$, outputs the complex amplitudes $\alpha_c \in \mathbb{C}$ for transitioning from a state $(q, a)$ to $(q', b, d)$, where this is the next state, the symbol to write at position $h$, and the direction to move the head in, left or right respectively.

We can define a time evolution operator as the linear operator $U: \mathcal{H} \rightarrow \mathcal{H}$ defining one computational step, mapping superposition of configurations at time $\tau$ to a superposition at time $\tau+1$, embodying the transition rule when applied simultaneously to all configurations.

Given the set of complex amplitudes $\mathbb{C}$, we can define the transition of the QTM from one superposition to the next, as,

$$U \vert \psi \rangle = \sum_{c\in\mathcal{C}} \alpha_c U \vert c \rangle = \sum_{c\in\mathcal{C}} \alpha_c \sum_{q', b, d} \delta(q, t(h); q', b, d) \vert q', t^{(h \rightarrow b)}, h + d \rangle$$

where,

• $\vert \psi \rangle = \sum_{c\in\mathcal{C}} \alpha_c \vert c \rangle$
• $U \vert c \rangle = \sum_{q', b, d} \delta(q, t(h); q', b, d) \vert q', t^{(h \rightarrow b)}, h + d \rangle$
• $d$ is the direction the tape moves, $\in \{L, R\}$
• $b$ is the symbol the QTM writes at position $h + d$

as $U$ encodes the transformation of $\delta$ over all configurations $c \in \mathcal{C}$.

The halting state of the QTM is reached when $U$ begins to act as an identity for some $\vert c \rangle$, meaning $U \vert c \rangle = \vert c \rangle$.

Quantum Turing Machines are able to solve the class of decision problems in bounded-error quantum polynomial time (BQP) in polynomial time, meaning efficiently.

A decision problem is in BQP if there exists a quantum algorithm that solves the decision problem with high probability and is guaranteed to run in $\text{P}$.

This Quantum Turing Machine is capable of simulating every finite physical system, meaning if there is some physical process that can be described by a set of fundamental laws, then it can be simulated by a Quantum Turing Machine.

Note that the QTM can simulate any TM - the Turing Machine can be seen as a special case of Quantum Computation where for every basis state, $\vert c \rangle$, there is only a single $\alpha_c$ that is non-zero and for all other basis states, $\alpha_c = 0$.

Yet again, the Quantum Turing Machine is not a Universal Constructor by definition as it can only compute what it's specialized to compute, dependent on the initial conditions of its input state and the program being run within it.

We can now consider the Universal Quantum Turing Machine (UQTM), which is a Quantum Turing Machine that can simulate any other Quantum Turing Machine to any level of precision, given that it has enough resources to do so.

Therefore, the Universal Quantum Turing Machine can be referred to as a Universal Computer.

Universal Constructors vs Universal Computers

The UQTM is also not a universal constructor, though it's the closest model of computation that has been covered so far to a universal constructor.

Universality is a principle that requires more than the ability to compute any physical phenomena, although computation is an important aspect of it.

Let $\mathcal{C}_\mathcal{U}$ be a universal computer capable, in principle, of simulating any finitely realizable physical process $\mathcal{P}$ to arbitrary precision.

When $\mathcal{C}_\mathcal{U}$ is given a program $\pi$ that encodes $\mathcal{P}$, the evolution of $\mathcal{C}_\mathcal{U}$’s internal state will follow some trajectory of symbolic (or quantum-informational) configurations whose mathematical structure mirrors the dynamics of $\mathcal{P}$.

Consider a universal computer $\mathcal{C_{\mathcal{U}}}$ which is capable of computing any physical process. When instantiated with an instruction program $\pi$, made to compute a physical process $\mathcal{P}$, say the process of a quasar being born, its computation will follow some trajectory of complex symbolic and information manipulation to be able to simulate $\mathcal{C}_\mathcal{U}$, but it will not be able to simulate the physics itself.

We generalize this limitation to any physical process.

While the $\mathcal{C}_\mathcal{U}$ can simulate any physical process, it will not be able to directly map its computations to the physics itself as it purely relies on state transitions through the unitary matrix $U$ mapping the superposition of all basis states $\vert \psi_t \rangle$ to the next basis state $\vert \psi_{t+1} \rangle$.

Its means of computation will remain the same for all programs $\pi \in \Pi$, and will not be able to directly simulate the physics itself.

The Universal Computer thereby only satisfies the principle of Universality for purely computation.

The most important principle to take away is that the universal computer is the means by which one can test a theory for any physical process through a program $\pi$.

Meaning for every hypothesis and corresponding experiment, $\mathcal{h}, e$, there exists a program $\pi$ that can run $e$ on $\mathcal{C}_\mathcal{U}$ to test $\mathcal{h}$.

For any physical transformation, given complete and correct knowledge of the physical laws and initial conditions, one can rely on a universal computer to simulate and thereby verify whether the transformation is computationally possible under those laws.

This verification means confirming that the transformation is not forbidden by physics and can be modeled by the universal computer to arbitrary precision.

The universal model of computation serves as the foundational framework and entrypoint for analyzing any physical transformation. It provides the means to simulate and verify its possibility, as it can simulate any physical process.

The universal constructor extends beyond this computational framework by embodying the physical capability to perform all possible transformations, including its own construction, within the laws of physics.

Thus, the universal model of computation is the necessary computational pivot, but not sufficient alone, for the realization of a transformation per the universal constructor.

Given that, let's consider the universal computer, $\mathcal{U}$, independently of the universal constructor, and consider the requirements for it to be able to compute the set of all possible computations.

$\mathcal{U}$ has its computations defined by a set of instructions, $\pi_i \in \Pi$, and an initial state, $\psi_0$. The question then becomes, how does one define the set of instructions and the proper initial state to perform the desired computation?

$\pi$ relies on the relevant information, $\mathcal{I}$, that is had, and the information relies on the existing body of knowledge $\mathcal{K}$.

Then it can be said that the computations of $\mathcal{U}$, despite having the capability to compute any physical process, are bounded by the existing body of knowledge $\mathcal{K}$.

Now going more generally, the transformations that the universal constructor can perform are bounded by the existing body of knowledge $\mathcal{K}$ - if we don't have the existing $\mathcal{K}$ to form an instruction set $\Pi$ to perform a transformation, then we cannot perform the transformation through the universal constructor.

The Universal Explainer

Then, the question becomes, how does one acquire the existing body of knowledge $\mathcal{K}$ to form an instruction set $\Pi$ to perform a transformation, or a computation?

We can define good explanations, per David Deutsch's definition, an explanation that is hard-to-vary, where every piece of theory is tied intimately to how the world appears, and if any part of it varies, the explanation fails.

A universal explainer is an entity capable, in principle, of constructing explanations for any phenomenon permitted by the laws of physics. That is: if something can be understood at all, such a mind can eventually understand it.

In nature, transformations occur through unguided physical processes - evolution, geology, stellar fusion - which produce complex structures and regularities but without foresight or explicit reasoning. Humans differ in that we can deliberately instantiate configurations of matter and energy that would be astronomically improbable to arise without intelligent direction - skyscrapers, space probes, computers. These are still fully consistent with physics, but they represent directed transformations, guided by explicit explanatory knowledge.

The set of transformations that humans have performed in the history of civilization, or the transformations that we know to be possible, is a superset of the transformations that were possible through natural occurrence. An extension beyond what is naturally achievable.

Our capacity for explanation lets us bridge vast gaps of space and time. We can know what is happening inside a quasar billions of light-years away - not because we physically reach into it, but because we construct theories that faithfully capture the underlying processes. These explanations are not mere summaries of observations; they are hard-to-vary accounts of reality’s workings, refined through a process of conjecture and error-correction.

Error-correction here is not mere empirical trial-and-error like in evolution. It operates at the level of ideas: we create candidate explanations, subject them to criticism, and discard those that fail either real-world tests or the scrutiny of coherent modeling. This allows leaps that blind search could never realistically achieve - the conceptual jump from fire pits to integrated circuits, for example.

Our creativity is not bounded to phenomena that have actually occurred in nature. We can conceive of physical configurations that have never existed before, provided they are consistent with the laws of physics. The scope of what we can understand is thus bounded only by those laws, not by what nature has already instantiated.

We have the ability to take observations of the world around us, compress complexity and abstract ideas into rigorous bits of knowledge, and then use that knowledge to perform transformations that would be astronomically improbable to arise without intelligent direction.

As for instance, this is precisely what it took for humans to build spaceships, computers, and other complex machines.

We're even then, more augmented by the machines we build, specifically the supercomputers we build as an approximation to the universal computer, that allows us to perform computations that expand the growth of knowledge.

This, above all, is what makes us universal explainers: our minds generate explanatory knowledge with no inherent domain limits, constrained only by the structure of reality itself, and perform unique transformations.

It can even be said, given that the only thing preventing a specific transformation is knowledge, then given that we can be considered universal explainers, humans as a whole, in principle, are capable of performing any transformation, making us capable of being universal constructors.

Thereby, for any transformation one has a desire to cause, there is always a corresponding explanation that can be generated to perform the transformation, subject to the laws of physics and the desire to cause the transformation - anything within those bounds is soluble.

Definitions

1.0 $\vert c \rangle$

$\vert c \rangle$ is a basis vector in the Hilbert space $\mathcal{H}$ of the QTM that encodes a full classical configuration $c = (q, t, h)$

The full Hilbert space $\mathcal{H}$ is a tensor product of three parts:

$$\mathcal{H} = \mathcal{H}_Q \otimes \mathcal{H}_{T} \otimes \mathcal{H}_{H}$$

where,

• $\mathcal{H}_Q$ is the Hilbert space of the QTM's finite state space spanned by $\left\{\vert q \rangle : q \in Q\right\}$
• $\mathcal{H}_{T}$ is the Hilbert space of the tape spanned by $\left\{\vert t \rangle : t \in \mathbb{Z} \rightarrow \Gamma\right\}$
• $\mathcal{H}_{H}$ is the Hilbert space of the tape head spanned by $\left\{\vert h \rangle : h \in \mathbb{Z}\right\}$

We use Hilbert spaces to describe the possible superpositions of classical configurations the QTM can operate over.

Therefore, $\vert c \rangle = \vert q \rangle \otimes \vert t \rangle \otimes \vert h \rangle$.

• $\vert q \rangle \in \mathcal{H}_Q$ is a standard basis vector with $1$ in the position corresponding to the state $q \in Q$
• $\vert t \rangle \in \mathcal{H}_{T}$ is a vector encoding the entire tape content, defined as an infinite tensor product $\vert t \rangle = \bigotimes_{i \in \mathbb{Z}} \vert t(i) \rangle$
• $\vert h \rangle \in \mathcal{H}_{H}$ is the tape head position vector in an infinite-dimensional hilbert space.

$\vert c \rangle$ is then the huge tensor product encoding the entire basis configuration of the QTM,

$$\vert c \rangle = \vert q \rangle \otimes \left( \bigotimes_{i \in \mathbb{Z}} \vert t(i) \rangle \right) \otimes \vert h \rangle$$