What Is a Computer Program?

(Humorous?) Definition of "Program"

What Is a Programming Language?

What Is Implementation?

1. 
   Lycan, William G. (1987), "The Continuity of Levels of Nature", in William G. Lycan (ed.), Mind and Cognition: A Reader (Basil Blackwell): 77–96; excerpted from Chs. 4–5 of William G. Lycan, Consciousness (Cambridge, MA: MIT Press, 1987).
   • "…‘software’/‘hardware’ talk encourages the idea of a bipartite Nature, divided into two levels, roughly the physiochemical and the (supervenient) ‘functional’ or higher-organizational—as against reality, which is a multiple hierarchy of levels of nature…. See Nature as hierarchically organized in this way, and the ‘function’/‘structure’ distinction goes relative: something is a role as opposed to an occupant, a functional state as opposed to a realizer, or vice versa, only modulo a designated level of nature."

2. Chalmers, David J. (1993a), "A Computational Foundation for the Study of Cognition" (unpublished).
   • §2 was published (in slightly different form) as "On Implementing a Computation", Minds and Machines 4 (1994): 391-402.

3. Chalmers, David J. (1993b), "Does a Rock Implement Every Finite-State Automaton?", Synthese 108 (1996): 309-333.
   • This is a reply to an argument similar to Searle's (1990) argument about the wall behind me implementing Wordstar, but much more detailed, due to Hilary Putnam:
     Putnam, Hilary (1988), Appendix to Representation and Reality (Cambridge, MA: MIT Press): 121-125.
     • "Theorem. Every ordinary open system is a realization of every abstract finite automaton."

4. Suber, Peter (1997), "Formal Systems and Machines: An Isomorphism".
   Also see:
   • Suber, Peter (2002), "Sample Formal System S"

5. Rapaport, William J. (1999), "Implementation Is Semantic Interpretation" [PDF], The Monist 82 (1): 109-130.
   • This article was based on a longer chapter (which it alludes to as "in preparation"), which has since been published as:
     Rapaport, William J. (2005), "Implementation Is Semantic Interpretation: Further Thoughts", Special Issue on Theoretical Cognitive Science, Journal of Experimental and Theoretical Artificial Intelligence 17(4) (December): 385-417.

6. 
   Scheutz, Matthias (1999), "When Physical Systems Realize Functions", Minds and Machines 9: 161–196.
   • To refute Putnam 1988, Scheutz replaces the notion of "implementation of a computation" with "realization of a function". His view is not inconsistent with my "semantic" theory (Rapaport 1999), at least when Scheutz says: "what is the same [in the case of two realizations] is the syntactic structure of…the function"; i.e., they are different semantic interpretations of the same syntactic structure.

7. Dresner, Eli (2010), "Measurement-Theoretic Representation and Computation-Theoretic Realization", Journal of Philosophy 108(6) (June): 275–292.
   • Presents a theory of "realization" (= implementation) that equates it to representation more generally, not unlike the way I identify implementation with semantic interpretation.

Are Programs Theories?

1. Simon, Herbert A. & Newell, Allen (1956), "Models: Their Uses and Limitations", in Leonard D. White (ed.), The State of the Social Sciences (Chicago: University of Chicago Press): 66-83.

2. The clearest statement of the idea can be found in:
   • Simon, Herbert A., & Newell, Allen (1962), "Simulation of Human Thinking", in Martin Greenberger (ed.), Computers and the World of the Future (Cambridge, MA: MIT Press): 94-114
     • "1. Computers are quite general symbol-manipulating devices that can be programmed to perform nonnumerical as well as numerical symbol manipulation.
       "2. Computer programs can be written that use nonnumerical symbol manipulating processes to perform tasks which, in humans, require thinking and learning.
       "3. These programs can be regarded as theories, in a completely literal sense, of the corresponding human processes. These theories are testable in a number of ways: among them, by comparing the symbolic behavior of a computer so programmed with the symbolic behavior of a human subject when both are performing the same problem-solving or thinking tasks." (p.97)

   • Miller, George (1962), Comments in the "Panel Discussion" on Simon & Newell 1962, in Martin Greenberger (ed.), Computers and the World of the Future (Cambridge, MA: MIT Press): 118-121
     • In these comments, Miller lists "alternative" languages for expressing theories: natural language, calculus, symbolic logic, and probability, and concludes that computer programs are more natural for psychology than any of these.

3. Weizenbaum, Joseph (1976), Computer Power and Human Reason: From Judgment to Calculation (New York: W.H. Freeman).
   • Ch. 5 ("Theories and Models"), pp. 132-153.
   • Ch. 6 ("Computer Models in Psychology"), pp. 154-181.
   • Complete PDF version of the above two chapters (not missing any pages that we know of!)
   • Original PDF version of the above two chapters, which is missing two pages (see below).
     • Missing pages 138-139!
     • Missing pages 142-143!!

4. Moor, James H. (1978), "Three Myths of Computer Science" British Journal for the Philosophy of Science 29(3) (September): 213-222.

5. Johnson-Laird, Philip N. (1981), "Mental Models in Cognitive Science", in Donald A. Norman (ed.), Perspectives on Cognitive Science (Norwood, NJ: Ablex), Ch. 7 (pp. 147-191):
   • "Computer programming is too useful to cognitive science to be left solely in the hands of the artificial intelligenzia [sic]. There is a well established list of advantages that programs bring to a theorist: they concentrate the mind marvelously; they transform mysticism into information processing, forcing the theorist to make intuitions explicit and to translate vague terminology into concrete proposals; they provide a secure test of the consistency of a theory and thereby allow complicated interactive components to be safely assembled; they are "working models" whose behavior can be directly compared with human performance. Yet, many research workers look on the idea of developing their theories in the form of computer programs with considerable suspicion. The reason...[i]n part...derives from the fact that any large-scale program intended to model cognition inevitably incorporates components that lack psychological plausibility.... The remedy...is not to abandon computer programs, but to make a clear distinction between a program and the theory that it is intended to model. For a cognitive scientist, the single most important virtue of programming should come...from the business of developing [the program]. Indeed, the aim should be neither to simulate human behavior...nor to exercise artificial intelligence, but to force the theorist to think again." (pp. 185-186.)

6. Thagard, Paul (1984), "Computer Programs as Psychological Theories", in O. Neumaier (ed.), Mind, Language, and Society (Vienna: Conceptus-Studien): 77-84.
   • A critique of the whole idea.

7. Pylyshyn, Zenon W. (1984), Computation and Cognition: Toward a Foundation for Cognitive Science (Cambridge, MA: MIT Press), Ch. 3 ("The Relevance of Computation"), pp. 48-86, esp. the section "The Role of Computer Implementation" (pp. 74-78):
   • "[T]he...requirement—that we be able to implement [a cognitive] process in terms of an actual, running program that exhibits tokens of the behaviors in question, under the appropriate circumstances—has far-reaching consequences. One of the clearest advantages of expressing a cognitive-process model in the form of a computer program is, it provides a remarkable intellectual prosthetic for dealing with complexity and for exploring both the entailments of a large set of proposed principles and their interactions." (p. 76.)

8. Johnson-Laird, Philip N. (1988), The Computer and the Mind: An Introduction to Cognitive Science (Cambridge, MA: Harvard University Press), Ch. 3 ("Computability and Mental Processes"), pp. 37-53:
   • "[T]heories of mind should be expressed in a form that can be modelled in a computer program. A theory may fail to satisfy this criterion for several reasons: it may be radically incomplete; it may rely on a process that is not computable; it may be inconsistent, incoherent, or, like a mystical doctrine, take so much for granted that it is understood only by it adherents. These flaws are not always so obvious. Students of the mind do not always know that they do not know what they are talking about. The surest way to find out is to try to devise a computer program that models the theory." (p. 52.)

9. Partridge, Derek; & Wilks, Yorick (eds.) (1990), The Foundations of Artificial Intelligence: A Sourcebook (Cambridge, UK: Cambridge University Press).
   • Lockwood & SEL: Q335 .F68 1990
   Especially the following two sections, containing the articles listed (many of which are available elsewhere, some online):
   • §3 ("Levels of Theory", pp. 95-118), containing:
     1. Marr, David (1977), "Artificial Intelligence: A Personal View", pp. 97-107; reprinted from Artificial Intelligence 9: 37-48.

     2. Boden, Margaret A., "Has AI Helped Psychology?", pp. 108-111.

     3. Partridge, Derek, "What's in an AI Program?", pp. 112-118.

   • §4 ("Programs and Theories", pp. 119-164), containing:
     1. Wilks, Yorick, "One Small Head: Models and Theories", pp. 121-134.
        • Online in slightly different form as:
          Wilks, Yorick (1974), "One Small Head—Models and Theories in Linguistics", Foundations of Language 11(1) (January): 77–95.

     2. Bundy, Alan; & Ohlsson, Stellan (198?), "The Nature of AI Principles", pp. 135-154; reprinted from AISB Quarterly ##47-50.

     3. Simon, Thomas W., "Artificial Methodology Meets Philosophy", pp. 155-164.

10. Daubert v. Merrell Dow Pharmaceuticals (92-102), 509 U.S. 579 (1993).
    • A Supreme Court case concerning what counts as "generally accepted" reliability by the scientific community. Prof. Srihari (personal communication) wonders if certain computer programs would pass muster.

11. Simon, Herbert A. (1996), The Sciences of the Artificial, Third Edition (Cambridge, MA: MIT Press), Ch. 1 ("Understanding the Natural and Artificial Worlds"), pp. 1-24 [PDF].
    • Originally written in 1969, updated in 1981.

12. Scheutz, Matthias; & Peschl, Markus (2000), "Some Thoughts on Computation and Simulation in Cognitive Science" [PDF], in Proceedings of the 6th Congress of the Austrian Philosophical Society: 534-540.

13. Winsberg, Eric (2001), "Simulations, Models, and Theories: Complex Physical Systems and Their Representations", Proceedings of the 2000 Biennial Meeting of the Philosophy of Science Association, Part I: Contributed Papers, Philosophy of Science 68(3) (September) Supplement: S442-S454.

14. Coward, L. Andrew; & Sun, Ron (2001??), "Some Criteria for an Effective Scientific Theory of Consciousness and Examples of Preliminary Attempts at Such a Theory" [PDF].

15. Peschl, Markus F.; & Scheutz, Matthias (2001), "Explicating the Epistemological Role of Simulation in the Development of Theories of Cognition" [PDF], in Proceedings of the 7th Colloquium on Cognitive Science (ICCS-01): 274-280.

16. Lane, Peter C.R.; & Gobet, Fernand (2003), "Developing Reproducible and Comprehensible Computational Models" [PDF], Artificial Intelligence 144: 251-263.

17. Humphreys, Paul (2002), "Computational Models", Philosophy of Science 69 (September): S1-S11.

18. Green, Christopher D. (2004), "(How) Do Connectionist Networks Model Cognition?" (forthcoming and unpublished Ph.D. dissertation, Dept. of Philosophy, University of Toronto), Ch. 3 ("Philosophical Approaches to Explanation and Scientific Models, and Their Relations to Connectionist Cognitive Science") [.doc].

19. Shieh, David (interviewer) (2009), "The Trouble with Computer Simulations: Linked in with Sherry Turkle", Chronicle of Higher Education (March 27): A14.
    • "Computer simulations have introduced some strange problems into reality."

20. Simonite, Tom (2009, August), "Soap Bubbles to Take the Drag out of Future Cars", New Scientist
    • Despite the increasing sophistication of computer simulations, finding ways to show complex air flows visually is critical to understanding aerodynamics, says Alex Liberzon at Tel Aviv University in Israel, and new ways to do that in large wind tunnels are valuable. "You cannot solve everything completely in space and time on a computer," Liberzon told New Scientist. "Simulations do not capture the full complexity of wakes and other features, which can exhibit large changes in behaviour caused by very small changes."

21. Turner, Raymond (2010?), "Programming Languages as Mathematical Theories" [PDF]
    • "That computer science is somehow a mathematical activity was a view held by many of the pioneers of the subject, especially those who were concerned with its foundations. At face value it might mean that the actual activity of programming is a mathematical one. Indeed, at least in some form, this has been held. But here we explore a different gloss on it. We explore the claim that programming languages are (semantically) mathematical theories. This will force us to discuss the normative nature of semantics, the nature of mathematical theories, the role of theoretical computer science and the relationship between semantic theory and language design."

1. Moor, James H. (1978), "Three Myths of Computer Science" British Journal for the Philosophy of Science 29(3) (September): 213-222.
   • Moor discusses different "levels" from which to understand things like computers and programs; this notion is reminiscent of Dennett's 1971 theory of "stances":

     Dennett, Daniel C. (1971), "Intentional Systems", Journal of Philosophy 68: 87-106; reprinted in Daniel C. Dennett, Brainstorms (Montgomery, VT: Bradford Books): 3-22.

     • For some interesting followups to Dennett's paper, see:
       Miller, Christopher A. (guest ed.) (2004), "Human-Computer Etiquette: Managing Expectations with Intentional Agents", Communications of the ACM 47(4) (April): 31-34.

2. Suber, Peter (1988), "What Is Software?", Journal of Speculative Philosophy 2(2): 89-119.

3. Colburn, Timothy R. (1999), "Software, Abstraction, and Ontology", The Monist 82 (1): 3-19.
   • Reprinted (in slightly different form) as:
     Colburn, Timothy R. (2000), Philosophy and Computer Science (Armonk, NY: M.E. Sharpe), Ch. 12 ("Software, Abstraction, and Ontology"), pp. 198-209.

   • On the case of the exportable software text and its non-exportable hardware implementation, see:
     Wallich, Paul (1997), "Cracking the U.S. Code", Scientific American (April): 42.

   • On the various theories that Colburn discusses concerning the mind-body problem, see: Roderick Chisholm's cartoon

4. Duncan, William (2009), "Making Ontological Sense of Hardware and Software".
   • An essay by a former student of this course arguing that both Moor and Suber are wrong about the nature of the hardware-software distinction, and that an analysis based on the formal ontology BFO can clarify matters.