Philosophy of Computer Science: Online Resources

Further Readings for Chapter 13:

Implementation

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

§13.1.1: Implementation vs. Abstraction:

• One must be careful in discussing implementation (also called 'realization') as to what exactly gets implemented. E.g., Polger & Shapiro 2023, p. 337 say: "But subtracting details from a description of cognitive processes no more makes them multiply realizable than does subtracting details from a description of water make it multiply realizable."

  But although they are correct to say that water isn't multiply realizable, the description of water minus some details is!

• On multiple realization, see:
  • Ritchie & Piccinini 2018
    
  • Polger & Shapiro 2023.

• Turner 2018

• Durán, J.M. (2020), What is a simulation model?. Minds and Machines, 30:301–323.

• Rapaport, W.J. (2020). Syntax, semantics, and computer programs: Comments on Turner's Computational Artifacts. In Philosophy and Technology, 33:309–321.

§13.2.2: Semantic Interpretation

• For good descriptions of the syntax and semantics of formal systems and their relationship to Turing Machines, see:
  • Haugeland, J. (1981). Semantic engines: An introduction to mind design. In Haugeland, J., editor, Mind Design: Philosophy, Psychology, Artificial Intelligence, pages 1–34. MIT Press, Cambridge, MA.

  • Suber, P. (1997). Formal systems and machines: An isomorphism

• Gödel also identified formal systems with Turing Machines (see §15.2.3).

• And Kripke 2013, p. 80, has advocated for this point of view:
  "[A] computation is a special form of mathematical argument. One is given a set of instructions, and the steps in the computation are supposed to … follow deductively … from the instructions as given. So a computation is just another mathematical deduction … "

• For more on formal systems, see:
  • Kyburg, Jr., H.E. (1968). Philosophy of Science: A Formal Approach. Macmillan, New York, Ch. 1, "The Concept of a Formal System"

• Real examples of formal systems include:
  • propositional logic

  • first-order logic

  • the "MIU" system, in:
    • Hofstadter, D.R. (1979). Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, New York.

  • Peter Suber's system "S" (see also Suber 1997)

  • and my own "mark system" L′, in:
    • Rapaport, W.J. (2017). Semantics as syntax. American Philosophical Association Newsletter on Philosophy and Computers, 17(1):2–11, §2.2

• Sometimes, the entities of such systems are called 'constructive objects'.

• On "marks" and "mark manipulation" systems, see Kearns 1997, §2, pp. 273–274.

§13.2.2.1: Formal Systems:

• In footnote 6, I said that Lego Transformers were "a thought experiment, not a real one!". At the time that I wrote that, it might have been true. Much to my surprise, I saw a Lego Transformer in a toy store in December 2024! You can see one here.

• 
  On the "A Recursive Definition of Understanding" digression, see the discussion of "the analogical practice in science" in Nersessian 2024, esp. pp.10–11.
  

• On representation by bits in a computer, see the discussion of "it from bit" and "bit from it" in Chalmers 2022, Ch. 8.

  Abstract bits (e.g., 0s and 1s) are used to represent physical objects, but physical objects (e.g., voltages) are used to represent abstract bits.

• Originally written in 1993, the 2011 version of Chalmers 2011 was accompanied by commentaries, including:
  • Egan 2012,
  • Rescorla 2012,
  • Scheutz 2012,
  • Shagrir 2012)

  and a reply:

  • Chalmers 2012.

• Chalmers 2011, §2, was published in slightly different form as Chalmers 1994.

• See also:
  • Chalmers, D.J. (1996). Does a rock implement every finite-state automaton? Synthese, 108:309–333

  which is a reply to Putnam's "theorem" that "Every ordinary open system is a realization of every abstract finite automaton" (Putnam 1988, Appendix).

  • Putnam's argument for this "theorem" is related to Searle's 1990 argument about the wall behind me implementing Wordstar (discussed in §9.4.6), but it is much more detailed.

• Chalmers corrects "an error in my arguments" in Chalmers 2012, pp. 236–238.

• On implementation and its relationship to the concept of a virtual machine, see Sloman 2008 and Sloman 2019.

• Ladyman, J. (2009). What does it mean to say that a physical system implements a computation? Theoretical Computer Science, 410(4–5):376–383, esp. p. 379
  • Critiques the kind of relationship that Chalmers sees between his formal and his causal mappings.

• Dresner 2010 examines "the association between numbers and the physical world that is made in measurement" and argues that implementation "and (measurement-theoretic) representation" are "a single relation (or concept) viewed from different angles" (p. 276). Note that "representation" is a semantic concept.

• Shagrir, O. (2012). Computation, implementation, cognition. Minds and Machines, 22(2):137 148.
  • Takes on almost everyone: Arguing that there can be "systems that simultaneously implement different complex automata" (p. 137), he critiques:
    • Putnam 1988,
    • Searle 1990,
    • Chalmers 1996,
    • Scheutz, M. (2001). Computational versus causal complexity. Minds and Machines, 11:543 566,
    • Piccinini, G. (2006). Computation without representation. Philosophical Studies, 137(2):204–241,

• The philosopher and computer scientist Matthias Scheutz has written extensively on implementation; see:
  • Scheutz, M. (1998). Implementation: Computationalism's weak spot. Conceptus Journal of Philosophy, 31(79):229–239.
  • Scheutz, M. (1999). When physical systems realize functions. Minds and Machines, 9:161‐196.
  • Scheutz 2001
  • Scheutz 2012