Tell me more ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
1  
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 […]" – Will Vousden Jun 27 '11 at 7:33
@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)? – Marek Jun 27 '11 at 8:55
1  
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. – Peter Shor Jun 28 '11 at 13:11

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
Thanks, I suppose it follows directly since turing machines can simulate CM? And same with QM it seems. – Holowitz Jun 27 '11 at 20:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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