The Ontology of Digital Physics

Abstract

Digital physics claims that the entire universe is, at the very bottom, made out of bits; as a result, all physical processes are intrinsically computational. For that reason, many digital physicists go further and affirm that the universe is indeed a giant computer. The aim of this article is to make explicit the ontological assumptions underlying such a view. Our main concern is to clarify what kind of properties the universe must instantiate in order to perform computations. We analyse the logical form of the two models of computation traditionally adopted in digital physics, namely, cellular automata and Turing machines. These models are computationally equivalent, but we show that they support different ontological commitments about the fundamental properties of the universe. In fact, cellular automata are compatible with a rather traditional form of physicalism, whereas Turing machines support a dualistic ontology, which could be understood as a realism about the laws of nature or, alternatively, as a kind of panpsychism.

1 Introduction

Possibly many things in the universe are digital computers, that is, physical realisations of computing machines. Nonetheless, there is no general agreement about what kind of things should be regarded as such, nor about what exactly is the relation of physical realisation in question (cf. Piccinini 2015). Notably, many philosophers (following, for instance, Putnam 1960; Fodor 1975) have argued that human minds are Turing machines. This thesis, inspired by Turing himself (Turing 1950), is the core of the computational theory of mind also called computationalism. More incisively, others scholars—frequently called “digital physicists”—have defended that the whole physical reality is digital and the universe may be best seen as the realisation of a (quantum) Turing machine (cf. Deutsch 1997; Lloyd 2000; Chaitin 2005) or, alternatively, of a universal cellular automaton (cf. Zuse 1967; Wolfram 2002; Steinhart 2004). To be precise, digital physics is grounded on three assumptions:

• 1. The physical world is a digital structure;

• 2. Physical objects perform computational processes;

• 3. The physical world is a universal computer.

We shall call the first assumption digitalism, the second pancomputationalism, and the third Zuse thesis, in honour of its inventor.¹ Very little attention has being paid to the metaphysical import of these theses as a whole. We find in the literature some recent works on digitalism (cf. Floridi 2009, as well as Berto and Tagliabue 2014), but no systematic analysis of all digital physics. We believe that the main reason for this state of affairs is the absence of a rigorous logical formulation of digital physics, which makes inferences about its metaphysical status questionable.² In this article, we shall try to fill—at least partially—this deficiency. Our aim is to make explicit what kind of properties has to be instantiated by the physical world in order to be a digital structure and, thus, performs the computations that digital physicists impute to it. Our strategy will be to analyse the ontological commitments of the Zuse thesis using the tools of first-order logic. Since the Zuse thesis can be formulated according to two alternative computational models, cellular automata and Turing machines, it will be necessary to consider them both in detail. Even though cellular automata and Turing machines are computationally equivalent (i.e., they can compute the same functions), this does not imply that they can be realised by objects with the same properties. As a matter of fact, we shall prove that the ontological commitments of the two formalisms are quite different.

The structure of the paper is as follows. In Sect. 2, we prove that digitalism implies a form of pancomputationalism. In Sect. 3, we present a general version of the Zuse thesis and show that there is no logical or geometrical definitive reason to formulate it in terms of cellular automata—as digital physicists usually defend—instead of Turing machines, as some other authors believe: both formalisms are perfectly suitable for the purpose. In Sect. 4, we argue that Turing machines and cellular automata rely, respectively, on a dualism and a monism of properties. Finally, in Sect. 5, we explore the metaphysical implications of these claims. To conclude, we present some general remark.

2 Digitalism and Pancomputationalism

The first thesis of digital physics, which we have called digitalism, is that the universe is made out of bits, it is digital. Digitalism is well exemplified by one of the most celebrated slogan of digital physics, namely, Wheeler’s “It from bit”:

“It from bit” symbolizes the idea that every item of the physical world has at bottom - a very deep bottom, in most instances - an immaterial source and explanation; that which we call reality arises in the last analysis from the posing of yes-no questions and the registering of equipment-evoked responses (Wheeler 1990, p. 5).

In Sects. 4 and 5, we shall explain what kind of properties bits should have in order to support digital physics. To achieve that, we need at first to present a detailed description of all the three theoretical assumptions that ground digital physics. Accordingly, in this section, we develop a formal approach to digitalism. Our aim is to elucidate its relation with pancomputationalism. So let us begin with a general definition of digital structure.³

Definition 2.1

A point x in a structure A is said to be isolated if inside the topology over the domain of A there exists a neighbourhood of x which does not contain any other points of A except x. A structure is discrete if every point in its domain is isolated. A discrete structure A is digital if there is a finite subset B of its domain $D_A$, called a base, such that every element in $D_A$ is equal to a finite concatenation of elements in the base B.

Example 2.1

Any finite structure with a discrete topology is digital: for instance, a set $\{ 0, 1 \}$ with the Sierpinski topology $\{ \oslash , \{ 1 \}, \{ 0, 1 \} \}$ is digital. The set of natural numbers is discrete and, given a numerical systems, for instance, the binary system, it is also digital. Of course, intervals of real numbers are not digital, since not discrete.

The definition of digital structure presented here follows Maley (2011) and Frigerio et al. (2013). It differs, however, from both. On the one hand, our definition is more general than Maley’s definition because not only numbers, but whatever, can be the base of the structure. On the other hand, the definition given here is more direct than the one presented by Frigero et al., since it does not presuppose a system of codification. The aim of our definition is to allow a precise definition of digitalism.

Digitalism :

The physical world is isomorphic to a digital structure.

It is important to emphasis that digitalism does not assert that the world is made of concatenations of a finite base of objects. It affirms that the structure of the physical world can be put into a bijection to a digital structure in such a way that all of its properties and relations are preserved—this is what means to be isomorphic. Zuse (1967) wondered whether typical phenomena of electromagnetism, mechanics and thermodynamics are digital or not. From his analysis, he concluded that, in a sense, practically all physical observed phenomena allow a digital interpretation and, therefore, can be conceived as computational processes. This is the core of pancomputationalism. In order to elucidate this point, we need a notion of process.

Definition 2.2

A process is a function $P : I \rightarrow O$ such that its domain I is a set whose elements are called inputs and its codomain O is a set whose elements are called outputs and both I and O are subsets of a physical world.

Given this notion of process, which presupposes a concept of physical reality, we also assume some notion of computation, in order to define what are the computational processes.

Definition 2.3

A computer is a function $C : {\overline{I}} \rightarrow {\overline{O}}$ from a set of input symbols ${\overline{I}}$ to a set of output symbols ${\overline{O}}$ such that $C({\bar{x}})$ is generated from ${\bar{x}}$ via a computation. A process $P : I \rightarrow O$ is computational if P is generated by a computer C, i.e., $C({\bar{x}}) = P(x)$ for all $x \in I$, where ${\bar{x}}$ is a symbolic representation of x.

Pancomputationalism :

Physical objects perform computational processes.

To be precise, the term “pancomputationalism” designates many different positions. Piccinini (2015) calls the kind of pancomputacionalism here at issue ontic pancomputacionalism. According to ontic pancomputacionalism, each physical object accomplishes, in virtue of some elementary property, exactly one kind of computation at an instant of time. The main challenge to ontic pancomputacionalism is to provide an exact characterisation of the properties which enable objects to perform specific computations. We postpone the discussion of this problem to Sect. 5. By now, our aim is to exhibit an intrinsic relation between digitalism and pancomputationalism.

Theorem 2.1

If digitalism is true, then pancomputationalism is true.

Proof

Suppose that the whole physical reality R is isomorphic to a digital structure A whose domain is $D_A$. Then, for every process $P : I \rightarrow O$ such that $I \subseteq R$ and $O \subseteq R$, i.e., for every physical process, there is a function $f_{P} : A \rightarrow A$ and an isomorphism $\phi : R \rightarrow A$ such that $\phi (P(x)) = f_{P}(\phi (x))$ for all $x\in I$. Since $\phi$ is an isomorphism, we can think about the inverse $\phi ^{-1}$. Now, $\phi ^{-1}(\phi (P(x))) = P(x)$ and $\phi ^{-1}(\phi (P(x))) = \phi ^{-1}(f_{P}(\phi (x)))$. Hence, $P(x) = \phi ^{-1}(f_{P}(\phi (x)))$. But, $f_{P}(\phi (x)) \in D_A$, which means that $f_{P}(\phi (x))$ is a concatenation of elements from a finite base in $D_A$, say that, $f_{P}(\phi (x)) = a_1 \ldots a_n$. Now, we stipulate that ${\overline{x}} = a_1 \ldots a_n$ and $C = \phi ^{-1}$. Since $\phi (x)$ is defined for each $x \in I$ and $f_{P}(\phi (x))$ is defined for each $\phi (x)$, we deduce that, for each $x \in I$,

$$\begin{aligned} P(x) = \phi ^{-1}(f_{P}(\phi (x))) = C(f_{P}(\phi (x))) = C(a_1 \ldots a_n) = C({\overline{x}}). \end{aligned}$$

Therefore, C can be considered as our desired computer. $\square$

Remark 2.1

The method behind the proof above is to use the isomorphism between the physical reality and the alleged digital structure in order to define physical processes as computational ones. Note that in this proof we have made a crucial use of the digitalist hypothesis that the world is isomorphic to a structure composed of concatenations.

Hence, digitalism implies pancomputationalism, which, as we shall see shortly, grounds the Zuse thesis. The converse may not be true. The processes in the world may be computational and yet generated by analogical computers; in that case, the world would not be isomorphic to a digital structure. Furthermore, the notion of pancomputationalism deduced from pure digitalism does not encompass any notion of mechanicity: to be computational is not necessarily to be computable. It could be that the world were computational but with incomputable processes—Wheeler himself, for instance, adopts this position.⁴ To get a more substantial characterization of digital physics, we shall turn to the Zuse thesis.

3 The Zuse Thesis, Turing Machines and Cellular Automata

The third fundamental assumption of digital physics is the Zuse thesis, according to which the physical world is a universal computing machine. In order to rigorously characterise it, let us display some definitions.⁵

Definition 3.1

A process P is computable if P is generated by a computer M equivalent to a Turing machine. A computer U is said to be universal if every computable process P is generated by U, i.e., for every process P computable by some computer M equivalent to a Turing machine, we have that $U({\bar{x}}) = M({\bar{x}})$.

Given that, the Zuse thesis has now an exact sense.

The Zuse thesis :

The whole physical reality is a universal computer.

The formulation of this thesis relies on two previous assumptions, to know, Church thesis (Church 1936) and Kreisel thesis (Kreisel 1965).

Church thesis :

Every effectively calculable function is recursive.

Kreisel thesis :

Every discrete physical process is recursive.

Given Theorem 2.1, if we assume digitalism, we shall have that every physical process is computational. As we claimed in the previous section, this does not exclude the existence of incomputable processes in the world. With Church and Kreisel theses in hand that possibility can be rejected. The reason is the following. Every recursive function is computable, and vice versa (Turing 1936). In addition the converse of Church thesis is generally accepted, i.e., that recursive functions are effectively calculable. Taking this for granted, it follows, from Church and Kreisel theses, that the discrete physical processes are effectively calculable processes. This means by turns they can be generated via computers equivalent to Turing machines. Zuse (1967, 1993), and most of digital physicists, goes further: the best explanation for such a state of affair is the Zuse thesis. That is to say, the world actually is a universal computer.⁶

It should be clear that the Zuse thesis is not equivalent to Kreisel thesis. In virtue of the existence of incomputable properties of Turing machines—think, for instance, of the halting problem, if the Zuse thesis is true, then either Kreisel thesis is false or we must accept that incomputable processes are non-physical. Digital physics as conceived by Zuse adopts the latter option: only the functions that are generated by a universal computer are part of the physical world; everything else is outside it. To be precise, the factual Zuse conjecture—as he presented it in his writings—was that the world is a kind of cellular automata. In order to make sense of this choice, we need to go back to Turing’s and von Neumann’s analysis of computability.

Turing (1936) defined the model of computation today known as Turing machine. To get at such a model, he paid attention to the phenomenon of a person performing automatic calculations with pencil and paper. Turing believed that some aspects of this phenomenon were inessential for its mechanical character; e.g., the length of the paper, its dimensionality, the size of the letters, the material used to write, etc. By abstracting from these aspects, Turing obtained what we may call the Turing components, which define a person as a person that performs a computation:

• 1. A uni-dimensional linear tape divided into cells;

• 2. A head connected to the tape with the capacity of performing two operations: (1) To read and write symbols on the cells; (2) To move to the right and to the left on the cells.

In this setting, the configurations of Turing machines are descriptions of the tape and the head during computations. Hence, by looking at the configurations of computations, Turing concluded that the minimal parts interact in the following way:

T1 :

The head has a finite quantity of instructions inside it, which are ordered by a finite quantity of internal states;

T2 :

At each instant of time, the instructions inside the head completely determine the operations to be performed on the tape in the next instant;

T3 :

At each instant of time, the head follows one instruction to perform its operations on the tape;

T4 :

At each instant of time, one cell of the tape can be either read or wrote by the head;

T5 :

At each instant of time, one move can be made by the head on the tape.

From Turing’s analysis, we infer that the intended model of a universal computer is a structure in which the instructions are inside the head of the machine and the tape is linked to the head as shown in Fig. 1.⁷

Fig. 1

Turing machine intended model

Turing conditions T1–T5 make the intended model of Turing machines quite stable. That is to say, it does not matter whether a Turing machine has n tapes or just one, whether it has k heads or just one, whether it makes choices, etc.: the class of processes that Turing machines generate is always the same, namely, the recursive functions (cf. Sipser 2013, pp. 207–208). This is by turns the main motivation for the Church thesis.

Given Turing’s concept of computing machine, Von Neumann (1966) looked for an automaton capable of self-reproduction, a key feature of living beings. By pursuing this, he devised the concept of cellular automaton, as a computing structure with the following Neumann components:

• 1. An n-dimensional lattice, called grid, divided into cells;

• 2. A finite neighbourhood around each cell which permits to change symbols on the cell.

In this setting, the configurations of cellular automata are descriptions of the symbols on the cells at each instant of time, which involves following these rules:

N1 :

The grid has a finite quantity of instructions which are applied to update the cells according the configuration of their neighbourhood;

N2 :

At each instant of time, the instructions completely determine the changes to be performed inside the grid in the next instant;

N3 :

At each instant of time, the automaton follows one instruction to perform its changes;

N4 :

At each instant of time, each cell of the grid has one symbol;

N5 :

At each instant of time, a fixed finite number of the symbols on the cells is updated.

In, Fig. 2, we have the intended model of a cellular automaton with a two dimensional grid.⁸

Fig. 2

Cellular automaton intended model

If we imagine the movement of elementary particles as forming a calculating space, look to the spatial structure of cellular automata and assume that the symbols are the particles, then it seems natural to infer that the world is indeed a universal cellular automaton. This is the Zuse thesis. Let us show, however, that this preference for cellular automata instead of Turing machines has no mathematical obvious justification.

At first glance, it could appear that cellular automata are much more powerful than Turing machines because conditions N4 and N5 allow them to perform parallel computations, whereas T4 and T5 restrict the actions of Turing machines to sequential processing. Nonetheless, Turing machines and cellular automata are computationally equivalent (cf. Smith 1971). Moreover, in spite of the different geometrical dispositions, the symbols in both figures above are the same. Remember that we have said above that Turing machines are stable: What about to define a Turing machine with four tapes and stipulate that the head is in the second one? Figure 3 intended model emerges.

Fig. 3

Multi-tape Turing machine

Therefore, we get precisely the same geometrical representation in cellular automata and Turing machines. The only difference is that in Turing machines we have states and symbols and in cellular automata there are only symbols. By the way, if we look at the proofs of computational equivalence between Turing machines and cellular automata, the key passage usually covers a method to represent the location of the states of Turing machines, something that is missing in cellular automata (cf. Smith 1971). Nonetheless, this is not conclusive, because the computations of cellular automata presuppose a distinction between the cell that changes along the time and its neighbourhood, as it is expressed in the distinction between the two Neumann components. This may imply a kind of necessary dual distinction analogous to the head and tape duality of Turing components. In order to assess this question, we need a careful logical analysis.

4 Digital Monism and Dualism

In the previous section we have shown that, as specifications of the Zuse thesis, Turing machines and cellular automata provide two approaches intuitively different but mathematically equivalent. We now turn to the main question of this article: What kind of properties should the physical world instantiate to be a realisation of a universal computer? In agreement with a standard criterion of ontological commitment (Quine 1953; van Inwagen 1998), we shall respond to this question by analysing the logical form of cellular automata and Turing machines; afterwards, we shall try to interpret them. Let us begin with a little bit of terminology.

Definition 4.1

A digital structure A is monistic if its domain $D_A$ has only one sort, i.e., concatenations of elements from a finite base set. If $D_A$ has instead two sorts of concatenations of elements from the base, we say that A is dualistic.

The technical term sort—from model theory (cf. Hodges 1993)—is used here to express the idea of something sharing a certain property. According to the previous definition, a monistic structure is composed by objects of exactly one kind, i.e., concatenations of the elements of its base. The existence of two sorts in a dualistic structure indicates that the elements of the base cannot be conceived as a unique kind of object, because they instantiate two distinct kinds of properties, expressed by the two sorts. In order to denote a monistic structure, a first-order language for Turing machines and cellular automata must have only one predicate to describe the computations, while in order to denote a dualistic structure they must have exactly two predicates. The number of predicates indicates how many sorts the structure in question has and so establishes how many common properties are shared by all the elements of the base. To formalise these intuitions, we are going to define first-order languages for Turing machines and cellular automata. We follow the mathematical approach originally presented by de Araújo and Carnielli (2012), making changes associated to the ontological problem at stake in this article.

Definition 4.2

A computational language ${\mathcal {L}}$ is a first-order language with identity whose signature contains the set ${\mathcal {S}} = \{ 0, +1, -1, < \}$, wherein the elements are, respectively, the constant zero, the unary function symbols successor and (truncated) predecessor, and the binary relation symbol strict order. A computational language ${\mathcal {L}}$ is said to be monistic if it has only one more predicate M with an ariety defined according to the model of computation; ${\mathcal {L}}$ is called dualistic if it has two predicates E and S with arities also associated to the model of computation in question.

The idea behind the concept of computational language is to represent the locations in the space $c_0, c_1, \ldots$ and the instants of time $t_0, t_1, \ldots$ with the natural numbers in the indexes. The signature ${\mathcal {S}} = \{ 0, {+1}, {-1}, < \}$ has this role. Likewise, we can also represent the symbols $s_0, s_1, \ldots , s_n$ and states $e_0, e_1, \ldots , e_m$. We only need to specify which parameters in M or E and S represent what. For instance, in the case of a Turing machine, we can establish that $M_T(e, c, s, d, t)$ represents that the machine has the state e inside its head at location c, and the symbol s on the cell number d, all of this at instant t. Using this convention and assuming that the first cell of the tape is at position 0, the configuration in Fig. 1—at instant, say, 10—can be represented by the following first-order formula:

$$\begin{aligned} M_T(0,1,0,1,10) \wedge M_T(0,1,1,2,10) \wedge M_T(0,1,2,3,10) \wedge \cdots \wedge M_T(0,1,8,9,10). \end{aligned}$$

Instead of a monistic language, we could use a dualistic one, $E_T(e,c,t)$ and $S_T(s,d,t)$, with the same kind of parameters as above. In this case, the configuration in Fig. 1 at instant 10 can be expressed by:

$$\begin{aligned} E_T(0,1,10) \wedge S_T(1,2,10) \wedge S_T(2,3,10) \wedge \cdots \wedge S_T(8,9,10). \end{aligned}$$

Remark 4.1

In a sense, both formulas above are logically equivalent, but they are in two different languages for Turing machines. The first one has just one sort of predicate, $M_T$, the second has two sorts, $E_T$ and $S_T$.

We can develop the same approach for cellular automata. We establish that $M_C(s, c, t)$ represents that the machine has symbol s located at cell c at instant of time t. In order to deal with the fact that cellular automata can be n-dimensional, we make the convention of representing the cells with an oblique path from up to down. That is, the cell $a_{00}$ is represented by $c = 0$, $a_{01}$ by $c = 1$, $a_{10}$ by $c = 2$, $a_{02}$ by $c = 3$, $a_{11}$ by $c = 4$, and so on. Using this convention, the configuration in Fig. 1 can be represented by the following first-order formula at instant, say, 10:

$$\begin{aligned} M_C(0,7,10) \wedge M_C(1,1,10) \wedge M_C(2,3,10) \wedge M_C(3,6,10) \wedge \cdots \wedge M_C(8,4,10). \end{aligned}$$

A dualistic language for cellular automata may have, for example, $E_C(e,c,t)$ and $S_C(s,d,t)$, where e is the symbol that changes according to the symbol s in the neighbourhood, c and d represent the cells in the grid and t an instant of time. In this formalization, the Fig. 2 can be represented by:

$$\begin{aligned} E_T(0,7,10) \wedge S_C(1,1,10) \wedge S_C(2,3,10) \wedge S_C(3,6,10) \wedge \cdots \wedge S_C(8,4,10). \end{aligned}$$

Remark 4.2

Note again that both formulas above are logically equivalent, but in the case of cellular automata there is no real difference between the formulas, just a change of symbols.

The next result responds the question about how many sorts are necessary and sufficient to represent computations of Turing machines and cellular automata.

Theorem 4.1

There is a class of first-order structures ${\mathcal {B}}$ that correspond to computations of cellular automata and ${\mathcal {B}}$ interprets the monistic computational language with predicate $M_C(s, c, t)$ and all the others possible structures that correspond to its computations are equivalent to this monistic language. On the other hand, a class of first-order structures ${\mathcal {A}}$ corresponds to the class of computations of Turing machines if, and only if, ${\mathcal {A}}$ is equivalent to the class of structures that interpret the dualistic computational language with predicates $E_T(e,c,t)$ and $S_T(s,d,t)$.

Proof

Here we assume an intuitive notion of correspondence between computations and structures that interpret computational languages in order to sketch the main steps in the proof of this theorem.⁹ The part of the theorem about cellular automata is the easy one. To construct a structure A that interprets the monistic computational language with predicate $M_C(s, c, t)$ for a cellular automaton C, we consider the domain $D_A$ as being the set of natural numbers ${\mathbb {N}}$. Thus, the symbols $0, +1, -1, <$ can be interpreted in the regular way as, respectively, the number zero, the successor function, the truncated predecessor function and the strict order on the natural numbers. Thus, we define the interpretation of $M_C(s, c, t)$ as we have outlined above. According to this formulation, an instruction of C with, for instance, one dimension is expressed by a formula

$$\begin{aligned}&M_C(u, c-1, t) \,\wedge\, M_C(s, c, t) \,\wedge\, M_C(r, c+1, t) \\&\quad \rightarrow M_C(u, c-1, t+1) \,\wedge\, M_C(s', c, t+1) \,\wedge\, M_C(r, c+1, t+1), \end{aligned}$$

meaning that if the machine has the symbols u, s, r on the consecutive cells $c-1, c, c+1$ at time t, then it has the symbols $u, s', r$ on the consecutive cells $c-1, c, c+1$ at time $t +1$. This clearly enables us to represent the computations in a monistic language. Thus, we have a monistic structure associated to the computations of cellular automata. Besides, since there is a universal cellular automaton with dimension one (cf. Smith 1971), all the others possible structures that correspond to computations of cellular automata are equivalent to the monistic language defined above.

To prove that the structures that correspond to computations of Turing machines are dualistic we need much more effort. We prove two lemmas by reductio ad absurdum. First, we prove that there is no such a class of structures defined over a signature with unary relational symbols for each of the sorts of a Turing machine, where, say, H, T, E, I are, respectively, predicates for the sorts state, symbol, space and time. The reason is that the Turing conditions T1–T5 impose that the states and symbols should be related in some way.¹⁰ Second, we prove that there is no class of structures that correspond to computations of Turing machines and are defined over a signature with relational symbols that have exactly one parameter for each sort of a Turing machine, for instance, M(e, s, c, t) where e represents a state, s a symbol, c a cell and t an instant. This can be proved to be impossible due to the fact that it would imply that at each instant of time the machine has one state inside its head but it would be located at different cells, what is not allowed by Turing conditions.¹¹ From these two steps, by analysing the possible combination of parameter associated to computations of Turing machines, we verify that a monistic language for Turing machines should has a predicate like the one $M_T(e, c, s, d, t)$ exhibited above, which is equivalent to a dualistic language with predicates $E_T(e,c,t)$ and $S_T(s,d,t)$. In such a dualistic language, an instruction of a Turing machine has the form

$$\begin{aligned} E_T(e,c,t) \wedge S_T(s,c,t) \rightarrow E_T(e',c',t+1) \wedge S_T(s',c,t+1), \end{aligned}$$

meaning that if the machine is in the state e at position c and in this cell the symbol s is written at time t, then the machine will be in state $e'$ and at cell $c'$ with either $c' = c-1$ or $c' = c+1$, according the instruction says to it to go to the left or to the right, and the machine has the symbol $s'$ at cell c, because it wrote something on the that cell, all of this at instant $t+1$. This clearly enables us to represent the computations of Turing machines in a dualistic language. Therefore, the structures that correspond to computations of Turing machines are actually dualistic.¹² $\square$

It is important to emphasise that there is a lot of possible formulations of first-order languages for cellular automata. For example, we could ask about the possibility of a language with predicates P(s, t) and R(c, t) , where the symbols and cells are related to time alone. Theorem 4.1 proves that there is no structure that interprets this language and corresponds to computations of cellular automata. Why? Because the language of cellular automata must be essentially monistic, it must have formulas that are equivalent to the monistic one $M_C(s, c, t)$. The same is true with respect to Turing machines. For instance, we could ask about the representation of computations of Turing machines in a language with predicates A(e, t), B(s, c) and C(e, s), where we would like to highlight that the states are related to time alone, the symbols to the space and, to make a connection, the states are related to the symbols. Theorem 4.1 shows that this is not possible. All of the languages that correspond to computations of Turing machines should have the states, symbols, cells and instants as in $H_T(e,c,t)$ and $S_T(s,c,t)$. Why? Because states and symbols require their own parameterisation in the space–time. In a nutshell, the language of Turing machines is necessarily dualistic.

We are now ready to provide a more precise ontological interpretation of the distinction between monistic and dualistic structures. In order to do this, we adopt a simple analytic tool originally employed by Schaffer (2015). According to him, from an ontological point of view, the distinction between monism and dualism (or other forms of pluralism) is always relative to two terms: the term to which is attributed “oneness” or “dualness” (or “pluralness”), which is called the target, and the unit according to which the target is counted. In this context, the target is the set of fundamental properties that must be instantiated by physical objects to make digital physics true. Since, according to digitalism, a physical object is fundamentally composed of bits, we can say that the target is the set of properties that must be instantiated by bits. Concerning the unit, our analysis over monistic and dualistic structures provided us with a reliable method for counting kinds of properties, that is, the number of predicates of a first-order language for Turing machines and cellular automata. Therefore, on the one hand, we interpret the fact that cellular automata structure can be expressed by a single predicate as evidence that their physical realisations (according to the Zuse thesis, the entire universe itself) share exactly one kind of fundamental property. On the other hand, we believe that the fact that Turing machines structure must be expressed through two predicates suggests that the physical realisations of Turing machines (included, obviously, the giant Turing machine postulated by the Zuse thesis) have to reflect a certain dualism of properties. In next section, we shall explore some metaphysical implications of these ontological commitments.

5 Metaphysical Implications of Digital Physics

At the end of the previous section, we have determined the number of fundamental properties that must be instantiated by physical objects in order to make digital physics true. However, we are not only interested in knowing the number of the fundamental properties, but in what kind of properties they are too. We believe that we can get some insight on this question by interpreting results obtained so far in the light of the contemporary debate about physicalism and the ontological status of the laws of nature. More precisely, we hold that, in digital physics, the choice of a formalism instead of the others entails a specific position in these metaphysical debates. Thus, we are going to argue that some of the metaphysical options available to digital physicists which adopt the cellular automaton model are strikingly incompatible with some of the options available to those who adopt the Turing machine model.

The monistic interpretation of digital physics attached to the model of cellular automata maintains that the entire universe is composed, at the very bottom, of elementary entities—namely, symbols -, which are to some extent identical to each other. This kind of monism seems to be implicit in Wheeler’s slogan and it is intuitively supported by a commonly accepted physicalist view, for which non-elementary properties are always realisable by fundamental, microphysical, properties (cf. Kim 1998; Stoljar 2010).¹³ These fundamental properties are generally assumed to be responsible for the ultimate causal structure of the universe. If we combine this interpretation with another commonly accepted physicalist principle, namely, the causal closure of the physical, we obtain that, according to the monist interpretation of digital physics, symbols are causally sufficient for the instantiation of any physical (and thus also biological or psychological) process. Specific computations would emerge, according to the monistic interpretation of digital physics, from local interactions between symbols (cf. Wolfram 2002). This view, in our opinion, supports a certain version of Humean supervenience (cf. Lewis 1986, 1994), namely, the thesis according to which the laws of nature are not included into the basic furniture of the world. If, as a matter of fact, all of what exists at the very bottom of the universe is a concatenation of symbols, then laws of nature—that is, according to the formalism, the rules of the universal cellular automaton—are not primitive, but supervenient on particular interactions or, even, merely in “the eye of the beholder”. Accordingly, cellular automata monism excludes the interpretation of cellular automata rules in terms of universals or other abstracta. Since, in fact, the structure of cellular automata has only one sort, which means that the objects that compose it share exactly one kind of property, it is no clear how such a structure might instantiate universals, in addition to the local interactions between symbols.

On the other hand, the dualistic interpretation of digital physics prescribes that, in order to be computable, any non-elementary property must be realised by a conjunction of symbols and states of a Turing machine, whose properties are not reducible to each other. According to the metaphysical framework that we have outlined, this is compatible with two interpretations: realism—or, at least, antireductionism—about the laws of nature and panpsychism. The former option consists in taking the collection of the states of the universal Turing machine as the rules, or the laws, of the universe. This perspective is diametrically opposed to Humean supervenience, and well exemplifies the metaphysical trade-off involved in the choice of a specific formalism for digital physics. According to this perspective, in fact, laws are real and fundamental. States could be conceived as relational properties, which establish beforehand what kind of physical process is admitted—and what is not—in specific regions of the universe.¹⁴ Even though Humean supervenience guarantees a more economical ontology, some authors (like Maudlin 2007, or Carroll 2008) have quite convincingly argued that it is inadequate to account for the distinction between nomological and merely accidental regularities. These authors argue—from slightly different standpoints—that, to account for this distinction, laws must be considered as non-reducible entities. “Turing machine realism” about laws of nature offers a way of characterising this intuition.

The second metaphysical option available to those who adopt the Turing machine model of digital physics is panpsychism. Since it is a more controversial option, we shall discuss it in some detail. Panpsychism is, in a nutshell, the thesis that “some fundamental physical entities have mental states” (Chalmers 2016, p. 19). It may be considered—although other interpretations are possible—as a kind of broad physicalism (Chalmers 2016, pp. 27–28; see also Strawson 2006). More precisely, panpsychism is a physicalism that includes as fundamental properties, in addition to those which are admitted by physical theories (see note 12), phenomenal properties instantiated together with the physical properties. Russell (1927), among others, defended this perspective. For Russell, panpsychism provides an elegant solution to the problem of consciousness: micro-phenomenal properties of matter are responsible for macro-phenomenal properties, just like micro-physical properties of matter are responsible for macro-physical properties. The relationship between micro-physical and micro-phenomenal properties (and, consequently, macro-physical and macro-phenomenal properties) can be interpreted in various ways (cf. Stoljar 2013). In line with some interpretations (cf. Locke 1975; Lewis 2009), phenomenal properties are dispositional properties realised by physical properties or vice versa, in such a way that one kind of property underlies the other. We might call this conception dispositional panpsychism. According to an alternative interpretation, called by Chalmers Russellian property dualism (2016, p. 35), the two kinds of properties are equally fundamental, and none is grounded in the other (despite their co-instantiation). Physical and phenomenal properties are, according to Russellian property dualism, mutually conditioning, and the causal structure of reality is the result of the combined action of both—in different proportions, depending on the ontological degree of complexity (corresponding to, respectively, physical, biological and psychological domains).

Although dispositional panpsychism is compatible with the Turing machine model, we believe that Russellian property dualism is the best way to conceive the dualistic ontology of digital physics. This is because, according to this ontology, symbols and states do not show any logical priority one over the other. Assuming that the entire universe is a giant realisation of a Turing machine, symbols could be considered as the basic constituents of the physical properties (as also assumed by the monistic interpretation) and states could be conceived as the basic constituents of the phenomenal properties. The universe would be unitary—as a whole and with respect to its components, but any computation in it would instantiate processes that are both physical and phenomenal, in the sense that they would cause—at least to some extent—certain modification in both kinds of properties of the world. In light of digitalism, no one kind of property would be more fundamental than the other: if interpreted as two necessary aspects of Wheeler’s bits, physical properties could not subsist without phenomenal properties and vice versa. While the monistic interpretation of digital physics satisfies quite well the necessities of those—like Wolfram (2002) and many of his followers (see, for instance, Tagliabue 2013)—who aim to explain complexity from a minimal physicalist base, the panpsychist conception here presented could be attractive to those who are interested in integrating consciousness in a highly unified conception of the universe without invoking concepts like that of emergence (cf. Nagel 1979).¹⁵

6 Conclusion

In the present article, we have spelt out the logical connections between the fundamental assumptions of digital physics. In Sect. 2, we proved that there is a logical entailment from digitalism to a broad pancomputationalism. In Sect. 3, we argued that the Zuse thesis can be seen as a restriction of pancomputationalism to the realm of computable processes and so it puts digitalism on solid ground. Nonetheless, this last step has metaphysical implications. In the last two Sects. 4 and 5, we showed that different metaphysical conceptions are compatible with digital physics, but the freedom to choose among them depends on the prior choice of a proper model of the computational processes. We do not believe that there are conclusive reasons for preferring one formalism over the other: cellular automata and Turing machines are computationally equivalent, so they both allows to interpret the Zuse thesis equally well.

Metaphysical hypotheses are usually not taken as conclusive reasons for the adoption of a theory, or a model, rather than another. Yet, when one is faced to such an abstract theory like digital physics, reasoning about its ultimate implications can help to understand what it does mean to endorse it. The logical and mathematical indetermination about what is the appropriate model for digital physics reinforces the impression that, contrarily to what could seem at first glance, metaphysical preferences not only contribute to understand the implications of a specific model, but also guide the choice of it.

Appendix

In this appendix, we provide the details of the Proof of Theorem 4.1. We assume the definitions of Turing structure and computations as they are defined in de Araújo and Carnielli (2012). Let us begin by showing that the sorts of Turing structures cannot be approached in an isolated form. That is to say, states, symbols, cells and instants of computations must be related.

Lemma 6.1

There is no class of Turing structures ${\mathcal {A}}$ that corresponds to the class of Turing computations ${\mathcal {C}}$ such that ${\mathcal {A}}$ is defined over a signature with unary relational symbols for each of the sorts of a Turing machine.

Proof

The proof is by reductio ad absurdum. Suppose that there is a class of Turing structures ${\mathcal {A}}$ that corresponds to the class of Turing computations ${\mathcal {C}}$ and ${\mathcal {A}}$ is defined over a signature with unary relational symbols for each of the sorts of a Turing machine. Let us say, without loss of generality, that the signature of ${\mathcal {A}}$ is

$$\begin{aligned} {\mathcal {S}} = \{0,S,P,<,H,T,E,I\}, \end{aligned}$$

where H, T, E, I are, respectively, unary relational symbols for the sorts state, symbol, space and time. This choice of signature indeed does not make our proof below to loose generality, since in the case of the signature of ${\mathcal {A}}$ to have more or less symbols it must have at least the four symbols for each sort and names for the particular states, symbols, cells and instants, and so the method of proof below will be applicable to such a case as well.

Because ${\mathcal {A}}$ corresponds to ${\mathcal {C}}$, for each $t \in {\mathbb {N}}$ and for each Turing structure $A_{M}^{\alpha } \in {\mathcal {A}}$, there is a formula $\phi$ over ${\mathcal {S}}$ such that

$$\begin{aligned} A_{M}^{\alpha }\,\vDash\, \phi \,{\text{if}},\,{\text{and}}\,{\text{only}}\,{\text{if,}}\, M^{\alpha }(t)=(c,e,T). \end{aligned}$$

Let M be a machine that has among its instruction this one

$$\begin{aligned} (0,1,0,0,\triangleleft ). \end{aligned}$$

Consider the Turing structure $A_{M}^{\alpha }$ associated to the computation of M, for the input $\alpha = 1$. Given the initial configuration of $M^{\alpha }$, it must be true that $A_{M}^{\alpha }\,\vDash\, T(S0) \wedge E(0) \wedge I(0)$, that is to say, M has the symbol 1 on the tape at the cell 0 in the instant 0. By applying the instruction $(0,1,0,0,\triangleleft )$, we also get at $A_{M}^{\alpha }\,\vDash\, T(0)\wedge E(P0)\wedge I(S0)$, which means that M erased the symbol 1 and it is still on cell 0, because the tape is truncated to the left, but now M is at the instant 1. Hence, $A_{M}^{\alpha } \,\vDash\, T(0) \wedge T(S0) \wedge E(0) \wedge I(0)$, i.e., the machine M has the symbols 0 and 1 on the cell 0 at the instant of time 0. But Turing conditions T1–T5 say that the machine M cannot have different symbols on one cell at the same instant of time. Therefore, we must have $0 = 1$, what is a contradiction. $\square$

The second fact shows that there is no Turing structure that has all the sorts in just one predicate. This means that states, symbols, cells and instants cannot be regarded as a unique object. That is to say, the minimal parts defined by Turing, head and tape, are necessarily different.

Lemma 6.2

There is no class of Turing structures ${\mathcal {A}}$ that corresponds to the class of Turing computations ${\mathcal {C}}$ such that ${\mathcal {A}}$ is defined over a signature with relational symbols that have exactly one parameter for each sort of a Turing machine.

Proof

The proof is once again by reductio ad absurdum. Suppose the contrary of the lemma. Due to the same reason of the previous proof, we may consider, without lost of generality, the signature

$$\begin{aligned} {\mathcal {S}} = \{S,P,<,A\},\end{aligned}$$

where A is a relation symbol of ariety 4, with one parameter for states, one for symbols, one for cells and one for instants. Consider the machine M that has among its instruction this one

$$\begin{aligned} (0,1,0,1,\triangleleft ). \end{aligned}$$

As before, take the computation for the input $\alpha = 1$. Given the initial configuration of $M^{\alpha }$, it must be true that $A_{M}^{\alpha } \,\vDash\, A(0,S0,0,0)$. By applying the instruction $(0,1,0,1,\triangleleft )$, we also get at $A_{M}^{\alpha }\,\vDash\, A(0,S0,P0,S0)$, i.e., $A_{M}^{\alpha }\,\vDash\, A(0,S0,0,S0)$. Thus, nothing has happened at all, except that the time has passed. The machine will be forever reprinting 1 on the cell 0. But the tape of the machine M is infinite, and, by definition, M has the empty symbol 0 printed on each cell $c>0$. Thus, we have

$$\begin{aligned} A_{M}^{\alpha }\,\vDash\, A(0,0,S0,0), \quad A_{M}^{\alpha }\,\vDash\, A(0,0,SS0,0), \ldots \end{aligned}$$

but also

$$\begin{aligned} A_{M}^{\alpha }\,\vDash\, A(0,0,S0,S0),\quad A_{M}^{\alpha }\,\vDash\, A(0,0,SS0,S0), \ldots \end{aligned}$$

and so on.

This means that at each instant of time the machine has one state within its head but it is located at an infinity quantity of cells. Turing conditions T1–T5 says that this is impossible. Therefore, we have an absurd. $\square$

We turn now to the second part of Theorem 4.1, which here is stated as particular theorem.

Theorem 6.1

A class of first-order structures ${\mathcal {A}}$ corresponds to the class of Turing computations ${\mathcal {C}}$ if, and only if, ${\mathcal {A}}$ is equivalent to the class of Turing structures ${\mathcal {M}}$.

Proof

Let ${\mathcal {A}}$ be a class of first-order structures with signature ${\mathcal {S}}$ that corresponds to ${\mathcal {C}}$. Take a Turing computation $M^{\alpha } \in {\mathcal {C}}$. By the Lemma 6.1, ${\mathcal {S}}$ cannot have only unary relational symbols for each isolated sort of M. Thus, ${\mathcal {S}}$ must have, at least, relational symbols of ariety greater than or equal to 2. Besides, ${\mathcal {S}}$ must have relational symbols with parameters for states and symbols, otherwise, it would be impossible to represent the computations of M. Say that ${\mathcal {S}}$ has the relational symbol $A(\tau _{1},\tau _{2},\ldots ,\tau _{n})$, where $\tau _{1}$ is a parameter for states, $\tau _{2}$ for symbols and $\tau _{3},\ldots ,\tau _{n}$ are other parameters of A. Among $\tau _{3},\ldots ,\tau _{n}$ some parameters must, for sure, represent cells, otherwise, it would be impossible to determine the position of M during a computation. Let us suppose that $\tau _{3}$ is a parameter for cells. What about parameters for instants? Since the correspondence is valid for ${\mathcal {A}}$, it must be able to represent the time as well. Let us assume the $\tau _{4}$ is a parameter for instants. In this way, we have $A(\tau _{1},\tau _{2},\tau _{3},\tau _{4},\ldots ,\tau _{n})$ with just one parameter for states, one for symbols, one for cells and one for instants. By Lemma 6.2, it must exist another parameter $\tau _i$, $5\, \le\, i\, \le\, n$, that represents something else. Let us analyse what kind of thing, without lost of generality, $\tau _5$ represents.

For the sake of concreteness, suppose that M has the instruction $(0,0,1,1,\triangleleft )$. Consider the computation for the input $\alpha = 0$. Since ${\mathcal {A}}$ corresponds to ${\mathcal {C}}$, the initial configuration of $M^{\alpha }$ ensures that $A^{\alpha }_{M} \,\vDash\, A(0,0,0,0,\tau _{5},\ldots ,\tau _{n})$. By applying the instruction $(0,0,1,1,\triangleleft )$, we have $A^{\alpha }_{M} \,\vDash\, A(S0,S0,0,S0,\tau _{5},\ldots ,\tau _{n})$.

Could $\tau _{5}$ be a parameter for states? Yes, it could. If $\tau _{5}$ were a state, then, at the instant 0, it must be that $\tau _{5} = 0$, because the machine cannot have different states within its head at a given instant of time—remember Turing conditions T1–T5. By the same reason, at the instant 1, it must be that $\tau _{5} = S0$. In general, if $\tau _{5}$ is a state, $\tau _{5} = \tau _{1}$. Hence, to add new parameters for states does not change the logical properties of $A^{\alpha }_{M}$, for it continues to be equivalent to a structure with a relation symbol of ariety 4, with one parameter for states, one for symbols, one for cells and one for instants.

What about $\tau _{5}$ as a parameter for symbol? If $\tau _{5}$ is the symbol on the cell that $\tau _{3}$ represents, then, at the instant 0, it must be that $\tau _{5} = 0$, and at the instant 1 it must be that $\tau _{5} = S0$. The reason is analogous to the last case: the conditions T1–T5 forbid to have two different symbols on the same cell. Hence, if $\tau _{5}$ is a symbol on the cell $\tau _{3}$, $\tau _{5} = \tau _{2}$, and we gain nothing. If $\tau _{5}$ is the symbol on the cell that is not represented by $\tau _{3}$, where is such a symbol? It must exist another parameter in the relation $A(\tau _{1},\ldots ,\tau _{n})$, say, $\tau _{6}$ that represents the location of $\tau _{5}$. In our particular example, we have, then, $A^{\alpha }_{M} \,\vDash\, A(0,0,0,0,0,S0,\tau _7,\ldots ,\tau _{n})$ and $A^{\alpha }_{M} \,\vDash\, A(S0,S0,0,S0,0,S0,\tau _7,\ldots ,\tau _{n})$. Except for the terms $\tau _7, \ldots , \tau _{n}$, these sentences are, respectively, equivalent to $E_T(0,0,0) \wedge S_T(0,0,0) \wedge S_T(0,S0,0)$ and $E_T(S0,0,S0) \wedge S_T(S0,0,S0) \wedge S_T(0,S0,S0)$ from our standard Turing language. Hence, if $\tau _{5}$ is a parameter for symbols, our theorem is true in that case too.

Now let us think of $\tau _{5}$ as a parameter for the space. If $\tau _{5}$ represents the location of the head, $\tau _{5} = \tau _{3}$, because the machine cannot be in two different places. If $\tau _{5}$ represents the location of the symbol $\tau _{2}$, it could be that $\tau _{5} = \tau _{3}$ or not, since the same symbol might be located at different cells; for instance, we have $A^{\alpha }_{M} \,\vDash\, A(0,0,0,0,S0,\tau _6,\ldots ,\tau _{n})$, meaning that at the instant 0, the machine has the symbol 0 on the cells 0 and 1. But this does not matter, as the formula $E_T(0,0,0) \wedge S_T(0,0,0) \wedge S_T(0,S0,0)$ from our standard Turing language is equivalent to $A(0,0,0,0,S0,\tau _6,\ldots ,\tau _{n})$ again. If $\tau _{5}$ does not represent either the location of the head or the location of the symbol $\tau _{2}$, we can even so define a formula of the standard Turing language that expresses this fact—the argument is analogous.

To conclude, it remains to look at the case in which $\tau _{5}$ is a parameter for the time. This is the easiest one, for if $\tau _{5}$ were to represent an instant of time, $A(\tau _{1},\tau _{2},\tau _{3},\tau _{4},\tau _{5},\ldots ,\tau _{n})$ would mean that some of the terms (maybe all of them) $\tau _i$ for $i = 1, 2, 3$ is the same at the instants $\tau _{4}$ and $\tau _{5}$, and we gain nothing at all.

Our proof is independent of the machine M presented above—we have used it just to make clear the argument. Therefore, since ${\mathcal {A}}$ correspond to ${\mathcal {C}}$, for each formula $\phi$ over the signature ${\mathcal {S}}$ of ${\mathcal {A}}$ that is true over $A^{\alpha }_{M} \in {\mathcal {A}}$, we find a formula $\psi$ of the standard Turing language that also is true with respect to the Turing structure $A^{\alpha }_{M}$, and vice versa.