2

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?

6
  • @hide_in_plain_sight: References? Can you relate to things Turing or VonNeumann said, or comments since? I'm looking for more than conjecture. Chiara is saying there is a key difference, & she sounds convincing. But, I don't understand what it is
    – CriglCragl
    May 21, 2021 at 1:10
  • I am deleting the comment. if you want to dismiss experience as conjecture, I am not willing to play along. The construction for VonNeumann's machine is published in. "The Theory of Self-Replicating Automata". I don't have it, but I have implemented it. It is a Universal Turing Machine, and as a Cellular Automaton, it can be no more powerful than that. May 21, 2021 at 3:00
  • 1
    Here (researchgate.net/publication/…). "von Neumann's universal constructors holds a close similarity to universal computers that appear in Turing's original proof of the undecidability of the halting problem...This attempt will never be completed because of the indefinite cascade of self-computation, which accounts for the undecidability of the halting problem and also agrees well with the fact that life has maintained its reproductive activity for an indefinitely long period of time." May 21, 2021 at 4:21
  • 1
    von Neumann's "Computer and the Brain" is one such resource. Turing's universal machine is a general framework of computation. Neumann added a functionality of self-replication (universal constructor) which, as I understand, is implementable using Turing's formalism. The point is that Turing's machine is a "general" representation of what it means to follow a rule. Even with univ-constructor the idea is same -storing the code of the constructor and life within the current version of machine, and then following a rule to generate next. And life replication is clearly a mechanical process.
    – Ajax
    May 21, 2021 at 10:51
  • @DoubleKnot. You don't have to leave this open because Church's Thesis is unresolveable. From a mathematical point of view, if I can do A with B and B with A, then A and B are equally powerful. Period. May 21, 2021 at 16:29

2 Answers 2

3

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.

2
  • VonNeumann's automata are one thing, and Deutsch and Marletto's range of constructors are another. I think we are spreading attribution inappropriately. Cellular Automata and the automata of automata theory are discrete. The constructors in 'universal constructor theory' need not be so. VonNeumanns 'universal constructor' even if it has come to seem inappropriately named, is a specific thing in a given paper which is provably equivalent to a UTM. May 21, 2021 at 16:55
  • 1
    @hide_in_plain_sight I added a few clarifications to show how Von Nuemann's constructors are different than constructor theory hope that helps. Ty for the notes about Von Nuemann
    – J Kusin
    May 21, 2021 at 17:10
1

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

1
  • 1
    That's me shooting from the hip like the Yank I am. If your limey(?) erudition raises flags on account of intuitions, please register them, as I appreciate your contributions, as always.
    – J D
    Apr 22, 2023 at 3:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .