4 ms·
>Turing machines (we think) capture everything that's computable. ?? eh?! we think? Isn't the definition of computable, "something that can be reached by a T
by GhotiFish 13y ago
>Turing machines (we think) capture everything that's computable.
??
eh?! we think?
Isn't the definition of computable, "something that can be reached by a Turing machine?"
- Grothendieck 13y agoThere's good evidence that Turing machines do capture the right notion of computability. You can enhance a Turing machine in many ways without changing what it can compute. Further, Turing machines, the lambda calculus, recursive functions, cellular automata, and register machines all give the same notion. Even a quantum computer can be simulated by a Turing machine. https://en.wikipedia.org/wiki/Church-turing_thesis https://en.wikipedia.org/wiki/Church-turing_thesis
- argv_empty 13y agoThat's the definition when "computable" is used in a formal setting. What we believe is that it is also equivalent to our informal, intuitive understanding of the term.