Foundational Analyses of Computation

详细信息    查看全文

• 作者：Yuri Gurevich (1)
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7318
• 期：1
• 页码：264-275
• 全文大小：180.5 KB
• 参考文献：1. Blass, A., Gurevich, Y.: Algorithms: A quest for absolute definitions. In: Paun, G., et al. (eds.) Current Trends in Theoretical Computer Science, pp. 283–311. World Scientific (2004); also in: Olszewski, A. (ed.): Church’s Thesis After 70 Years Ontos Verlag, pp. 24–57. Ontos Verlag (2006)
  2. Blass, A., Gurevich, Y.: Abstract state machines capture parallel algorithms. ACM Trans. on Computational Logic 4(4), 578–651 (2003); Correction and Extension, Same Journal 9(3), article 19 (2008)
  3. Blass, A., Gurevich, Y.: Ordinary interactive small-step algorithms. ACM Trans. Computational Logic 7(2), Part I, 363–419 (2006); plus 8:3 , articles 15 and 16 (Parts II and III) (2007)
  4. Blass, A., Gurevich, Y., Rosenzweig, D., Rossman, B.: Interactive small-step algorithms. Logical Methods in Computer Science 3(4) (2007); papers 3 and 4 (Part I and Part II)
  5. Dershowitz, N., Gurevich, Y.: A natural axiomatization of computability and proof of Church’s thesis. Bull. of Symbolic Logic 14(3), 299–350 (2008)
  6. Church, A.: An unsolvable problem of elementary number theory. American Journal of Mathematics 58, 345–363 (1936)
  7. Gandy, R.: Church’s thesis and principles for mechanisms. In: Barwise, J., et al. (eds.) The Kleene Symposium, pp. 123–148. North-Holland (1980)
  8. Gandy, R.O., Yates, C.E.M. (eds.): Collected works of A.M. Turing: Mathematical logic. Elsevier (2001)
  9. G枚edel, K.: A philosophical error in Turing’s work. In: Feferman, S., et al. (eds.) Kurt G枚del: Collected Works, vol. II, p. 306. Oxford University Press (1990)
  10. Gurevich, Y.: On Kolmogorov machines and related issues. Bull. of Euro. Assoc. for Theor. Computer Science 35, 71–82 (1988)
  11. Gurevich, Y.: Evolving algebra 1993: Lipari guide. In: B枚rger, E. (ed.) Specification and Validation Methods, pp. 9–36. Oxford Univ. Press (1995)
  12. Gurevich, Y.: Sequential abstract state machines capture sequential algorithms. ACM Trans. on Computational Logic 1(1), 77–111 (2000)
  13. Gurevich, Y.: What Is an Algorithm? In: Bielikova, M., et al. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 31–42. Springer, Heidelberg (2012)
  14. Kolmogorov, A.N.: On the concept of algorithm. Uspekhi Mat. Nauk 8(4), 175–176 (1953) (Russian)
  15. Kolmogorov, A.N., Uspensky, V.A.: On the definition of algorithm. Uspekhi Mat. Nauk 13(4), 3–28 (1958) (Russian); English translation in AMS Translations 29, 217–245 (1963)
  16. Levin, L.A.: Private communication (2003)
  17. Markov, A.A.: Theory of algorithms. Trans. of the Steklov Institute of Mathematics 42 (1954) (Russian); English translation by the Israel Program for Scientific Translations, 1962; also by Kluwer (2010)
  18. Shagrir, O.: Effective computation by humans and machines. Minds and Machines 12, 221–240 (2002)
  19. Shagrir, O.: G枚edel on Turing on computability. In: Olszewski, A., et al. (eds.) Church’s Thesis After 70 Years, pp. 393–419. Ontos-Verlag (2006)
  20. Sieg, W.: On computability. In: Irvine, A. (ed.) Handbook of the Philosophy of Mathematics, pp. 535–630. Elsevier (2009)
  21. Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of London Mathematical Society 2(42), 230–265 (1936)
  22. Uspensky, V.A.: Kolmogorov and mathematical logic. Journal of Symbolic Logic 57(2), 385–412 (1992)
  23. Uspensky, V.A., Semenov, A.L.: Theory of algorithms: main discoveries and applications, Nauka (1987) (Russian), Kluwer (2010) (English)
• 作者单位：1. Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, United States of America
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

How can one possibly analyze computation in general? The task seems daunting if not impossible. There are too many different kinds of computation, and the notion of general computation seems too amorphous. As in quicksand, one needs a rescue point, a fulcrum. In computation analysis, a fulcrum is a particular viewpoint on computation that clarifies and simplifies things to the point that analysis becomes possible.