Philosophy of Computer Science: Online Resources

Further Readings for Chapter 7:

Algorithms and Computability

Note 1: Many of these items are online; links are given where they are known. Other items may also be online; an internet search should help you find them.

Note 2: In general, works are listed in chronological order. (This makes it easier to follow the historical development of ideas.)

General Readings on Computability

• Henkin 1962, pp. 788–791, is an excellent, brief overview of the history of logic and the foundations of mathematics that led up to Turing's analysis.

• Davis 1995 overlaps and extends Henkin's history, and provides a useful summary of Turing 1936, which we will discuss in great detail in the next chapter.

• Harnad, S., editor (1994). What Is Computation? is a special issue of the journal Minds and Machines (Vol. 4, No. 4), including, among others:
  • Bringsjord, S. (1994). Computation, among other things, is beneath us. Minds and Machines, 4(4):489–490.

  • Chalmers, D.J. (1994). On implementing a computation. Minds and Machines, 4(4):391–402. Originally §2 of "A Computational Foundation for the Study of Cognition".

  • Harnad, S. (1994). Computation is just interpretable symbol manipulation; cognition isn’t. Minds and Machines, 4(4):379–390.

• Shagrir 1999 discusses what computers are and what computation is.

• Soare, R.I. (1999). The history and concept of computability. In Griffor, E., editor, Handbook of Computability Theory, pages 3–36. North-Holland, Amsterdam, especially §§1–3, 4.5–4.6.
  • An excellent source on the history and terminology of computability.

• Herman, G.T. (2000). Algorithms, theory of. In Ralston, A., Riley, E.D., and Hemmindinger, D., editors, Encyclopedia of Computer Science, 4th edition, pages 51–53. Grove's Dictionaries/Nature Publishing Group, New York/London.
  • Discusses the informal notions of "algorithm" and "effective computability"; good background for Turing 1936.

• Smith, B.C. (2002). The foundations of computing. In Scheutz, M., editor, Computationalism: New Directions, pages 23–58. MIT Press, Cambridge, MA.

• "PolR" 2009 is an excellent introduction for lawyers(!) to computation theory.

• Bernhardt, C. (2016). Turing's Vision: The Birth of Computer Science. MIT Press, Cambridge, MA.
  • An excellent guide for the general reader to the mathematics of computation theory.

"Many now view computation as a fundamental part of nature, like atoms or the integers."
 — Fortnow, L. (2010). What is computation? Ubiquity, Article 5, p. 2.

'compute':
According to the OED, the verb 'to compute' comes from the Latin verb ' computare', meaning "to calculate, reckon, to count up". But when people talk about "computing" today, they mean a great deal more than mere counting. Computing has come to include everything we can do with computers, including text processing, watching videos, and playing games. So, clearly, the meaning has been extended to include non-numerical "reckoning".

The Latin word ' computare', in turn, comes from the Latin morpheme ' com', meaning "together with", and the Latin word ' putare', meaning "to cleanse, to prune, to reckon, to consider, think" (and ' putare' came from a word meaning "clean, pure"). So, in ancient Rome at least, to "compute" seems to have meant, more or less, something like: "to consider or think about things together", "to clear things up together", or maybe "to reckon with (something)".

'reckon':
The verb 'to reckon' originally meant "to give an account of, recount; to tell; to describe", and later came to mean "to count, to calculate". 'Reckon' is from an Indo-European root 'rek', possibly meaning "to reach" or "to tell, to narrate, to say" (as in "to recite" or "to recount"). These meanings, in turn, may derive from an earlier meaning "to arrange", "to put right", "to move in a straight line".

'count':
'Count' also came from 'computare' and originally meant "to enumerate", "to recite a list" (and, as we just saw, 'recite' is probably related to 'reckon'). Note that when you "count", you "recite" a list of number words.

'calculate':
'Calculate' came from Latin 'calculus'. This certainly did not mean the contents of a certain high school or college course that studies the branch of mathematics concerned with differentiation and integration, and invented by Newton and Leibniz in the 17th century! Rather, it meant "pebble" or "small stone", since counting was done with stones originally. (As a Rhymes with Orange comic strip from 22 August 2011 put it, "There is more computing power in this little abacus than in all the giant rocks we move aorund to do addition.") Even today, a "calculus" in medicine is an accumulation of minerals in the body, forming a small, stone-like object. The root 'calc' came from 'calx', meaning "chalk, limestone", and is related to 'calcium'.

'figure':
The verb 'to figure' means "to use figures to reckon". The earliest citation in the OED for the noun 'figure' is from 1225, when it meant "numerical symbol". A citation from 1250 has the meaning "embodied (human) form". And a citation from 1300 has the more general meaning of "shape". (This conversion of the noun 'figure' to a verb is an example of what Alan Perlis meant when he joked, "In English, every word can be verbed".)

The bottom line seems to be this: 'Computation' originally meant something very closely related to our modern notion of "symbol (that is, shape) manipulation", which is another way of describing syntax — the "grammatical" properties of, and relations among, the symbols of a language. (We discuss syntax in §§13.2, 15.2.1, 16.10, and 18.8.3.)

On the history of the terms 'computable' vs. 'recursive', see:

• Soare, R. I. (2009). Turing oracle machines, online computing, and three displacements in computability theory. Annals of Pure and Applied Logic, 160:368–399, especailly §11.5, p. 391.

We discuss recursive functions in §7.6.

§7.2.3: Functions Described Intensionally:

For more on the notion of understanding in terms of the internal workings of a black box, see:

• Strevens, M. (2013, 24 November). Looking into the black box. New York Times Opinionator.

which also suggests an analogy between computation and causation.

§7.3.1: Ancient Algorithms:

For more on Al-Khwarizmi and his algorithms, see:

• Crossley, J. N. and Henry, A. S. (1990). Thus spake al-Khwarizmi: A translation of the text of Cambridge University Library ms. Ii.vi.5. Historia Mathematica, 17:103–131.

• O'Connor, J. and Robertson, E. (1999). Abu Ja'far Muhammad ibn Musa Al-Khwarizmi. MacTutor History of Mathematics Archive

• Devlin, K. (2011). The Man of Numbers: Fibonacci's Arithmetic Revolution. Walker & Co., New York, Ch. 4.

§7.3.2: "Effectiveness":

• Church, A. (1956). Introduction to Mathematical Logic. Princeton University Press, Princeton, NJ.
  • Calls 'effective' an "informal notion". See:
    • pp. 50–51:
      • Gives four "requirements" for effectiveness, each of which uses the term 'effective'!
    • p. 52:
      • "We have assumed the reader's understanding of the general notion of effectiveness, and indeed it must be considered as an informally familiar mathematical notion … . We shall not try to give here a rigorous definition of effectiveness, the informal notion being sufficient … ."
    • p. 52, note 118:
      • "an effective method of calculating, especially if it consists of a sequence of steps with later steps depending on results of earlier ones, is called an algorithm"
    • p 53, note 119:
      • "an effective method of computation, or algorithm, is one for which it would be possible to build a computing machine", by which he means a Turing Machine
    • p. 83:
      • Seems to identify effectiveness with "mechanical procedure".
    • p. 99, note 183:
      • "a procedure … should not be called effective unless there is a predictable upper bound of the number of steps that will be required"
    • p. 326, note 535:
      • Discusses the "non-effective notion of [logical] consequence" (my italics).

• See also:
  • Manzano 1997, pp. 219–220.

  • Sieg, W. (1997). Step by recursive step: Church's analysis of effective calculability. Bulletin of Symbolic Logic, 3(2):154–180.

  • Copeland, B. J. (2000). The Church-Turing thesis.

• Another explication of 'effective' is on p. 124 of:
  • Gandy, R. (1980). Church's thesis and principles for mechanisms. In Barwise, J., Keisler, H., and Kunen, K., editors, The Kleene Symposium, pages 123–148. North-Holland.

§7.3.3: Three Attempts at Precision

On Procedures vs. Algorithms:

• Hopcroft, J.E. and Ullman, J.D. (1969). Formal Languages and Their Relation to Automata. Addison-Wesley, Reading, MA, pp. 2–3.
  • Distinguishes a "procedure" from an "algorithm". In their "vague … definition", a procedure is "a finite sequence of instructions that can be mechanically carried out, such as a computer program" (to be formally defined in their chapter on Turing Machines), and an algorithm is "a procedure which always terminates".

• For more on the attempts to make the notion of "algorithm" precise, see:
  • Sieg 1994
    • Contains a detailed history and analysis of the development of the formal notions of algorithm in the 1930s and after.

  • Copeland 1997
    • An essay on hypercomputation — or "non-classical" computation — whose introductory section (pp. 690–698) contains an enlightening discussion of the scope and limitations of Turing's accomplishments.

  • See also:
    • Korfhage, R.R. (1993). Algorithm. In Ralston, A. and Reilly, E.D., editors, Encyclopedia of Computer Science, 3rd Edition, pages 27&–29. Van Nostrand Reinhold, New York.

    • Copeland, B.J. (1996). What is computation? Synthese, 108:335–359.

    • Sieg 1997

    • Moschovakis, Y.N. (1998). On founding the theory of algorithms. In Dales, H. and Oliveri, G., editors, Truth in Mathematics, pages 71–104. Clarendon Press, Oxford.

    • Moschovakis, Y.N. (2001). What is an algorithm? In Engquist, B. and Schmid, W., editors, Mathematics Unlimited: 2001 and Beyond, pages 918–936. Springer, Berlin

    • Blass, A. and Gurevich, Y. (2003). Algorithms: A quest for absolute definitions. Bulletin of the European Association for Theoretical Computer Science (EATCS), 81:195–225.

    • Copeland 2004

    • Chazelle 2006

    • Sieg, W. (2008). Church without dogma: Axioms for computability. In Cooper, S., Löwe, B., and Sorbi, A., editors, New Computational Paradigms: Changing Conceptions of What Is Computable, pages 139–152. Springer.

    • Gurevich, Y. (2011). What is an algorithm? In SOFSEM 2012: Theory and Practice of Computer Science, pages 31–42. Springer Lecture Notes in Computer Science 7147.

    • Hill, R.K. (2013). What an algorithm is, and is not. Communications of the ACM, 56(6):8–9.

    • Dean, Walter (2016), "Algorithms and the Mathematical Foundations of Computer Science", in Leon Horsten & Philip Welch (eds.), Gödel's Disjunction: The Scope and Limits of Mathematical Knowledge (Oxford: Oxford University Press):19–66.
      • Argues that the identification of algorithms with mathematical objects suffers from the same limitations of the identification of numbers with sets, as in Benacerraf, Paul (1965), "What Numbers Could Not Be", Philosophical Review 74(1):47–73.

  • In §12.3.4, we look at whether computer programs can be copyrighted or patented.
    In order to answer this question, many legal experts have tried to give a definition of 'algorithm'.
    One such attempt is:
    • Chisum, D. S. (1985-1986). The patentability of algorithms. University of Pittsburgh Law Review, 47:959–1022.

  • Farkas, D.K. (1999). The logical and rhetorical construction of procedural discourse. Technical Communication, 46(1):42–54.
    • Contains advice on how to write informal procedures.

• On input/output, as discussed in the section on Knuth, see the discussion of external input vs. internal states in §§2 and 3.2 of:
  • Ritchie, J. Brendan; & Piccinini, Gualtiero (2018), "Computational Implementation", in Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind (London: Routledge):192–204.

§7.4.1: Insight 1: Representation:

• For more on binary representation, link to Great Idea I: Binary Representation,
  and see:
  Heath, F.G. (1972), "Origins of the Binary Code", Scientific American 227(2) (August):76–83,124
  

• The URL for the quotation from Francis Bacon should be replaced with by:
  Advancement of Learning by Lord Bacon; then search for "A Biliteral Alphabet"

• Wheeler, J. A. (1989). Information, physics, quantum: The search for links. In Proceedings III International Symposium on Foundations of Quantum Mechanics, pages 354–358. Tokyo.
  • Argues against the existence of the "continuum" of real numbers.

• Chaitin, G.J. (2006). How real are real numbers? International Journal of Bifurcation and Chaos.
  • "discuss[es] mathematical and physical arguments against continuity and in favor of discreteness".

• On Leibniz's binary insight, see:
  • Ross 1984, p. 29.

  • Chaitin 2009.

• For some interesting comments that are relevant to the insight about binary representation of information, see:
  • Cerf, V.G. (2014). Virtual reality redux. Commmunications of the ACM, 57(1):7.

• On Shannon, see:
  • Horgan, J. (1990, January). Profile: Claude E. Shannon; unicyclist, juggler and father of information theory. Scientific American, pages 22, 22A–22B.

  • Johnson, G. (2001). Claude Shannon, mathematician, dies at 84. New York Times, page B7.

  • Cerf, V.G. (2017). Information technology: A digital genius at play. Nature, 547(7662):159.

• Shapiro, Stewart; Snyder, E.; & Samuels, R. (2022), Computability, notation, and de re knowledge of numbers. Philosophies 7(1), p. 6.
  • Discusses the relative advantages of binary representation of natural numbers vs. unary representation.

§7.4.2: Insight 2: Processing:

For another minimal set of operations, see:

Wang, H. (1957). A variant to Turing's theory of computing machines. Journal of the ACM, 4(1):63–92, p. 63.
• "offer[s] a theory which is closely related to Turing's but is more economical in the basic operations. … [A] theoretically simple basic machine can be … specified such that all partial recursive functions (and hence all solvable computation problems) can be computed by it and that only four basic types of instruction are employed for the programs: shift left one space, shift right one space, mark a blank space, conditional transfer. … [E]rasing is dispensable, one symbol for marking is sufficient, and one kind of transfer is enough. The reduction is … similar to … the definability of conjunction and implication in terms of negation and disjunction … ."

A version of Wang's machine, with many examples, is given in Dennett 2013, Ch. 24.

§7.4.3: Insight 3: Structure:

• On structure:
  • Two cartoons that illustrate the benefits of good structure in programming are online:
    • XKCD: Good Code

    • Abstruse Goose: O.P.C.

  • For more on the structure insight, link to Great Idea III: The Boehm-Jacopini Theorem and Structured Programming.

• On abstraction:
  • Dijkstra, E.W. (1972). Notes on structured programming. In Dahl, O.J., Dijkstra, E.W., and Hoare, C.A.R., editors, Structured Programming, pages 1–82. Academic Press, London.

  • Pylyshyn 1992

  • Pattis, R.E., Roberts, J., and Stehlik, M. (1995). Karel the Robot: A Gentle Introduction to the Art of Programming, Second Edition. John Wiley & Sons, New York.
    • One of the best introductions to abstraction.

  • Dijkstra, E.W. (2001), What Led to "Notes on Structured Programming" (EWD1308)

  • Conery, J.S. (2010). What is computation? Computation is symbol manipulation. Ubiquity. Article 4

  • See also §5.2.2 of:
    Rapaport, W.J. (2017). On the relation of computing to the world. In Powers, T.M., editor, Philosophy and Computing: Essays in Epistemology, Philosophy of Mind, Logic, and Ethics, pages 29–64. Springer, Cham, Switzerland.

  • For more on the power of abstraction, see the first few paragraphs of:
    • Antoy, S. and Hanus, M. (2010). Functional logic programming. Communications of the ACM, 53(4):74–85.

§7.4.4: Insight 4: The Church-Turing Computability Thesis:

• Recommended textbooks on computability theory include:
  • Kleene, S.C. (1952). Introduction to Metamathematics. D. Van Nostrand, Princeton, NJ.

  • Davis, M.D. (1958). Computability & Unsolvability. McGraw-Hill, New York.

  • Kleene, S.C. (1967). Mathematical Logic. Wiley, New York.

  • Minsky, M. (1967). Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ.

  • Rogers, Jr., H. (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York.

  • Hopcroft and Ullman 1969

  • Boolos, G.S. and Jeffrey, R.C. (1974). Computability and Logic. Cambridge University Press, Cambridge, UK.

  • Clark, K.L. and Cowell, D.F. (1976). Programs, Machines, and Computation: An Introduction to the Theory of Computing. McGraw-Hill, London.

  • Kfoury, A., Moll, R.N., and Arbib, M.A. (1982). A Programming Approach to Computability. Springer-Verlag, New York.

  • Davis, M.D. and Weyuker, E.J. (1983). Computability, Complexity and Languages. Academic Press, New York.

  • Cooper, S.B. (2004). Computability Theory. Chapman & Hall, Boca Raton, FL.

  • Homer, S. and Selman, A.L. (2011). Computability and Complexity Theory, 2nd Edition. Springer, New York.

  • Soare 2016

• For discussion of the appeal to Gödel's authority, see:
  • Shagrir, O. (2006). Gödel on Turing on computability. In Olszewski, A., Wołenski, J., and Janusz, R., editors, Church's Thesis after 70 Years, pages 393–419. Ontos-Verlag.
    • Explores why Gödel believed both that:
      "the correct definition of mechanical computabilty was established beyond any doubt by Turing"
      (Gödel, K. (1938). Undecidable Diophantine propositions. In Feferman, S. et al., editors, Kurt Gödel: Collected Works, Vol. III, pages 164–175. Oxford University Press, 1995, Oxford, p. 168)

      and that:

      "this definition … rest[s] on the dubious assumption that there is a finite number of states of mind" (Shagrir 2006, §1).

  • Copeland, B.J. and Shagrir, O. (2013). Turing versus Gödel on computability and the mind. In Copeland, B. J., Posy, C. J., and Shagrir, O., editors, Computability: Turing, Gödel, Church, and Beyond, pages 1–33. MIT Press, Cambridge, MA.
    • Explores both Gödel's interpretations of Turing's work and the relation of the human mind to Turing Machines.

  • See also:
    • Sieg, W. (2006). Gödel on computability. Philosophia Mathematica, 14:189–207.

    • Soare 2009, §2, "Origins of Computabilty and Incomputablity".
      • Contains a good summary of the history of both Turing's and Gödel's accomplishments.

• Turing cites:
  • Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2):345–363,

  for the definition of lambda-definability.

  He cites:

  • Kleene, S.C. (1935-1936). General recursive functions of natural numbers. Mathematische Annalen, 112:727–742,

  for the definition of general recursiveness.

  And he cites:

  Kleene, S.C. (1936). λ-definability and recursiveness. Duke Mathematical Journal, 2:340–353.

  for the proof of their equivalence.

• For statements of equivalence of general recursive, μ-recursive, lambda-definable, etc., see:
  • Soare, R.I. (2012). Formalism and intuition in computability. Philosophical Transactions of the Royal Society A, 370:3277–3304, esp. p. 3284.

• Kleene, S.C. (1995). Turing's analysis of computability, and major applications of it. In Herken, R., editor, The Universal Turing Machine: A Half-Century Survey, Second Edition, pages 15–49. Springer-Verlag, Vienna.
  • Shows how to "compile" (or translate the language of) recursive functions into (the language of) Turing Machines, i.e., how a Turing Machine can compute recursive functions.

• Kreisel, G. (1987). Church's thesis and the ideal of informal rigour. Notre Dame Journal of Formal Logic, 28(4):499–519.
  • An essay by a well-known logician arguing that Church's Thesis can be proved.

• Similar arguments are made in:
  • Shapiro, Stewart (1993). Understanding Church's thesis, again. Acta Analytica, 11:59–77.

  • Dershowitz, N. and Gurevich, Y. (2008). A natural axiomatization of computability and proof of Church's thesis. Bulletin of Symbolic Logic, 14(3):299–350.

• For more on the Church-Turing Computability Thesis, see:
  • Shapiro, Stewart (1983). Remarks on the development of computability. History and Philosophy of Logic, 4(1):203–220.
    • Discusses the notion of computability from a historical perspective, and contains a discussion of Church's thesis.

  • Mendelson, E. (1990). Second thoughts about Church's thesis and mathematical proofs. Journal of Philosophy, 87(5):225–233.

  • Bringsjord, S. (1993). The narrational case against Church's thesis
    • A reply to Mendelson 1990.

  • Folina, J. (1998). Church's thesis: Prelude to a proof. Philosophia Mathematica, 6:302–323.

  • Piccinini, G. (2007). Computationalism, the Church-Turing thesis, and the Church-Turing fallacy. Synthese, 154:97–120.

• Soare 2016, §17.3.3, argues that the Computability Thesis should properly be understood as a "claim with demonstration" and not as a proposition "in need of continual verification".

• Rescorla, M. (2007). Church's thesis and the conceptual analysis of computability. Notre Dame Journal of Formal Logic, 48(2):253–280.
  • Identifies Church's Thesis as the proposition that a number-theoretic function is intuitively computable iff it is recursive.
  • And he identifies Turing's Thesis as the proposition 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.
  • He concludes that Church's Thesis is therefore not the same as Turing's Thesis.

• On representing numbers by strings, see:
  • Shapiro, Stuart C. (1977). Representing numbers in semantic networks: Prolegomena. In Proceedings of the 5th International Joint Conference on Artificial Intelligence, page 284. Morgan Kaufmann, Los Altos, CA.)

• Tharp, L.H. (1975). Which logic is the right logic? Synthese, 31:1–21.
  • Investigates an analogous issue in logic:
    Is our informal or pre-theoretical conception of logic best captured by first-order predicate logic or by some other (more powerful?) logic.

§7.4.5: Insight 5: Implementation:

Physical implementations of computation are discussed in great detail in:

• Piccinini 2015

• Shagrir 2022

§7.5.1: Basic Programs:

• On the comparison of Euclidean impossibility proofs with those in the theory of computation, see:
  • Leach-Krouse, Graham (2016), "Provability, Mechanism, and the Diagonal Problem", in Leon Horsten & Philip Welch (eds.), Gödel's Disjunction: The Scope and Limits of Mathematical Knowledge (Oxford: Oxford University Press):211–240, esp. §9.3 and endnote 33.

• Peano's axioms were originally proposed in:
  • Peano, G. (1889). The principles of arithmetic, presented by a new method. In van Heijenoort, J., editor, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, pages 83–97. Harvard University Press, Cambridge, MA.

  • Dedekind, R. (1890). Letter to Keferstein. In van Heijenoort, J., editor, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, pages 98–103. Harvard University Press, Cambridge, MA. Trans. by Hao Wang and Stefan Bauer-Mengelberg.

• For more on what are also sometimes called the "Dedekind-Peano" axioms, see:
  • Hempel, C.G. (1945). On the nature of mathematical truth. American Mathematical Monthly, 52(10):543–556.

  • Kennedy, H.C. (1968). Giuseppe Peano at the University of Turin. Mathematics Teacher, pages 703–706. Reprinted in Kennedy, Hubert C. (2002), Twelve Articles on Giuseppe Peano (San Francisco: Peremptory Publications): 14–19.

  • Joyce, D. (2005). The Dedekind/Peano axioms.

  • Giuseppe Peano (Wikipedia)

§7.6.2: Recursive Definitions of Recursive Functions:

A good general overview of recursive functions that is pretty consistent with the presentation in this section is:

• Dean, Walter, Recursive Functions, The Stanford Encyclopedia of Philosophy (Summer 2020 Edition), Edward N. Zalta (ed.).

§7.7.1: The Halting Problem:

• For an even simpler outline than the one I give here of the proof of the Halting Problem, see:
  • Brubaker, Ben (2023), "Alan Turing and the Power of Negative Thinking", Quanta Magazine (5 September).

• Chaitin 2006 (and Chaitin, G.J. (2006b, March). The limits of reason. Scientific American, pages 74–81, which is aimed at a more general audience) discusses the Halting Problem, the non-existence of real numbers(!), and the idea that "everything is software, God is a computer programmer, … and the world is … a giant computer"(!!).
  • On the non-"reality" of "real" numbers, see also: Knuth 2001, pp. 174–175.

  

• For more on Hilbert's 10th Problem, see:
  Davis, Martin; & Hersh, Reuben (1973), "Hilbert's 10th Problem", Scientific American 229(5) (September):84–91,136
  

• The Busy Beaver function was first described, and proved to be non-computable, in:
  • Radó, T. (1962, May), On non-computable functions, The Bell System Technical Journal, pages 877–884.
    • This paper is a wonderfully readable introduction to the Busy Beaver "game". §II gives a very simple example, aimed at students, of a Turing Machine, and §§I–III and, especially, §VIII are amusing and well worth reading!

  • For more information, see:
    • Chaitin, G.J. (1987). Computing the busy beaver function. In Cover, T. and Gopinath, B., editors, Open Problems in Communication and Computation, pages 108–112. Springer.

    • Dewdney, A. (1989). The Turing Omnibus: 61 Excursions in Computer Science. Computer Science Press, Rockville, MD, pp. 241–242.

    • Suber, P. (1997). Turing machines II

    • Busy Beaver (Wikipedia)

• On countable and uncountable infinities, see:
  • Countable Set (Wikipedia)

  • Why are there more non-computable functions than computable ones? (StackExchange)

• For more on the difference between a single program that can determine whether any program halts
  and programs that can determine whether a given program halts, see:
  • Cook, B., Podelski, A., and Rybalchenko, A. (2011). Proving program termination. Communications of the ACM, 54(5):88–98.

  • Vardi, M.Y. (2011). Solving the unsolvable. Communications of the ACM, 54(7):5.

  • Ledgard, H. and Vardi, M.Y. (2011). Solved, for all practical purposes. Communications of the ACM, 54(9):7.

• On Gödel Numbering:
  • "Does it hurt to know that any piece of music, however sublime, can be turned into a unique large number?"
    —Richard Powers, Orfeo: A Novel (New York: W.W. Norton, 2014), p. 194.

  • Gödel numbering is actually a bit more complicated than presented in the text.
    • For more information, see:
      • "Gödel Number" (Wolfram MathWorld)

      • "Gödel Numbering" (Wikipedia).

    • For a comparison of it with "Turing numbering", see:
      • Kleene, S.C. (1987). Reflections on Church's thesis. Notre Dame Journal of Formal Logic, 28(4):490–498, especially p. 492.

§7.9: Questions for the Reader

Question 7:
For more information on relative computability, see Soare 2009, Soare 2016, and Homer and Selman 2011