What Is an Algorithm?

What Is Computation?

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.
   • Contains examples of algorithms for doing elementary arithmetic.

3. Is this an algorithm?

4. Stewart, Ian (2001), "Easter is a Quasicrystal", Scientific American (March): 80, 82-83.
   • Includes an algorithm for computing the date of Easter.

5. Phone Number Trick

6. Another trick
   link

7. For a discussion of one of the first searching algorithms for a list sorted alphabetically, dating from 1604(!), see the highlighted paragraph from:
   • Gleick, James (2008), "‘If Shakespeare Had Been Able to Google…’", The New York Review of Books (December 18): 77-79; highlighted paragraph on p. 78, cols. 2-3.

• Rapaport, William J. (2010), "What Is Computation?"
  • lecture notes

• Etymology of ‘Compute’

Articles on the Nature of Algorithms

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]
   • Reprinted, with corrections, in Martin Davis (ed.), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (New York: Raven Press, 1965): 116-154.

   • And here is a fantastic, annotated version!:
     Petzold, Charles (2008), The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine (Indianpolis: Wiley).
     • There are 3 separate links in the above title.
     • See also a book review:
       Davis, Martin (2008), "Touring Turing" (review of Petzold 2008), American Scientist 96(6) (November-December): 520.

   • For a good, slow-reading analysis of one sentence of Turing 1936, see:
     Dresner, Eli (2003), "Effective Memory and Turing's Model of Mind", Journal of Experimental & Theoretical Artificial Intelligence 15(1): 113–123.

   ---

   

   ---

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.
   • An excellent brief overview of the history of logic and the foundations of mathematics.
   • The "Henkin" link above is to a "webarchive" file of Henkin's obituary, which may only be readable via Safari.
   • The "Leon" link above is to an "rtfd" directory containing the same obituary, which should be downloadable and readable by any word processor that can handle RTF files.
     Alternatively, download that .rtfd directory; it contains two files, TXT.rtf, which contains the text of the obit, and unknown.jpg, which contains a photo of Henkin.

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.
   Abstract: This paper contains a proof that every program with gotos can be transformed into a semantically equivalent program without goto. A transformation algorithm is given.
   • Discussed in:
     Raskin, Jef (2003), Letter to the Editor about "Life beyond OOP", American Scientist 91 (May-June): 197-198.

7. Wangsness, T., & Franklin, J. (1966), " "Algorithm" and "Formula" ", Communications of the ACM 9(4) (April): 243.
   • This is a letter to the editor that is so short that I am going to reprint it in its entirety here:
     Editor:
     We are making this communication intentionally short to leave as much room as possible for the answers.
     
     1. Please define "Algorithm."
     2. Please define "Formula."
     3. Please state the difference.
     T. WANGSNESS
     J. FRANKLIN
     TRW Systems
     Redondo Beach, California
   The published answers:
   1. Huber, Harmut G.M. (1966), "Algorithm and Formula", Communications of the ACM 9(9) (September): 653-654.

   2. Knuth, Donald (1966), "Algorithm and Program: Information and Data", 9(9) (September): 654.

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).
    • Ch. 2 ("Where the Power of the Computer Comes From") contains a masterful presentation of a Turing Machine implemented with pebbles and toilet paper!
    • This is also an excellent book on the role of computers in society, by the creator of the "Eliza" program.

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.
    • Argues "that Turing's analysis of computation by a human being does not apply directly to mechanical devices." Gandy was Turing's only Ph.D. student.

    • A follow-up article that simplifies and generalizes Gandy's paper:
      Sieg, Wilfried, & Byrnes, John (1999), "An Abstract Model for Parallel Computation: Gandy's Thesis", The Monist 82(1) (January): 150-164.

    • Israel, David (2002), "Reflections on Gödel's and Gandy's Reflections on Turing's Thesis", Minds and Machines 12(2) (May): 181-201.

    • Shagrir, Oron (2002), "Effective Computation by Humans and Machines", Minds and Machines 12(2) (May): 221-240.

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.
    • See "Can Programs be Copyrighted or Patented?"

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).
    • Included primarily for Ch. 48 on Universal Turing Machines, with the earlier chapters included for the sake of completeness.

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.
    • SCI/ENGR Periodical Collection Per QA21 .H54

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).
    Contents:
    
    • Harnad, Stevan, "Preface", pp. 377-378.
    • Harnad, Stevan, "Computation Is Just Interpretable Symbol manipulation; Cognition Isn't", pp. 379-390.
    • Chalmers, David J., "On Implementing a Computation", pp. 391-402.
    • Chrisley, Ronald L., "Why Everything Doesn't Realize Every Computation", pp. 403-420.
    • MacLennan, Bruce J., "Words Lie in Our Way", pp. 421-437.
    • Kentridge, Robert W., "Symbols, Neurons, Soap-Bubbles, and the Neural Computation underlying Cognition", pp. 439-449.
    • Boyle, C. Franklin, "Computation as an Intrinsic Property", pp. 451-467.
    • Bringsjord, Selmer, "Computation, among Other Things, Is beneath Us", pp. 489-490.

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.
    • See also:
      Soare, Robert I. (1999), "The History and Concept of Computability" [PDF], in E.R. Griffor (ed.), Handbook of Computability Theory (Amsterdam: Elsevier): 3-36.
      • "a revised and shortened form" of Soare 1996.

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.
    • postscript [.ps]
    • [PDF]
    • Moschovakis, Yiannis N. (2001), "What Is an Algorithm?", in B. Engquist & W. Schmid (eds.), Mathematics Unlimited: 2001 and Beyond (Berlin: Springer): 918–936.

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.
    • Despite its title, this paper is more about what computers are and what computation is; Shagrir assumes that CS is the science of computers.

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
    • Website that contains a variety of interesting papers on various aspects of Turing's work, most written by Copeland, a well-respected contemporary philosopher, including:
      1. Copeland, Jack (2000), "The Church-Turing Thesis"
      2. Copeland, Jack (2000), "What Is a Turing Machine?"

41. Chaitin, Gregory (2006) "How Real Are Real Numbers?", International Journal of Bifurcation and Chaos
    • Also see:
      Chaitin, Gregory (2006), "The Limits of Reason", Scientific American (March): 74-81.

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.
    • Rescorla argues that Church's Thesis (that a number-theoretic function is intuitively computable iff it is recursive) is not the same as Turing's Thesis (that a number-theoretic function is intuitively computable iff a corresponding string-theoretic function [that represents the number-theoretic one] is computable by a Turing machine).

    • See also:
      Shapiro, Stuart C. (1977), "Representing Numbers in Semantic Networks: Prolegomena", in Proceedings of the 5th International Joint Conference on Artificial Intelligence (Los Altos, CA: Morgan Kaufmann): 284.

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).

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), 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.