Alan Turing and the other theory of computation (expanded)
| Autor: | Lenore Blum |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Computer science
business.industry Church–Turing thesis Epistemology law.invention Turing machine symbols.namesake Hypercomputation TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Turing completeness law Theory of computation symbols Time hierarchy theorem Universal Turing machine Artificial intelligence business Turing computer computer.programming_language |
| Zdroj: | Turing's Legacy |
| Popis: | We recognize Alan Turing's work in the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), its influence in modern complexity theory, and how it helps provide a unifying concept for the two major traditions of the theory of computation. §1. Introduction . The two major traditions of the theory of computation, each staking claim to similar motivations and aspirations, have for the most part run a parallel non-intersecting course. On one hand, we have the tradition arising from logic and computer science addressing problems with more recent origins, using tools of combinatorics and discrete mathematics. On the other hand, we have numerical analysis and scientific computation emanating from the classical tradition of equation solving and the continuous mathematics of calculus. Both traditions are motivated by a desire to understand the essence of computation, of algorithm; both aspire to discover useful, even profound, consequences. While the logic and computer science communities are keenly aware of Alan Turing's seminal role in the former (discrete) tradition of the theory of computation, most remain unaware of Alan Turing's role in the latter (continuous) tradition, this notwithstanding the many references to Turing in the modern numerical analysis/computational mathematics literature, e.g., [Bur 10, Hig02, Kah66, TB97, Wil71]. These references are not to recursive/computable analysis (suggested in Turing's seminal 1936 paper), usually cited by logicians and computer scientists, but rather to the fundamental role that the notion of “condition” (introduced in Turing's seminal 1948 paper) plays in real computation and complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|