Classical physics and the Church--Turing Thesis

@article{citeulike:504932, abstract = {Would physical laws permit the construction of computing machines that are capable of solving some problems much faster than the standard computational model? Recent evidence suggests that this might be the case in the quantum world. But the question is of great interest even in the realm of classical physics. In this article, we observe that there is fundamental tension between the Extended Church--Turing Thesis and the existence of numerous seemingly intractable computational problems arising from classical physics. Efforts to resolve this incompatibility could both advance our knowledge of the theory of computation, as well as serve the needs of scientific computing.}, address = {New York, NY, USA}, author = {Yao, Andrew C.}, citeulike-article-id = {504932}, doi = {10.1145/602382.602411}, issn = {0004-5411}, journal = {J. ACM}, keywords = {church, computing, turing}, month = {January}, number = {1}, pages = {100--105}, posted-at = {2006-02-14 09:37:36}, priority = {4}, publisher = {ACM Press}, title = {Classical physics and the Church--Turing Thesis}, url = {http://dx.doi.org/10.1145/602382.602411}, volume = {50}, year = {2003} }

TY - JOUR ID - citeulike:504932 L3 - citeulike-article-id:504932 N2 - Would physical laws permit the construction of computing machines that are capable of solving some problems much faster than the standard computational model? Recent evidence suggests that this might be the case in the quantum world. But the question is of great interest even in the realm of classical physics. In this article, we observe that there is fundamental tension between the Extended Church--Turing Thesis and the existence of numerous seemingly intractable computational problems arising from classical physics. Efforts to resolve this incompatibility could both advance our knowledge of the theory of computation, as well as serve the needs of scientific computing. IS - 1 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 105 TI - Classical physics and the Church--Turing Thesis PB - ACM Press VL - 50 SP - 100 KW - church KW - computing KW - turing AU - Yao, Andrew PY - 2003/01// UR - http://dx.doi.org/10.1145/602382.602411 ER -