0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Hi @XL_At_Here_There, welcome to QCSE. It seems like you are asking if a quantum Turing machine simulate a Laplace Demon. But right now the wording of the question is a bit confusing. Can you consider revising your question in the formalism of quantum computing, if you can? Are $A$ and $B$ states, and $P$ an operation acting on $A$ to convert it to $B$? $\endgroup$ – Mark S Apr 24 '20 at 17:19
  • $\begingroup$ states? maybe, but it does not matter. $\endgroup$ – XL _At_Here_There Apr 26 '20 at 11:55
  • $\begingroup$ I would counsel you to make an effort to clarify your question, or accept @gIS's already informed answer. $\endgroup$ – Mark S Apr 26 '20 at 18:02
3
$\begingroup$

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:

  1. What would it mean to disprove Church-Turing thesis? (on cstheory)
  2. Extended Church-Turing Thesis [and QC] (on cstheory)
  3. Why do we believe the Church-Turing Thesis? (on math)
  4. Can a Turing machine simulate a quantum computer? (here)
$\endgroup$
6
  • $\begingroup$ so, we have to believe or prove that any cause-effect relation in nature is computable, or any process P in nature is computable. I think this may be wrong. And it is not about CT-Thesis. CT-Thesis. say that the computability is Turing computability. $\endgroup$ – XL _At_Here_There Apr 26 '20 at 8:59
  • 1
    $\begingroup$ you cannot prove that "any cause-effect relation in nature is computable", because that is not a mathematical statement. What is true is that every current physical theory is computable. Also, you would be hard-pressed to even think of what an "uncomputable physical theory" would be. In my mind, accepting such a thing would be the same as saying that no physical theory can describe nature. But again, this is more about phylosophy than physics. Also, it has nothing to do with quantum mechanics. Quantum mechanics only enters the discussion when you care about computational hardness. $\endgroup$ – glS Apr 26 '20 at 9:06
  • 1
    $\begingroup$ btw, what (I think) you are asking about is often referred to as the "physical Church-Turing thesis". $\endgroup$ – glS Apr 26 '20 at 9:08
  • $\begingroup$ Can we prove that "any cause-effect relation in nature is computable" by physical theory? $\endgroup$ – XL _At_Here_There Apr 26 '20 at 11:41
  • 1
    $\begingroup$ @XL_At_Here_There I'd say that physics is concerned, by definition, with physical theories, and thus your question is not about physics $\endgroup$ – glS Apr 26 '20 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.