tag:blogger.com,1999:blog-3722233.post85426362..comments2020-01-20T07:37:42.239-05:00Comments on Computational Complexity: Foundations of Complexity Lesson 1: What is a computer?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-83072563690600491072012-01-04T14:40:53.215-05:002012-01-04T14:40:53.215-05:00That is not the church-turing thesis!?That is not the church-turing thesis!?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70983800142930369092009-05-01T21:40:00.000-04:002009-05-01T21:40:00.000-04:00Turing machines don't tell you what a computer is....Turing machines don't tell you what a computer is. They may be special because of their historical role, and their simplicity, but they're just a model of a computer, and even there they're not intrinsically any more special than any other computational system. No particular computational model/system tells you what a computer is. We don't really understand exactly what a 'computer' is. See, for example, http://www.calculemus.org/lect/L-I-MNS/12/ekon-i-modele/smith-foundtns.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55340949183755550392009-03-30T15:55:00.000-04:002009-03-30T15:55:00.000-04:00I find the first order logic notions of $\Sigma_1$...I find the first order logic notions of $\Sigma_1$ subsets and $\Delta_1$ subsets of $\mathbb N}$ to be much more natural than Turing enumerable or Turing decidable which are after all defined in terms of a particular kind of machine (one of many possible). In my view, the Church-Turing hypothesis looks more plausible if stated in terms of recursive functions (or \Sigma_1/\Delta_1 sets) than through the language of "machines". Talking about different machines gives the hypothesis a mystifying aura that it does not deserve.Anonymousnoreply@blogger.com