2
$\begingroup$

(weak) Church-Turing thesis states every physically realizable computation device can be simulated by a Turing machine (not necessarily efficiently). (1) Then Does any model that is not physically realizable and cannot be simulated by Turing machine? (2) Is there any evidence for this thesis?

$\endgroup$
  • $\begingroup$ As a corollary it implies that every physical process can be modeled by a turing machine. I don't think we've discovered one that cannot. $\endgroup$ – ratchet freak Aug 2 '17 at 10:51
  • $\begingroup$ Please pick a better title, it's rather unhelpful. $\endgroup$ – Raphael Aug 2 '17 at 16:09
  • $\begingroup$ >Raphael thank you for editing. I cannot come up with an appropriate title. Is the title "Turing machine and physical reality" better? $\endgroup$ – Jingfang Aug 3 '17 at 1:52
3
$\begingroup$

You are asking two questions. The answer to your first question, for models stronger than Turing computation, is the field of hypercomputation. The answer to your second question, asking for evidence for the Church-Turing thesis, has been answered on cstheory.

$\endgroup$

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.