Can every process in nature be simulated by a Turing Machine or a quantum computer?

Question

Given any initial condition or value A, A leads to B after a procedure of physics or nature P. Now is there any turing machine or quantum computer that can simulates P,converting A into B? In other word, is any cause-effect relation in nature computable?

glS · Answer

As far as we know, yes. This is essentially the Church-Turing thesis. Note that this is not a mathematical result, but more of a definition of what it means to be computable. You can find plenty of discussions about this around. A few notable examples are:

What would it mean to disprove Church-Turing thesis? (on cstheory)
Extended Church-Turing Thesis [and QC] (on cstheory)
Why do we believe the Church-Turing Thesis? (on math)
Can a Turing machine simulate a quantum computer? (here)

Can every process in nature be simulated by a Turing Machine or a quantum computer?

One Answer

Add your own answers!

Ask a Question