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

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: 230-265.
   • 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.

   • Click on the title to do a Google search of various online versions.
     • The most common on-line version is best read using Microsoft Internet Explorer (or any other browser that uses cascaded style sheets).
       • Warning: That on-line version has several typographical errors!

     • Here is another, more readable, online version!

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

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

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

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

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

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

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

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

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

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

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

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

12. Chisum, Donald S. (1985-1986), "The Patentability of Algorithms", University of Pittsburgh Law Review 47: 959-1022.
    • See "Can Programs be Copyrighted or Patented?"

13. Davis, Martin (1987), "Mathematical Logic and the Origin of Modern Computers" [PDF], 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.

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

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

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

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

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

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

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

21. 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..."

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36. 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?"

37. "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.

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

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

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

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

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

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.