Is VonNeumann's universal constructor ontologically distinct from the universal Turing machine?

Question

I have recently been reading and watching Chiara's take on universal constructor theory. I knew about VonNeumann probes, as for instance described in Asimov's 2001 sequence. I hadn't taken in his constructor theory in a cellular automaton environment, as proposing something computationally discontinuous to a Turing machine.. if it is.

My intuition, is that there is a difference in the topological transformations VonNeumann and Turing machines are capable of, that can be related to number theory. The practical mechanism of the Turing machine tape has always as I understand it in philosophy, not been understood as limiting the capacity to simulate all other machines and environments, including other machines. So if there is a limit here on the power of Turing machines, what is it? And why isn't it better known?

Chiara is suggesting universal constructors may solve quantum gravity issues, and concerns around minds, meaning and Searle's Chinese room critique of computation as consciousness. It certainly sounds promising.

Can anyone help me understand exactly what the differences are between VonNeumann & Turing machines? Are they fundamentally -ontologically- different, or can the former be simulated by the latter? What are the relevant papers or other texts by VonNeumann? What else should I be reading or watching to understand this area?

Answer 1

Visiting the Church-Turing Thesis page I see: "computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that a function is computable if and only if it has an algorithm. Note that an algorithm in this sense is understood to be a sequence of steps a person with unlimited time and an unlimited supply of pen and paper could follow."

And the C-T implications for philosophy:

1. The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics.
2. The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves random real numbers, as opposed to computable reals, would fall into this category.
3. The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas and Roger Penrose have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation.

There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.

So given "Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949, was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection"...

...I think to show automata (which is what Von Nuemann was using to build his universal constructor) and TM are ontologically distinct, you'd have to show that automata can be built from "non-algorithmic" (non-infinite-pen-and-paper-maths) construction. Otherwise, all the logic of pen-and-paper maths is going to carry over and supervene on both. There is a possible issue that we define algorithms such that they are able to be carried out by Turing machines though.

See the 2nd answer and comments on this CS.SE post for some more discussion. Also see the hierarchy towards the bottom where automata and TM's have the same maximum powers.

In conclusion, as a non expert, I think both Von Neumann's automata and TM's are subject to the rules of mathematics that we can write down. It remains to be seen if there are more powerful modes of computation that don't use oracle black boxes that go beyond this. I mean we can say our computers are finite automata, and that infinite tape Turing machines are of course different than this. But to say TM's have ontologically different constructions and possibilities to automata once both are allowed to be infinite I think the answer is no, based on how they both "reduce" to pen and paper maths. I am comparing infinite automata to infinte tape TM's. A finite automata can't doing everything a finite TM can do, but that isn't the issue imo.

In my mind, the constructor theory of Deutsch and Marletto is a deeper version of the limits pen-and-paper maths puts on algorithms, automata, and TM's. It would be a way to generate all possible physical transformations allowable in the universe in a different way than the set of writing down all possible algorithms for example. Von Neumann was using automata to build his constructors, so his constructors must play by the rules of automata/computation/writing down maths.

Answer 2

Can anyone help me understand exactly what the differences are between VonNeumann & Turing machines? Are they fundamentally -ontologically- different, or can the former be simulated by the latter?

There is a distinction. A TM, particularly a universal TM, is an abstraction that models physical computation and is concerned with the notion of effective computability and quickly forms the basis for responding to the very important decision problem, the Entscheidungsproblem. vNUC on the other hand is a different type of abstract machine. It's primary purpose is to realize the modeling of a physical machine that replicate itself. The former is a theory that tries to generalize computation, whereas the latter is a theory that tries to show how physical systems can replicate (which was undertaken by JvN before DNA was discovered). Thus, while both types of abstract machines, they fill different theoretical intentions. Of interest to you should be the CS notion of the quine which is an algorithmic equivalent.

My intuition, is that there is a difference in the topological transformations VonNeumann and Turing machines are capable of, that can be related to number theory.

It might be more accurate to say that your intuitions on topology are confirmed that a (universal) TM is an extension of what is a finite state machine that allows for general computability where as the vNUC is much more complicated because it seeks to address an actual architecture for the task of self-replication. That is, a UTM is a model for how any algorithm that can be effectively computed can be described, where as the vNUC is dedicated to the task of replicating itself in the physical world.

What you have to understand is that there's a difference between the relatively simple formalisms of TMs and lamda-calculi, and actual implementation of physical artifacts. The former is mathematically preoccupied and the latter is a physically preoccupied. This is a central theme in physical computation (SEP). JvN's contributions like his involvement with EDVAC and ENIAC and his von Neumann's architecture aren't on the mathematical logic side of CS, but on the implementation side. In fact, he thought the TM was 'Simple and Neat'.

From the SEP article:

Computation may be studied mathematically by formally defining computational objects, such as algorithms and Turing machines, and proving theorems about their properties. The mathematical theory of computation is a well-established branch of mathematics. It deals with computation in the abstract, without regard to physical implementation.

By contrast, most uses of computation in science and ordinary practice deal with concrete computation: computation in physical systems such as computers and brains. Concrete computation is closely related to abstract computation: we speak of physical systems as running an algorithm or as implementing a Turing machine, for example. But the relationship between concrete computation and abstract computation is not part of the mathematical theory of computation and requires further investigation

This dichotomy may sound suspiciously familiar. The software-hardware distinction, in fact, arouses notions of mind-body duality. There is computer design, and computer implementation, and there are different notions of correctness for each. (See Turner's Computational Artifacts (GB) for more information.) So, do they possess a different ontology? Subtly, yes. TMs are mathematical abstractions (as abstracted from actual mathematicians) where as the vNUC is concrete abstraction (as in a model of physical system). We have fundamentally different ontologies for concrete systems than abstract ones, from systems of the mind and systems of the body. Because both are framed in terms of computation, they might seem similar, but that similarity betrays a deeper philosophical truth about what appears to be the dualistic nature of dualist systems. (I doubt I have to introduce you personally to property dualism, but for the reader's sake...)

n my mind, the constructor theory of Deutsch and Marletto is a deeper version of the limits pen-and-paper maths puts on algorithms, automata, and TM's. It would be a way to generate all possible physical transformations allowable in the universe in a different way than the set of writing down all possible algorithms for example.

Okay, so now that we have gotten that out of the way, let's rephrase this as a conversation about the relation between it and bit consciously raising Wheeler's notion of it-from-bit. On the one hand, we have physicists who bump into duality starting from the physical and running into the mental, and on the other hand, we have philosophers, influenced by phenomenalist thinking, trying to move from the mental to the physical. These are then, two sides of the same question, the same exact question that is raised famously by Cartesian duality, but perhaps more sophisticated since instead of attributing both sides to the duality to substance, this wrestles with the intuitions of substance to representation. That is, it-from-bit says substance is grounded in representation, and bit-from-it says representation is grounded in substance. We have a useful set of terms for these approaches, thankfully: materialism and idealism.

So, really, Marletto and Deustsch are trying to make a case for idealism to fellow physicists (Seth Lloyd of MIT, and others have similar approaches), in opposition to the skepticism of physicists that is patently rooted in intuitions about language (objects simply and objectively correspond to words a la logical atomism) whereas from the phenomenalist thinking prominent among philosophers, you have proponents of embodied cognition (SEP) working in the opposite direction fighting the opposing skepticism (words are grounded complexly behind the label 'intuition' from objects). The common ground that legitimizes both pursuits is 'computation'. Physicists know lots about the 'it' and philosophers know a lot about the 'bit' in the framework of traditional dualist thinking. Computer scientists have to live with the duality in a much more obvious way, because our vocabulary requires us to acknowledge the existence of software and hardware in every conversation. Of course, computer folk tend to gravitate towards the tribe of their bias, mathematically inclined to the abstractions, and engineers towards building actual systems.

In my mind, the constructor theory of Deutsch and Marletto is a deeper version of the limits pen-and-paper maths puts on algorithms, automata, and TM's. It would be a way to generate all possible physical transformations allowable in the universe in a different way than the set of writing down all possible algorithms for example.

Should we consider the physical universe subject to transcendent laws of thought, or are the laws of thought ultimately a manifestation of the physical universe? I won't continue, because that would bleed into my personal preference on this matter and the hard problem of consciousness, but suffice it to say, it's a helluva question to tackle. :D