Philosophy of Computer Science

What Is an Algorithm?

What Is Computation?

(Boldface items are particularly important or interesting.)
(Many items that do not have links may be available online from the UB Libraries Electronic Journal holdings.)

Last Update: 4 December 2013

Note: NEW or UPDATED material is highlighted



Examples of Algorithms:

  1. Some humorous examples

  2. Robertson, Jane I. (1979), "How to Do Arithmetic", American Mathematical Monthly 86(6) (June-July): 431-439.

  3. Is this an algorithm? UPDATED

  4. Stewart, Ian (2001), "Easter is a Quasicrystal", Scientific American (March): 80, 82-83.

  5. Phone Number Trick

  6. Another trick

  7. For a discussion of one of the first searching algorithms for a list sorted alphabetically, dating from 1604(!), see the highlighted paragraph from:



Articles on the Nature of Algorithms

"What is the difference between a Turing machine and the modern computer? It's the same as that between Hillary's ascent of Everest and the establishment of a Hilton hotel on its peak."
Alan Perlis

  1. Turing, Alan M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Ser. 2, Vol. 42 (1937): 230–265. [PDF]



  2. Carpenter, B.E.; & Doran, R.W. (1975?), "The Other Turing Machine", The Computer Journal 20(3): 269-279.

  3. Leiber, Justin (2006), "Turing's Golden: How Well Turing's Work Stands Today" Philosophical Psychology 19(1): 13-46.

  4. Michie, Donald (2008), "Alan Turing's Mind Machines", in Philip Husbands, Owen Holland, & Michael Wheeler (eds.), The Mechanical Mind in History (Cambridge, MA: MIT Press), Ch. 4, pp. 61–74.

  5. Henkin, Leon (1962), "Are Logic and Mathematics Identical?", Science 138(3542) (November 16): 788-794.

  6. Boehm, C., & Jacopini, G. (1966), "Flow Diagrams, Turing Machines, and Languages with only Two Formation Rules", Communications of the ACM 9(5): 366-371.

  7. Wangsness, T., & Franklin, J. (1966), " "Algorithm" and "Formula" ", Communications of the ACM 9(4) (April): 243.

  8. Knuth, Donald (1973), "Basic Concepts: §1.1: Algorithms" (plus a few other neat things:-), The Art of Computer Programming, Second Edition (Reading, MA: Addison-Wesley): xiv-9.

  9. Knuth, Donald (1974), "Computer Science and Its Relation to Mathematics", American Mathematical Monthly 81(4) (April): 323-343.

  10. Weizenbaum, Joseph (1976), Computer Power and Human Reason (New York: W.H. Freeman).

  11. Gandy, Robin (1980), "Church's Thesis and Principles for Mechanisms" [PDF], in Jon Barwise, H.J. Keisler, & K. Kunen (eds.), The Kleene Symposium (Amsterdam: North-Holland): 123-148.

  12. Haugeland, John (1981), "Semantic Engines: An Introduction to Mind Design", in John Haugeland (ed.), Mind Design: Philosophy, Psychology, Artificial Intelligence (Cambridge, MA: MIT Press): 95-128.

  13. Herman, Gabor T. (1983), "Algorithms, Theory of" [PDF], in Anthony S. Ralston (ed.), Encyclopedia of Computer Science and Engineering, 2nd edition (New York: Van Nostrand Reinhold): 57-59.

  14. Rapaport, William J. (1985), "Turing Machines" [PDF], from Morton L. Schagrin, Randall R. Dipert, & William J. Rapaport, Logic: A Computer Approach (New York: McGraw-Hill): 327-339.

  15. Chisum, Donald S. (1985-1986), "The Patentability of Algorithms", University of Pittsburgh Law Review 47: 959-1022.

  16. Davis, Martin (1987), "Mathematical Logic and the Origin of Modern Computers", Studies in the History of Mathematics; reprinted in Rolf Herken (ed.), Universal Turing Machine: A Half-Century Survey; Second Edition (Vienna: Springer-Verlag, 1995): 135-158. [PDF]

  17. Kreisel, Georg (1987), "Church's Thesis and the Ideal of Informal Rigour", Notre Dave Journal of Formal Logic 28(4): 499-519.

    • Argues that Church's Thesis can be proved.

  18. Kleene, Stephen C. (1988), "Turing's Analysis of Computability and Major Applications of It", in Rolf Herken (ed.), Universal Turing Machine: A Half-Century Survey; Second Edition (Vienna: Springer-Verlag, 1995): 15-49.

  19. Dewdney, A.K. (1989), "Algorithms: Cooking Up Programs", "Turing Machines: The Simplest Computers", and "Universal Turing Machines: Computers as Programs", Chs. 1, 28, & 48 from Dewdney's The Turing Omnibus: 61 Excursions in Computer Science (Rockville, MD: Computer Science Press).

  20. Crossley, John N., & Henry, Alan S., "Thus Spake Al-Khwarizmi: A Translation of the Text of Cambridge University Library ms. Ii.vi.5", Historia Mathematica 17(2) (1990): 103-131.

  21. Mendelson, Elliott (1990), "Second Thoughts about Church's Thesis and Mathematical Proofs", Journal of Philosophy 87(5) (May): 225-233.

  22. Herman, Gabor T. (1993), "Algorithms, Theory of", in Anthony Ralston & Edwin D. Reilly (eds.), Encyclopedia of Computer Science, 3rd Edition, (New York: Van Nostrand Reinhold): 37-39.

  23. Korfhage, Robert R. (1993), "Algorithm", in Anthony Ralston & Edwin D. Reilly (eds.), Encyclopedia of Computer Science, 3rd Edition, (New York: Van Nostrand Reinhold): 27-29.

  24. Shapiro, Stewart (1993), "Understanding Church's Thesis, Again", Acta Analytica 11: S.59-77.

    • "tries to show that Church's thesis can be proved mathematically..."

  25. Harnad, Stevan (ed.) (1994), Special Issue on "What Is Computation?", Minds and Machines 4(4).

  26. Copeland, B. Jack (1996), "What Is Computation?" [PDF of preprint version], Synthese 108: 335-359.

  27. Soare, Robert I. (1996), "Computability and Recursion", Bulletin of Symbolic Logic 2(3) (September): 284-321.

  28. Sieg, Wilfried (1997), "Step by Recursive Step: Church's Analysis of Effective Calculability", Bulletin of Symbolic Logic 3(2) (June): 154-180.

  29. Suber, Peter (1997), "Turing Machines" (a 2-part handout; click on "second hand-out" at the end of part I to get to part II).

  30. Folina, Janet (1998), "Church's Thesis: Prelude to a Proof", Philosophia Mathematica 6: 302-323.

  31. Moschovakis, Yiannis N. (1998), "On Founding the Theory of Algorithms", in H.G. Dales & G. Oliveri (eds.), Truth in Mathematics (Oxford: Clarendon Press): 71–104.

  32. Farkas, David K. (1999), "The Logical and Rhetorical Construction of Procedural Discourse" [PDF], Technical Communication 46(1) (February): 42-54.

  33. Floridi, Luciano (1999), Philosophy and Computing: An Introduction (London: Routledge), Ch. 2: "The Digital Workshop".

  34. Shagrir, Oron (1999), "What Is Computer Science About?" [PDF], The Monist 82(1): 131-149.

  35. Preston, Beth (2000), "Recipes and Songs: Towards a Theory of Production" [PDF].

  36. Smith, Brian Cantwell (2002), "The Foundations of Computing", in Matthias Scheutz (ed.), Computationalism: New Directions (Cambridge, MA: MIT Press): 23-58.

  37. Blass, Andreas; & Gurevich, Yuri (2003), "Algorithms: A Quest for Absolute Definitions" [PDF], Bulletin of the European Association for Theoretical Computer Science (EATCS) No. 81 (October): 195-225.

  38. Sieg, Wilfried (2004?), "Church without Dogma: Axioms for Computability".

  39. Copeland, B. Jack (2004), "Computation", in Luciano Floridi (ed.), The Blackwell Guide to the Philosophy of Computing and Information (Malden, MA: Blackwell).

  40. Copeland, B. Jack, & Aston, Gordon, AlanTuring.net Catalogue of Reference Articles

  41. Chaitin, Gregory (2006) "How Real Are Real Numbers?", International Journal of Bifurcation and Chaos

  42. Chazelle, Bernard (2006), "The Algorithm: Idiom of Modern Science"

  43. Sieg, Wilfried (2006), "Gödel on Computability", Philosophia Mathematica 14 (June): 189-207.

  44. Piccinini, Gualtiero (2007), "Computationalism, the Church-Turing Thesis, and the Church-Turing Fallacy", Synthese 154: 97-120.

  45. Rescorla, Michael (2007), "Church's Thesis and the Conceptual Analysis of Computability", Notre Dame Journal of Formal Logic 48(2): 253-280.

  46. Schulman, Ari N. (2009), "Why Minds Are Not Like Computers", The New Atlantis (Winter): 46-68.

  47. Gurevich, Yuri (2011), "What Is an Algorithm?", Technical Report MSR-TR-2011-116 (Redmond, WA: Microsoft Research).


What is a heuristic?

  1. Newell, Allen, & Simon, Herbert A. (1976), "Computer Science as Empirical Inquiry: Symbols and Search", Communications of the ACM 19(3) (March): 113-126.

  2. Romanycia, Marc H.J., & Pelletier, Francis Jeffry (1985), "What Is a Heuristic?" [PDF], Computational Intelligence 1: 47-58.

  3. Korf, Richard E. (1992), "Heuristics", in Stuart C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, 2nd Edition (New York: John Wiley & Sons): 611-615.

  4. Shapiro, Stuart C. (1992), "Artificial Intelligence", in Stuart C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, 2nd Edition (New York: John Wiley & Sons): 54-57.

    • Revised version appears in
      Anthony Ralston & Edwin D. Reilly (eds.), Encyclopedia of Computer Science, 3rd Edition, (New York: Van Nostrand Reinhold, 1993): 87-90.

  5. Findler, Nicholas V. (1993), "Heuristic", in Anthony Ralston & Edwin D. Reilly (eds.), Encyclopedia of Computer Science, 3rd Edition, (New York: Van Nostrand Reinhold): 611-612.

  6. Rapaport, William J. (1998), "How Minds Can Be Computational Systems" [PDF], Journal of Experimental and Theoretical Artificial Intelligence 10: 403-419.
  7. Oommen, B. John; & Rueda, Luis G. (2005), "A Formal Analysis of Why Heuristic Functions Work", Artificial Intelligence 164(1-2) (May): 1-22.

  8. Thagard, Paul (2007), "Coherence, Truth, and the Development of Scientific Knowledge", Philosophy of Science 74 (January): 28-47.

    • Not about heuristics, but presents a theory of "approximate" truth that bears a close resemblance to the idea that a heuristic is an algorithm that computes an approximately correct answer.



Text copyright © 2004–2013 by William J. Rapaport (rapaport@buffalo.edu)
Cartoon links and screen-captures appear here for your enjoyment.
They are not meant to infringe on any copyrights held by the creators.
For more information on any cartoon, click on it, or contact me.

http://www.cse.buffalo.edu/~rapaport/584/whatisanalg.html-20131204