3

Turing machines were initially conceptualised as an abstraction of the human way of solving problems : loading things into memory, carrying out instructions, updating memory, etc. But as it turned out, this machine is also the limit of the kinds of computation that can be done by any entity, human or machine, as far as we know. We haven't been able to build something more powerful than a Turing machine.

Suppose, for the sake of this discussion, that the universe is exactly modeled by a 4D manifold structure. We will assume the universe is classical. The entities on the 4D spacetime are fields and particles. When I say "exactly modeled", I mean, for the sake of discussion, assume that this were the final theory of physics. There is no experiment that will ever falsify this one.

Now, if this is true, then any finite region of the universe is packing an ungodly amount of information at any moment of time. Specifically, these are the values of the fields on the points in that region. Furthermore, time evolution of this region corresponds to carrying out a computation on this region's data.

Then if we were to think of this universe itself as some machine, then it carries out far more powerful computations than a Turing machine. This is because the values of the fields in a region could correspond to non computable, or even non describable functions. (Note that I'm not saying that a human experimenter can't approximate the process using computable/describable functions. We can do that because we are only interested in finite measurement accuracy. I'm instead talking about the universe viewed as a computer).

My main question- If the universe viewed as a computer is more powerful than a Turing machine, the next question is, what kinds of emergent computers could be hosted by this universe? By emergent computer, I mean something like your smartphone. This computer's memory and computations are ultimately an abstraction of the memory and computations of the universe at the fundamental level. For instance, the data stored in this computer's memory chip is ultimately stored by the universe in the form of field/particle states. And any computation that this computer does is emergent out of the time evolution of the underlying field/particles.

So, if the underlying substrate machine does computations that a Turing machine machine can't do, one would expect that there can be emergent computers that are more powerful than a Turing machine. For instance, consider the abstract description of the memory of such a computer : it's possible that this is a countably infinite number of bits. This is possible because the substrate of the universe (fields and particles) can easily store that information in a finite region of space.

So, can we say for sure that these machines can't exist in a universe that's exactly modeled by continuous structures at the fundamental level?

P.S. I am restricting the definition of emergent computer to only mean computers that are confined to a finite region of space, and their computations are confined to a finite interval of time. This is because if I allow unbounded space and time, then even our everyday computers are more powerful than a Turing machine (as they can solve the halting problem by computing for an infinite time).

P.S. The conclusions that I arrived at say that the reason we haven't (and cannot) invent emergent computers that are this powerful is because our own brain is a specific kind of emergent computer whose memory and computations correspond to "finite set of bits" and "finite set of computation steps". So, while the substrate might support more powerful computers, our brains can't conceive and implement those modes of computation in an external device.

7
  • According to standard physics, the universe is not modeled by a computer executing an algorithm. Your picture is that of, e.g., Stephen Wolfram. Not what one learns in physics at uni. Commented 21 hours ago
  • 1
    What do you mean precisely by "more powerful"? A supercomputer is certainly more powerful than a smartwatch. I'm VTC because the answer is found here: cs.stackexchange.com/questions/55489/… Commented 19 hours ago
  • 1
    If we had an analog final theory of anything, Turing machines would be irrelevant. Commented 15 hours ago
  • 1
    you might get better answers on one of the computer science stacks, it looks to me like this is mostly a maths question, with a physics question about whether such a universe could actually give rise to hypercomputations mixed in Commented 14 hours ago
  • 1
    I’m voting to close this question because Is boo shee-yit Commented 8 hours ago

5 Answers 5

2

First, a clarification: Turing machines are not powerful in any meaningful sense of the word. Instead, Turing machines are a simplified abstraction of the way in which calculation is performed. It doesn't make any sense to say that a Turing machine is the most powerful computer that can be made; the correct phrase is that any (current) computer, no matter how powerful, is at heart a Turing machine.

Second, only symbolic processing devices with finite internal states and strict sequencing rules qualify as Turing machines. Every conventional (current) computer can be modeled that way, but quantum computers and analog computers — and arguably other types of computers not yet invented — cannot be modeled as Turing machines. I'm not suggesting these computers are more 'powerful' than Turing-machine computers; they're merely different.

It's also worth pointing out that Turing machines were intended to reflect the human method of 'doing calculations', not of 'solving problems', and we shouldn't fall into the ideological trap of believing that all problems are matters of mere calculation. But's maybe that's just me being philosophically peevish…

But let me get to the point. The way things are framed here, this question seems to presume that the universe as a while is already something like a vast quantum computer. And this forces us to consider a fundamental difference. In Turing devices the machine is an external device that works on symbols it is completely divorced from. It's all a bit Cartesian: a Turing device doesn't know anything about the symbols it processes, and the symbols themselves never enter into the device, the device merely carries the tape that contains the symbols, moving it this way and that, while 'information' is worked out entirely on a symbolic level. Quantum devices, by contrast, are not separate from or external to the information they work on; quantum devices are the information they work on. When we look at one of the current efforts at quantum computing we will see a lot of machinery, obviously, but this machinery has nothing to do with the quantum computation itself. These machines are there to maintain the quantum elements in a particular state: cooling them to low temperatures, excluding vibrational noise and radiation, providing interfaces, probably a few flashing lights to make it look cool… The actual 'computation' is contained entirely within the quantum processor itself, as transformations of its quantum state.

Obviously, a universe that is itself a quantum processor could allow the creation of other quantum computers within itself (with the caveat that these localized quantum computers need to be isolated from confounding interactions with the universal processor). Whether this is 'powerful' is a separate issue. Much like AI, quantum devices are a neat idea that might have important specialized uses, but that may not be all that productive for general consumption. Most of the things we use smart phones for are matters of symbolic processing. Talking to people, sending texts, playing games, taking pictures, translating, looking up information: these are all symbolic transformations of one sort or another, and a Turing-type machine is (in some ways) ideally suited for that kind of symbolic transformation work. I can imagine quantum computers being useful for certain scientific tasks: things where fundamental principles can be 'coded in', and complex results can be achieved in time-frames that Turing devices can't match. But I can't imagine what use a hand-held quantum device could be put to. And almost certainly any hand-held quantum device would need to be paired with a sophisticated Turing device that would translate the user's symbolic commands into rules for the quantum device to execute, and then retranslate the output into humanly accessible symbols. If we have to have that Truing device anyway, what added value does the quantum element bring? Time will tell, I suppose, but right now a common-use quantum device seems a bit like strapping a jet engine on a Kia Sorento: cool as hell if one could do it, but not useful for any of the normal purposes of an SUV.

11
  • 1
    I would enjoy to read the essence of your answer expressed straight forward in a few sentences :-) Commented 21 hours ago
  • 2
    @JoWehler: And I would throughly enjoy being that clear and effective a writer. 😁 Honestly though, as is this is probably a ten to fifteen thousand word essay cramped down to a couple of pages (the original question had some vaguenesses that need to be addressed), so I'm not sure about a TLDR. Maybe the short answer is…: If the universe is seen as a quantum processor, then smaller quantum processors are possible, and arguably more powerful than Turing machines. But Turing-type machines are uniquely suited to conventional human symbolic uses, and unlikely to be supplanted soon. Commented 20 hours ago
  • 1
    @JD. Let's not get into a semantic tussle over the use of the term 'powerful'. Technically speaking, a Turing machine made out of an abacus can solve all the same problems as a super computer; it's just a question of processing time. 'Power', thus, is a disingenuous term as used here; Turning machines are an abstraction that defines the class of calculations such machines can solve, nothing more. Commented 19 hours ago
  • 3
    @TedWrigley I am sceptical to see the universe as a quantum computer as if the universe makes any computations. Likewise nobody thinks that the universe solves ordinary differential equations from Newton’s mechanics before the planets start moving around the sun. Both kinds of comparison are human methods to state what we consider the laws of nature. But nobody knows what nature itself thinks about the laws of nature :-) Nevertheless thanks for explaining your thoughts. Commented 18 hours ago
  • 2
    @JD: I just wouldn't want to be the one waiting for the output… Commented 16 hours ago
2

if we were to think of this universe itself as some machine, then it carries out far more powerful computations than a Turing machine. This is because the values of the fields in a region could correspond to non computable, or even non describable functions

If, just for the sake of idle speculation, we assume that those "values" are non-describable, then presumably this means: non-describable by us, by any means, ever. So, we cannot describe them. Thus, we cannot know about them. Thus, assuming that whatever happens in the universe is a kind of computation, but that no conceivable computation could carry it out, then we cannot simulate it, model it, conceive of it, understand it. In other words: we could never know this.

Quantum computers are also turing machines; they are not more powerful in the sense that they would enable us to compute thing that are essentially uncomputable by any turing machine (e.g. the halting problem); they just allow faster, more efficient computations. It's possible to imagine devices that are more powerful (Turing himself imagined an "oracle" that could answer certain uncomputable questions), but those devices can not be physically realized (if we believe the Church-Turing thesis).

The upshot of this is that, if the Church-Turing thesis is true, then the universe can also not be (operating as) a kind of device that is essentially more powerful than a turing machine (unless the universe itself is actually infinite or contains actual infinities).

Independent of that: an emergent computation can never be more powerful than the underlying system: it cannot compute something that the underlying system would not be able to compute. Even though some problems or tasks may only become "visible" at a global, emergent macro-level (for instance: determining parity by a 1-dimensional black-white cellular automaton; 'parity' is itself a global property). Emergence means that the same process can be seen in different ways, either on a micro-level or on a macro-level; the two views are still views of the very same underlying process however. (New information can never as it were spontaneously be created.)

7
  • 1
    +1 "The upshot of this is that, if the Church-Turing thesis is true, then the universe can also not be (operating as) a kind of device that is essentially more powerful than a turing machine". Commented 19 hours ago
  • Quantum computers are not Turing machines, as such are typically defined. It may be the case that there are limitation on the use humans can put them to which impose Turing-like conditions. But that's a limitation on human symbolic capacities, not on such computers themselves. It's not clear to me that these limitations (should they exist) are insurmountable by developing technology. Commented 19 hours ago
  • It seems that there is indeed some disagreement among some CS scientists whether or not QTM are more powerful than classical TM. However, the most widely accepted view afaik is: "It turns out that such a machine is not more powerful, in the sense of computability, than the machine originally constructed by Turing. Quantum Turing-machines do not violate the Church-Turing thesis." (see: Harry Buhrman, Turing in Quantumland - ir.cwi.nl/pub/22927/22927B.pdf) Commented 17 hours ago
  • If you have an authoritative source that refutes this, I'm interested in knowing it. Commented 17 hours ago
  • 2
    I don't think there's any serious doubt. Quantum computers are exactly as powerful as Turing machines, that's just a known fact. They differ only in the speed at which computations can be performed, not in which computations can be performed and which can't. Commented 3 hours ago
2

I think this is a good question, but I also think it's very difficult to answer, and doing so would require some sophisticated mathematics.

Part of that would be defining exactly what's meant by the various components of the question. For example:

  • What kind of thing are the laws of physics in this universe? Are they just arbitrary partial differential equations on a 4 dimensional manifold, or do they obey the constraints of Hamiltonian dynamics (or some other constraints)? Does the manifold change dynamically as in general relativity (and if so, is that considered an essential part of the question or can it be ignored?)? What are the boundary conditions - are they arbitrary or do you impose some constraints on them? Either way, do you demand that these partial differential equations have a unique solution across all space-time for any permissible boundary conditions, or do you allow the possibility of multiple solutions, partial solutions, singularities etc.?
  • What is a computer in this setting exactly? How do you give it an input and get its output? Are the inputs and outputs continuous or discrete, and if the latter, how do you encode discrete signals in such a continuous universe?
  • Are computers meant to be "macroscopic" systems in this world, as they are in ours? If so, how can a theory of statistical mechanics be developed for this universe, such that this claim can be made precise?

These points are not meant as a criticism of the question - I'm not suggesting you should try to clarify your question by answering them. (Although if you do have precise enough answers to them, you could try asking this to mathematicians.) Rather, I'm trying to illustrate that questions like this can be very subtle, and making the question precise enough to be answered can be a research programme in itself.

On the other hand, a Google search for "computability in continuous systems" resulted in several papers about continuous models of computation. These are unlikely to exactly be answers to your question, but they are quite likely to be useful if you want to get closer to it. People (including the great Claude Shannon) have already done some of the work of making this kind of problem more precise, and learning about that will probably be very helpful to you.

1

No, because you haven't understood the difference between continuous and discrete processing

Turing Machines are a model of discrete sequential processing. That is, operations are carried out one step at a time, with some delay between operations. It turns out that all discrete sequential processing can be translated into Turing Machine operations.

Turing Machines fundamentally do not represent continuous operations though. We get a pretty good approximation by reducing the sample rate, but it's still not really the same.

Back in the day, we did do analogue computing, which is truly continuous. Look up how gunsights and predictors worked in WW2, for example. They have mostly been replaced with digital technology as the ability to model with faster sample rates has become possible. This is not because digital allows us to do anything different, but simply because analogue computing is hard to design, hard to build, and hard to change if you need a slightly different algorithm.

0

You seem to be mixing up lots of things, mainly configuration space and "computing power". In our computers, small files can be stored on large hard disks but not the other way around, and similarly, finitely many numbers can be represented be countably infinitely many which in turn can be represented by uncountably infinitely many but not the other way around. This says nothing about speed/efficiency/whatnot of compute.

Information as practically used today is always presumed finite. Defining information in an infinite setting, turns out, is quite difficult, see e.g. Shannon Information in infinite cases.

1
  • Defining information in infinite settings is indeed somewhat difficult, but nevertheless it's a solved problem; the link you posted says how it's solved, although perhaps not in a very clear way. Commented 3 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.