2
$\begingroup$

Can the Church–Turing Thesis be proved assuming classical mechanics, how is the proof or disproof?

Edited: I was looking for a proof of "everything computable by a device obeying CM is computable by a Turing machine", but it seems obvious now.

My followup question is why does it hold for QM?

$\endgroup$
  • 1
    $\begingroup$ What does Church–Turing have to do with classical mechanics? The article you linked to provides the answer: "Despite the fact that it cannot be formally proven […]" $\endgroup$ – Will Vousden Jun 27 '11 at 7:33
  • $\begingroup$ @Will: there is also physical CTT and quantum CTT (again in the linked-in article). Can't that be somehow relevant (I have no clue though)? $\endgroup$ – Marek Jun 27 '11 at 8:55
  • 1
    $\begingroup$ What do you mean by classical mechanics? Unlike the Standard Model, say, it's not a single actual well-defined theory of physics, and if you're not careful about your assumptions, then you get uncomputable behavior. For example, Newtonian gravity with point masses is problematic, as is the wave equation with computable initial data. $\endgroup$ – Peter Shor Jun 28 '11 at 13:11
2
$\begingroup$

This question was asked and answered on mathoverflow. You should read it there. We could have migrated it but that site is independent of SE network.

$\endgroup$
  • $\begingroup$ Thanks, I suppose it follows directly since turing machines can simulate CM? And same with QM it seems. $\endgroup$ – TROLLHUNTER Jun 27 '11 at 20:54

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.