Proving The Church-Turing-Deutsch Principle

[n01]

How does one prove the Church-Turing-Deutsch Principle?

The principle states that a universal computing device can simulate every physical process.

Not sure where to post this, as it seems like a pertinent question in proving the simulated universe thesis right or wrong along with possible justification in support of Everettian QM. I also don't know how to reconcile the Church-Turing-Deutsch Principle with Gödel's incompleteness theorems.

Any input greatly appreciated alleviating my confusion.

 

[secur]

One doesn't prove it. That's usually true of a "principle", it's assumed and used to derive actual physics. If those implications are always correct, after a while the principle becomes accepted, but never proved. The so-called "Church-Turing-Deutsch Principle" could possibly be "proved" someday, not now.

However the Church-Turing thesis has been proved, for various classes of algorithms. What Deutsch did was suppose that physics would fit into those classes of algorithms. To the extent that turns out to be true, his "principle" will turn out to be correct.

Deutsch is mainly interested in Quantum Computing and the principle is meant, at least in some version, to apply to that. Since they don't work yet (and may never) that puts the principle even farther from satisfactory validation.

Gödel's incompleteness theorem applies in logic, to a class of paradoxes similar to the famous Cretan or Epimenides' ("I am lying") paradox. No example of such has come up in physics.

BTW "the simulated universe thesis" is not allowed here on PF. Yes, I know it's incredibly ... complain to the management. I don't make the rules just follow them.

 

[Demystifier]

If physical laws are based on real numbers (or some other continuous number system), isn't it obvious that a universal computing device, based on integer (or countable) number system, cannot simulate nature exactly?

 

[Heinera]

If physical laws are based on real numbers (or some other continuous number system), isn't it obvious that a universal computing device, based on integer (or countable) number system, cannot simulate nature exactly?

Depends on what you mean by "exactly". I see no reason why it couldn't be simulated to arbitrary precision.

 

[n01]

One doesn't prove it.

The so-called "Church-Turing-Deutsch Principle" could possibly be "proved" someday, not now.

You can see the issue with the contradiction there.

Gödel's incompleteness theorem applies in logic, to a class of paradoxes similar to the famous Cretan or Epimenides' ("I am lying") paradox. No example of such has come up in physics.

This is an issue because given any sufficiently sophisticated universal computing device there will be "truths" or what can be called manifest physical laws (through mathematics, e.g in Hilbert Space) that can't be proven to be true. This is essentially putting a thorn via Godel's Incompleteness Theorems into the validity of the Church-Turing-Deutsch Principle. I don't know if you see the link there yet or if I haven't made the causal link sufficiently clear. If you want to take this line of reasoning as far as possible, then this conundrum extends all the way to ANY physical law, in that we can never be certain of it being true in all circumstances. Even in a deterministic universe via Everttian QM, we could have a computer that will never be able to tell us that every Entscheidungsproblem will be able to be resolved in a deterministic manner.

 

[atyy]

Perhaps the discussion is most fruitful when confined to classical physics. And instead of the incompleteness theorem, perhaps one may simplify to thinking about the halting problem.

Take a look at http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/

"We’ve stated the CTD Principle in a form which is independent of any particular physical theory. This means that given any physical theory we can ask whether or not the CTD Principle is true in that particular theory? That is, within the scope of that theory is it possible to construct a universal computing device that can simulate an arbitrary physical system, also within that theory?

For Newtonian physics, the answer seems to be “yes”. In 1982 Fredkin and Toffoli put forward a “billiard ball” model of computation, in which computations can be performed using colliding billiard balls – that is, using just the principles of Newtonian physics. Fredkin and Toffoli showed that such a model could simulate conventional computers like those Turing had proposed.

In turn, it is widely believed that Turing machines are sufficient to simulate all of Newtonian physics. Some detailed investigations of this question have been done by Pour-El and Richards; with some caveats, my understanding is that their work shows that Turing machines can simulate all of Newtonian physics. (I should say that my understanding of their work is rather superficial, and I have not worked through all the relevant results in detail.)"

 

[secur]

If physical laws are based on real numbers (or some other continuous number system), isn't it obvious that a universal computing device, based on integer (or countable) number system, cannot simulate nature exactly?

Depends on what you mean by "exactly". I see no reason why it couldn't be simulated to arbitrary precision.

I agree with @Heinera. But it's worth mentioning that's not how David Deutsch would respond. He proposes that a quantum computer is capable of providing "infinite" resolution - if, indeed, that's necessary in physics - because it performs computations in all the many worlds at once. Take it for what it's worth.

You can see the issue with the contradiction there.

The second "proved" meant "accepted" as defined in the previous sentence, so it's in quotes. Yes, it's prima facie contradictory; that's exactly why I thought the intended meaning would be discernible.

This is an issue because given any sufficiently sophisticated universal computing device there will be "truths" or what can be called manifest physical laws (through mathematics, e.g in Hilbert Space) that can't be proven to be true. This is essentially putting a thorn via Godel's Incompleteness Theorems into the validity of the Church-Turing-Deutsch Principle. I don't know if you see the link there yet or if I haven't made the causal link sufficiently clear. If you want to take this line of reasoning as far as possible, then this conundrum extends all the way to ANY physical law, in that we can never be certain of it being true in all circumstances. Even in a deterministic universe via Everettian QM, we could have a computer that will never be able to tell us that every Entscheidungsproblem will be able to be resolved in a deterministic manner.

Gödel's says that in any sufficiently complex logic system (which includes arithmetic), it will be possible to write an undecidable sentence. But it doesn't say that any application of it, no matter how sophisticated, must produce such a sentence. It's certainly possible that a complete description of physical laws would avoid such.

No physical law or theory, at all, is decidable, or provable - as Popper and common sense show. Only accomplished (i.e. past) experimental results are thoroughly "true" in physics. This "conundrum extends all the way to any physical law" regardless of Godel.

There's no real point to "putting a thorn into the validity" of CTD since it has no particular validity at the moment. It's just a guess. It seems you're looking for a logical contradiction in a principle which can not, yet, even be considered logical.

There's no reason to expect a simulation of physics to engender, much less solve, every decision problem.

My overall point: Physics and formal logic are apples and oranges which you're trying to mix. Undoubtedly, I could be wrong.

 

[n01]

So, what I am getting at is what you can ask.

My main point is that how can we know for certain that the MWI is actual/real/valid/.../true if the only practical means of verifying it is via trying to simulate the laws of the universe via the Church-Turing-Deutsch Principle, which itself can't be known to be true?

What's even more damning is that Godel showed that even if the Church-Turing-Deutsch Principle is by some means true, then even if one were to create such a sophisticated logical Turing Machine, then even then we would not be able to know whether halting problems (physical phenomena taking place within such a machine) are deterministic (via computational means) or not.

It's kinda like standing on a rug and pulling at it at the same time.

 

[atyy]

So, what I am getting at is what you can ask.

My main point is that how can we know for certain that the MWI is actual/real/valid/.../true if the only practical means of verifying it is via trying to simulate the laws of the universe via the Church-Turing-Deutsch Principle, which itself can't be known to be true?

It's kinda like standing on a rug and pulling at it at the same time.

MWI is not strictly related to the Church-Turing-Deutsch Principle. As you can see in Nielsen's discussion, CDT can be discussed in the context of classical mechanics.

Also, as far as we know, there is nothing that a quantum computer can do that a classical computer cannot do - the only difference is that a quantum computer can do some things faster.

 

[n01]

I'm going to try and simplify my question to a more simple one pertaining as to whether Godel's Incompleteness Theorems negates the possibility of constructing a universal Turing machine that would be capable of computing all known physical laws. Or am I running in circles in trying to state that all physical laws can be proven to be true (computable or replicable?). I mean, the act of a computer able enough to simulate them, would be sufficient evidence despite not being able to verify them from within such a system.

If anyone want's to take a stab at it here, then by all means.

 

[secur]

Remember we can never "know for certain" that MWI, or any other physical theory, is True. Tomorrow water might boil at 101 degrees C, invalidating thermodynamics and chemistry (I don't expect it though :-) If you haven't read Popper perhaps you should; but the idea is just common sense. Physical theories are in danger of being falsified every time we do another experiment. They can never be accepted as "True" with a capital T. So we're never going to find an absolute logical proof of MWI - and that's so with or without Godel. However it may be made so plausible that everyone accepts it.

BTW, full disclosure: I don't "believe" MWI, but admit it's possible. Indeed, I don't think it can be disproven any more than it can be proven.

Now, Deutsch has made these two statements:

1 - the CTD conjecture: a computer (quantum, in his view) is capable of simulating exactly all physical processes.

2 - If / when Quantum Computers actually work, that will "prove" MWI. His reasoning: in a sophisticated QC algorithm, essentially infinite computing power is involved. "Where" is all that computing taking place? Answer: in those infinitely many worlds.

These two statements are related and compatible but each can stand alone. When you say CTD is a "practical means of verifying" MWI I suspect you're conflating them.

Statement 2 is reasonable. If QC's work as well as some hope, their capabilities will be so amazing that it will make MWI seem sensible. But there will always be alternative explanations.

Statement 1 also is not unreasonable. It's clearly somewhat true: we can definitely simulate most (if not all) physical processes. And it can be done with regular digital computers, although quantum computers will do a much better job in many cases (if they ever work). But - to reiterate - it can never be proven "absolutely".

Bottom line, I think your difficulty originates in looking for absolute proof where it is not, and never will be, available.

 

[n01]

Well, I've always been more of a logical positivist despite being familiar with Popper and his doctrine of fallibility.

I contest the notion that logic and physics are two mutually independent things. I mean, the Church-Turing-Deutsch Principle hinges on these logical machines that can replicate physical laws. If a physical law can't be replicated then it will be by Godel's hand, hehe.

 

[atyy]

I'm going to try and simplify my question to a more simple one pertaining as to whether Godel's Incompleteness Theorems negates the possibility of constructing a universal Turing machine that would be capable of computing all known physical laws.

Well, how about a simpler question - instead of the incompleteness theorem, why not consider the halting theorem (which is related to the incompleteness theorem). Does the halting theorem prevent the construction of a Turing machine that simulates a world governed by classical mechanics?

 

[secur]

Halting theorem is definitely more relevant since it's basically Godel's theorem for computer programs - and that's what we're talking about. It says that for reasonably general and complex programs - which physics simulator would be - you can't always guarantee it will halt, having reached a solution.

The only way a non-halting program can ever happen is some form of infinite loop. That happens with any (sufficiently complex) program every now and then. Windows freezes and you have to reboot: that means an infinite loop popping up somewhere.

We've developed ways to handle the problem. In modern multi-tasking a process gets a time slice, 5 or 10 ms; then it's interrupted and control given to next in the scheduling queue (of course priorities are involved). That simple approach could cure the halting problem. First, notice that the scheduler is simple enough, with a very targeted mission, to be made bullet-proof. IOW it ought to always work. Now, each process could be allotted a "maximum time". If it exceeds that, it's removed. In this way we ought to be able to guarantee no infinite loops, no matter how vulnerable an individual process might be.

In terms of a physics simulator, infinite - or at least very long - loops are very much expected. For instance suppose you want to simulate, at a basic level, the gas in a container, to compute pressure on the walls (or whatever). The obvious way is to loop over every molecule. Update the position by a tiny time step (picosecond or so) and see it if hits the wall. Add the resulting impact's contribution to your accumulating sum. Get to the end of the loop, that sum is your calculated momentum (pressure). How long will the loop take? We could easily construct an example where, on the super-est supercomputer available today, it would take a billion years. That's too long, even if it's not infinite. So our physics simulator is going to require a clever way to approximate the final result - which is called "mathematics". E.g. Maxwell-Boltzmann equation etc.

Essentially this is the reason why math is "the language of physics" - because they didn't have computers back then. If they had, math would be nowhere near as important. You can view the whole point of math (especially integration) in physics as, precisely, the solution to loops that are too long to simulate.

So my point is that any comprehensive physics simulator will have to constantly be able to detect, abort, and provide an approximate answer for, the inevitable too-long loops that will arise. This mechanism will automatically put a halt to the halting problem, as well.

Note: you've never heard this idea before, so the natural reaction is to simply ignore it. This note is included to make you think twice.

 

[Demystifier]

that's not how David Deutsch would respond. He proposes that a quantum computer is capable of providing "infinite" resolution - if, indeed, that's necessary in physics - because it performs computations in all the many worlds at once. Take it for what it's worth.

Is there some reference where Deutch claims that? I would say that a quantum computer based on qubits (or any other countable basis) can do exactly the same as classical computers can. Yes, the parallelism due to "many worlds" can speed up some calculations, but as long as the number of "worlds" is also countable, I don't see how could quantum computers transcend the countability barrier.

 

[secur]

Is there some reference where Deutch claims that?

I believe it's a fair statement of his view. I put "infinite" in quotes to soften it a bit. Here's one quote I found on Scott Aaronson's blog:

Deutsch from 1997 book “The Fabric of Reality”:

Logically, the possibility of complex quantum computations adds nothing to a case [for the Many Worlds Interpretation] that is already unanswerable. But it does add psychological impact. With Shor’s algorithm, the argument has been writ very large. To those who still cling to a single-universe world-view, I issue this challenge: explain how Shor’s algorithm works. I do not merely mean predict that it will work, which is merely a matter of solving a few uncontroversial equations. I mean provide an explanation. When Shor’s algorithm has factorized a number, using 10500 or so times the computational resources that can be seen to be present, where was the number factorized? There are only about 1080 atoms in the entire visible universe, an utterly minuscule number compared with 10500. So if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it, then? How, and where, was the computation performed?

He was more explicit in "The Beginning of Infinity" where he argues specifically that infinity exists as such. I'm quite sure he says we'll be able to simulate physical processes exactly, but can't find a quote.

That's not enough to justify my paraphrase of his views, I admit. I just spent 15 minutes wading through a lot of pop-sci about MWI, QC, and how bold a visionary genius DD is, looking for a good quote. Can't take any more; would rather be branded a mis-paraphraser, or water-boarded.

 

[Mentz114]

Anyone who has done numerical integrations of simplectic processes has found the rather obvious rule that energy conservation only becomes exact in the limit as the time step $\delta t \rightarrow 0$. This is not possible in a finite time. If there is a 'minimum time' step in the universe, then energy conservation is never exact.

The universe is more like an analogue computer with faster than light internal communication.

 

[n01]

I have a small question.

If all the laws of physics can be computed, then doesn't that presuppose that logic is at least synonymous or at least as important as physics is. Or rather that physics relies on the laws of logic?

I always had a problem with understanding the importance of physics, mathematics, and logic and which of them follows from the rest. I am a platonist for the matter and subscribe to Tegmark's views on the multiverse.

 

[secur]

Anyone who has done numerical integrations of simplectic processes has found the rather obvious rule that energy conservation only becomes exact in the limit as the time step $\delta t \rightarrow 0$. This is not possible in a finite time. If there is a 'minimum time' step in the universe, then energy conservation is never exact.

As far as anyone knows there is no minimum time step, as such, in the universe - but there is a minimum action step, Planck's constant. So if the energy of an object is constant, in a given scenario, its "minimum time step" would be t = h / E. That's naïve, there are a number of details to consider, but perhaps it can be made a rigorous statement. In a subatomic simulation, one can probably adjust the time step according to this idea so as to get exact answers without letting it go to 0. In fact if it worked, a smaller time step would no doubt give a wrong answer.

If all the laws of physics can be computed, then doesn't that presuppose that logic is at least synonymous or at least as important as physics is. Or rather that physics relies on the laws of logic?

I always had a problem with understanding the importance of physics, mathematics, and logic and which of them follows from the rest.

From a practical, working-physicist point of view, logic comes first. That is, physics assumes logic and math as a necessary substrate.

However from a philosophical point of view it's not that simple. The basic counter-argument goes: evolution provided us with logic/math ability; evolution is driven by the real world, i.e. physics; therefore physics comes first.

The question is a can of worms, on this "deep" level. Fun to think about but no final answer is possible.

 

[Quotidian]

That assumes that evolutionary theory somehow pre-empts or explains logic, philosophy and rational thought. Which means that all of these are then rationalised in terms of evolutionary advantage, like peacock's tails, or claws or tentacles. Which, in turn, is no more than an illustration of the fundamental inadequacy of 'biologism'. It's really not a 'philosophical point of view' at all, it is more the point of view that declares, with Dennett, philosophy is dissolved in 'Darwin's dangerous idea'.

 

[n01]

The question is a can of worms, on this "deep" level. Fun to think about but no final answer is possible.

Many people say that there are no physical laws that are non-computable. This is a statement that requires much-needed justification in my humble opinion. I mean, many physicists as mentioned in the blog post take this for granted and continue computing. Hilbert went as far and proposed this as one of the central questions mathematicians and logicians must answer. Didn't Godel and Turing prove this to be not the case?

 

[MrRobotoToo]

How does one prove the Church-Turing-Deutsch Principle?

The principle states that a universal computing device can simulate every physical process.

Not sure where to post this, as it seems like a pertinent question in proving the simulated universe thesis right or wrong along with possible justification in support of Everettian QM. I also don't know how to reconcile the Church-Turing-Deutsch Principle with Gödel's incompleteness theorems.

Any input greatly appreciated alleviating my confusion.

At one level of interpretation, the principle as you've stated it is obviously true: as far as anyone can tell the laws of physics can be boiled down to a system of partial differential equations; if one discretizes space and time, a system of PDEs becomes a system of difference equations, which in turn can always be solved iteratively by a universal computing device. I posted a video of David Deutsch on my Youtube channel where he states that what's really strange about the universe is that it's possible to build universal computers inside the universe. I think what he means is that out of all the possible systems of PDEs and all possible initial conditions, only a tiny subset will contain solutions that exhibit universal computation, and for whatever reason our universe is in that subset.

 

[atyy]

At one level of interpretation, the principle as you've stated it is obviously true: as far as anyone can tell the laws of physics can be boiled down to a system of partial differential equations; if one discretizes space and time, a system of PDEs becomes a system of difference equations, which in turn can always be solved iteratively by a universal computing device.

At this point in time :) it is not clear that space and time can be discretized, because of the chiral fermion problem.

https://arxiv.org/abs/0912.2560: "Even if eventually a lattice formulation of the Standard Model is achieved ..."

 

[MrRobotoToo]

At this point in time :) it is not clear that space and time can be discretized, because of the chiral fermion problem.

https://arxiv.org/abs/0912.2560: "Even if eventually a lattice formulation of the Standard Model is achieved ..."

I didn't mean to imply that space and time are actually discrete, but only that discretization can be used to approximate the continuous theory. I haven't studied lattice gauge theory at any depth, but what I gather from a casual perusal of online material is that there's various kluges for the chiral fermion problem, as there must be if one considers the successes of something like lattice QCD.

 

[atyy]

I didn't mean to imply that space and time are actually discrete, but only that discretization can be used to approximate the continuous theory. I haven't studied lattice gauge theory at any depth, but what I gather from a casual perusal of online material is that there's various kluges for the chiral fermion problem, as there must be if one considers the successes of something like lattice QCD.

There are not. This is a major open problem in lattice gauge theory.

 

[Zafa Pi]

One doesn't prove it. That's usually true of a "principle", it's assumed and used to derive actual physics.

How about Heisenberg's Uncertainty Principle? There are many others. However laws aren't generally proved.

Deutsch is mainly interested in Quantum Computing and the principle is meant, at least in some version, to apply to that. Since they don't work yet (and may never) that puts the principle even farther from satisfactory validation.

All quantum computers (theory) can be simulated by classical computers, so the C-T-D works for them.

Gödel's incompleteness theorem applies in logic, to a class of paradoxes similar to the famous Cretan or Epimenides' ("I am lying") paradox. No example of such has come up in physics.

Interestingly there is a straight forward proof of Gödel's incompleteness theorem using C-T.

 

[Zafa Pi]

Take a look at http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/

I did. An interesting article and I have a lot of respect for Nielsen, particularly his book with Chuang. But in that article he says, "quantum mechanics isn’t a complete physical theory in its own right, but rather a framework for the construction of physical theories." I don't get it. QM has laws (or postulates), definitions, theorems (predictions) everything a theory wants. What does Nielsen mean?

 

[n01]

All quantum computers (theory) can be simulated by classical computers, so the C-T-D works for them.

Interestingly there is a straight forward proof of Gödel's incompleteness theorem using C-T.

Yes, and the question in my mind is whether it is possible to verify the consistency of such a sophisticated computer?

This would be a sine qua non in my mind to accurately know and predict the outcomes of such said computing device, and thus be able to truthfully make such statements like 'the universe is deterministic in nature' or 'quantum mechanics obeys causality'...

 

[Zafa Pi]

Yes, and the question in my mind is whether it is possible to verify the consistency of such a sophisticated computer?

This would be a sine qua non in my mind to accurately know and predict the outcomes of such said computing device, and thus be able to truthfully make such statements like 'the universe is deterministic in nature' or 'quantum mechanics obeys causality'...

I'm at a loss. If I have a program (computer) that when I input 2+3 it gives 5, but when I input 3+2 it gives 6, then is it inconsistent or merely a lousy addition program?
Can you verify if math is consistent?

Do you think that the concept of determinism can be programed? Is the result of flipping a coin in a wind determined?

 

[Zafa Pi]

If physical laws are based on real numbers (or some other continuous number system), isn't it obvious that a universal computing device, based on integer (or countable) number system, cannot simulate nature exactly?

Are you asserting that nature is continuous rather than discrete? Are not "physical laws" man made?

 

[Demystifier]

Are you asserting that nature is continuous rather than discrete? Are not "physical laws" man made?

Note that I started my assertion with "If". By "physical laws", I meant the laws of Nature itself.

 

[Zafa Pi]

Note that I started my assertion with "If". By "physical laws", I meant the laws of Nature itself.

Help me out here, because I am not trying to nit pick, but to understand what you mean. It would help me if you told me whether Newton's laws are "physical laws" = "the laws of Nature itself". And if not what is an example of a physical law. I believe my questions are germane to this thread.

 

[n01]

I'm at a loss. If I have a program (computer) that when I input 2+3 it gives 5, but when I input 3+2 it gives 6, then is it inconsistent or merely a lousy addition program?
Can you verify if math is consistent?

Do you think that the concept of determinism can be programed? Is the result of flipping a coin in a wind determined?

Well, if a formal system is Turing complete and decidable, then it is consistent. If it is consistent then it is deterministic.

It's not that complicated.

And for the matter I envisioned a simple solution to the question posed in the OP.

Namely, if human consciousness can be simulated (due to it obeying the same physical laws as any other object in the universe), then so can the Church-Turing-Deutsch Principle be verified to be true through an indirect method of proof. Whether this is true or not is highly contested by physicists to this day (Penrose, et al).

 

[Demystifier]

Help me out here, because I am not trying to nit pick, but to understand what you mean. It would help me if you told me whether Newton's laws are "physical laws" = "the laws of Nature itself". And if not what is an example of a physical law. I believe my questions are germane to this thread.

I mean we don't know what are the "ultimate final fundamental" laws of nature, but the most fundamental man-made currently known laws of nature are based on real and complex numbers (not the integer ones).

 

[Zafa Pi]

I mean we don't know what are the "ultimate final fundamental" laws of nature, but the most fundamental man-made currently known laws of nature are based on real and complex numbers (not the integer ones).

Newton's laws (of nature) are continuous and were valid for hundreds of years, but turned out to be not in accord with experiment. The laws of E&M, GR, and QM are continuous and these theories are really great, but have problems with being consistent with one another. But what about the "ultimate final fundamental" laws of nature, what will they be? Many working in the field of Q-gravity think they will be discrete. A perusal of the internet gave me the impression that a majority of physicists tend to believe that nature itself is discrete rather than continuous, digital rather than analog (e.g. see http://fqxi.org/community/essay/winners/2011.1).

When you said, "If physical laws are based on real numbers (or some other continuous number system), isn't it obvious that a universal computing device, based on integer (or countable) number system, cannot simulate nature exactly?" in post #3, it seems as though you think otherwise. "Isn't it obvious"? No, it isn't obvious, in spite of your "If".

Continuous laws? I like your quote, "It's a thinking tool, you fool. :)"