(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?
$\begingroup$
$\endgroup$
3
-
$\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 freakAug 2, 2017 at 10:51
-
$\begingroup$ Please pick a better title, it's rather unhelpful. $\endgroup$– Raphael ♦Aug 2, 2017 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$– JingfangAug 3, 2017 at 1:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 2, 2017 at 11:00