1. Computational Systems

Computational systems are widespread in everyday life. Their design,
development and analysis are the proper object of study of the
discipline of computer science. The philosophy of computer science
treats them instead as objects of theoretical analysis. Its first aim
is to define such systems, i.e., to develop an ontology of
computational systems. The literature offers two main approaches on
the topic. A first one understands computational systems as defined by
distinct ontologies for software and hardware, usually taken to be
their elementary components. A different approach sees computational
systems as comprising several other elements around the
software-hardware dichotomy: under this second view, computational
systems are defined on the basis of a hierarchy of levels of
abstraction, arranging hardware levels at the bottom of such a
hierarchy and extending upwards to elements of the design and
downwards to include the user. In the following we present these two
approaches.

1.1 Software and Hardware

Usually, computational systems are seen as composed of two
ontologically distinct entities: software and hardware. Algorithms,
source codes, and programs fall in the first category of abstract
entities; microprocessors, hard drives, and computing machines are
concrete, physical entities.

Moor (1978) argues that such a duality is one of the three myths of
computer science, in that the dichotomy software/hardware has a
pragmatic, but not an ontological, significance. Computer programs, as
the set of instructions a computer may execute, can be examined both
at the symbolic level, as encoded instructions, and at the physical
level, as the set of instructions stored in a physical medium. Moor
stresses that no program exists as a pure abstract entity, that is,
without a physical realization (a flash drive, a hard disk on a
server, or even a piece of paper). Early programs were even hardwired
directly and, at the beginning of the computer era, programs consisted
only in patterns of physical levers. By the software/hardware
opposition, one usually identifies software with the symbolic level of
programs, and hardware with the corresponding physical level. The
distinction, however, can be only pragmatically justified in that it
delimits the different tasks of developers. For them, software may be
given by algorithms and the source code implementing them, while
hardware is given by machine code and the microprocessors able to
execute it. By contrast, engineers realizing circuits implementing
hardwired programs may be inclined to call software many physical
parts of a computing machine. In other words, what counts as software
for one professional may count as hardware for another one.

Suber (1988) goes even further, maintaining that hardware is a kind of
software. Software is defined as any pattern that is amenable to being
read and executed: once one realizes that all physical objects display
patterns, one is forced to accept the conclusion that hardware, as a
physical object, is also software. Suber defines a pattern as
“any definite structure, not in the narrow sense that requires
some recurrence, regularity, or symmetry” (1988, 90) and argues
that any such structure can indeed be read and executed: for any
definite pattern to which no meaning is associated, it is always
possible to conceive a syntax and a semantics giving a meaning,
thereby making the pattern an executable program.

Colburn (1999, 2000), while keeping software and hardware apart,
stresses that the former has a dual nature, it is a “concrete
abstraction” as being both abstract and concrete. To define
software, one needs to make reference to both a “medium of
description”, i.e., the language used to express an algorithm,
and a “medium of execution”, namely the circuits composing
the hardware. While software is always concrete in that there is no
software without a concretization in some physical medium, it is
nonetheless abstract, because programmers do not consider the
implementing machines in their activities: they would rather develop a
program executable by any machine. This aspect is called by Colburn
(1999) “enlargement of content” and it defines abstraction
in computer science as an “abstraction of content”:
content is enlarged rather than deleted, as happens with mathematical
abstraction.

Irmak (2012) criticizes the dual nature of software proposed by
Colburn (1999, 2000). He understands an abstract entity as one lacking
spatio-temporal properties, while being concrete means having those
properties. Defining software as a concrete abstraction would
therefore imply for software to have contradictory properties.
Software does have temporal properties: as an object of human
creation, it starts to exist at some time once conceived and
implemented; and it can cease to exist at a certain subsequent time.
Software ceases to exist when all copies are destroyed, their authors
die and nobody else remembers the respective algorithms. As an object
of human creation, software is an artifact. However, software lacks
spatial properties in that it cannot be identified with any concrete
realization of it. Destroying all the physical copies of a given
software would not imply that a particular software ceases to exist,
as stated above, nor, for the very same reason, would deleting all
texts implementing the software algorithms in some high-level
language. Software is thus an abstract entity endowed with temporal
properties. For these reasons, Irmak (2010) defines software as an
abstract artifact.

Duncan (2011) points out that distinguishing software from hardware
requires a finer ontology than the one involving the simple
abstract/concrete dichotomy. Duncan (2017) aims at providing such an
ontology by focusing on Turner’s (2011) notion of specification
as an expression that gives correctness conditions for a program (see
§2).
Duncan (2017) stresses that a program acts also as a specification
for the implementing machine, meaning that a program specifies all
correct behaviors that the machine is required to perform. If the
machine does not act consistently with the program, the machine is
said to malfunction, in the same way a program which is not correct
with respect to its specification is said to be flawed or containing a
bug. Another ontological category necessary to define the distinction
software/hardware is that of artifact, which Duncan (2017) defines as
a physical, spatio-temporal entity, which has been constructed so as
to fulfill some functions and such that there is a community
recognizing the artifact as serving that purpose. That said, software
is defined as a set of instructions encoded in some programming
language which act as specifications for an artifact able to read
those instructions; hardware is defined as an artifact whose function
is to carry out the specified computation.

1.2 The Method of Levels of Abstractions

As shown above, the distinction between software and hardware is not a
sharp one. A different ontological approach to computational systems
relies on the role of abstraction. Abstraction is a crucial element in
computer science, and it takes many different forms. Goguen &
Burstall (1985) describe some of this variety, of which the following
examples are instances. Code can be repeated during programming, by
naming text and a parameter, a practice known as procedural
abstraction. This operation has its formal basis in the abstraction
operation of the lambda calculus (see the entry on the
lambda calculus)
and it allows a formal mechanism known as polymorphism (Hankin 2004).
Another example is typing, typical of functional programming, which
provides an expressive system of representation for the syntactic
constructors of the language. Or else, in object-oriented design,
patterns (Gamma et al. 1994) are abstracted from the common structures
that are found in software systems and used as interfaces between the
implementation of an object and its specification.

All these examples share an underlying methodology in the Levels of
Abstraction (henceforth LoA), used also in mathematics (Mitchelmore
and White 2004) and philosophy (Floridi 2008). Abstractions in
mathematics are piled upon each other in a never-ending search for
more and more abstract concepts. Similarly, abstraction in computer
science is a dynamic, layered, process creating new levels of
abstraction from previous ones (Turner 2021). Consider the case of
abstract data types, which are defined only on the basis of the
operations performed abstracting from the physical properties of any
concrete type. For instance, a list as an abstract type can
be defined by operations such as nil (returning an empty
list), cons (constructing a list), head (returning
the first element), and tail (returning the rest of the
list). Further abstractions performed over lists lead to the creation
of new abstract data types. The permutation function (perm)
between two lists allows the definition of the type bag,
while performing the operations Dup (removing duplicates) and
Ord (removing order), one may obtain the type
finiteset (Turner 2021).

On this account, abstraction is self-contained: an abstract
mathematical object takes its meaning only from the system within
which it is defined and the only constraint is that new objects be
related to each other in a consistent system that can be operated on
without reference to previous or external meanings. Some argue that,
in this respect at least, abstraction in computer science is
fundamentally different from abstraction in mathematics: computational
abstraction must leave behind an implementation trace and this means
that information is hidden but not destroyed (Colburn & Shute
2007). Any details that are ignored at one LoA must not be ignored by
one of the lower LoAs: for example, programmers need not worry about
the precise location in memory associated with a particular variable,
but the virtual machine is required to handle all memory allocations.
This reliance of abstraction on different levels is reflected in the
property of computational systems to depend upon the existence of an
implementation: for example, even though classes hide details of their
methods, they must have implementations. Hence, computational
abstractions preserve both an abstract guise and an
implementation.

A full formulation of LoAs for the ontology of digital computational
systems has been devised in Primiero (2016), including:

• Intention
• Specification
• Algorithm
• High-level programming language instructions
• Assembly/machine code operations
• Execution

Intention is the cognitive act that defines a computational
problem to be solved: it formulates the request to create a
computational process to perform a certain task. Requests of this sort
are usually provided by customers, users, and other stakeholders
involved in a given software development project.
Specification is the formulation of the set of requirements
necessary for solving the computational problem at hand: it concerns
the possibly formal determination of the operations the software must
perform, through the process known as requirements elicitation.
Algorithm expresses the procedure providing a solution to the
proposed computational problem, one which must meet the requirements
of the specification. High-level programming language (such
as C, Java, or Python) instructions constitute the linguistic
implementation of the proposed algorithm, often called the source
code, and they can be understood by trained programmers but cannot be
directly executed by a machine. The instructions coded in high-level
language are compiled, i.e., translated, by a compiler into
assembly code and then assembled in machine code
operations, executable by a processor. Finally, the
execution LoA is the physical level of the running software,
i.e., of the computer architecture executing the instructions.

According to this view, no LoA taken in isolation is able to define
what a computational system is, nor to determine how to distinguish
software from hardware. Computational systems are rather defined by
the whole abstraction hierarchy; each LoA in itself expresses a
semantic level associated with a realization, either linguistic or
physical.

2. Intention and Specification

Intention refers to a cognitive state outside the computational system
which expresses the formulation of a computational problem to be
solved. Specifications describe the functions that the computational
system to be developed must fulfil. Whereas intentions, per
se, do not pose specific philosophical controversies inside the
philosophy of computer science, issues arise in connection with the
definition of what a specification is and its relation with
intentions.

2.1 Intentions

Intentions articulate the criteria to determine whether a
computational system is appropriate (i.e., correct, see
§7),
and therefore it is considered as the first LoA of the computational
system appropriate to that problem. For instance, customers and users
may require a smartphone app able to filter out annoying calls from
call centers; such request constitutes the intention LoA in the
development of a computational system able to perform such a task. In
the software development process of non-naive systems, intentions are
usually gathered by such techniques as brainstorming, surveys,
prototyping, and even focus groups (Clarke and Moreira 1999), aimed at
defining a structured set of the various stakeholders’
intentions. At this LoA, no reference is made to how to solve
the computational problem, but only the description of the problem
that must be solved is provided.

In contemporary literature, intentions have been the object of
philosophical inquiry at least since Anscombe (1963). Philosophers
have investigated “intentions with which” an action is
performed (Davidson 1963), intentions of doing something in the future
(Davidson 1978), and intentional actions (Anscombe 1963, Baier 1970,
Ferrero 2017). Issues arise concerning which of the three kinds of
intention is primary, how they are connected, the relation between
intentions and belief, whether intentions are or presuppose specific
mental states, and whether intentions act as causes of actions (see
the entry on
intention).
More formal problems concern the opportunity for an agent of having
inconsistent intentions and yet being considered rational (Bratman
1987, Duijf et al. 2019).

In their role as the first LoA in the ontology of computational
systems, intentions can certainly be acknowledged as intentions for
the future, in that they express the objective of constructing systems
able to perform some desired computational tasks. Since intentions, as
stated above, confine themselves to the definition of the
computational problem to be solved, without specifying its
computational solution, their ontological and epistemological analysis
does not differ from those referred to in the philosophical
literature. In other words, there is nothing specifically
computational in the intentions defining computational systems which
deserves a separate treatment in the philosophy of computer science.
What matters here is the relation between intention and specification,
in that intentions provide correctness criteria for specifications;
specifications are asked to express how the computational problem put
forward by intentions is to be solved.

2.2 Definitions and Specifications

Consider the example of the call filtering app again; a specification
may require to create a black-list of phone numbers associated with
call centers; to update the list every n days; to check, upon
an incoming call, whether the number is on the black-list; to
communicate to the call management system not to allow the incoming
call in case of an affirmative answer, and to allow the call in case
of negative answer.

The latter is a full-fledged specification, though expressed in a
natural language. Specifications are often advanced in a natural
language to be closer to the stakeaholder’s intentions and only
subsequently they are formalized in a proper formal language.
Specifications may be expressed by means of graphical languages such
as UML (Fowler 2003), or more formal languages such as TPL (Turner
2009a) and VDM (Jones 1990), using predicate logic, or Z (Woodcock and
Davies 1996), focusing on set theory. For instance, Type Predicate
Logic (TPL) expresses the requirements of computational systems using
predicate logic formulas, wherein the type of the quantified variables
is specified. The choice of the variable types allows one to define
specifications at the more appropriate abstraction level. Whether
specifications are expressed in an informal or formal guise often
depends on the development method followed, with formal specifications
usually preferred in the context of formal development methods.
Moreover, formal specifications facilitate verification of correctness
for computational systems (see
§6).

Turner (2018) asks what difference is there between models and
specifications, both of which are extensively used in computer
science. The difference is located in what Turner (2011) calls the
intentional stance: models describe an intended
system to be developed and, in case of a mismatch between the two, the
models are to be refined; specifications prescribe how the
system is to be built so as to comply with the intended functions, and
in case of mismatch it is the system that needs to be refined.
Accordingly, models and specification can be equivalent in their
informational content but differ in their direction of
governance (Turner 2020). Matching between model and system
reflects a correspondence between intentions — describing
what system is to be constructed in terms of the
computational problem the system must be able to solve — and
specifications — determining how the system is to be
constructed, in terms of the set of requirements necessary for solving
the computational problem, as exemplified for the call filtering app.
In Turner’s (2011) words, “something is a specification
when it is given correctness jurisdiction over an artefact”:
specifications provide correctness criteria for computational systems.
Computational systems are thus correct when they comply with their
specifications, that is, when they behave according to them.
Conversely, they provide criteria of malfunctioning
(§7.3):
a computational system malfunctions when it does not behave
consistently with its specifications. Turner (2011) is careful to
notice that such a definition of specifications is an idealization:
specifications are themselves revised in some cases, such as when the
specified computational systems cannot be realized because of physical
laws constraints or cost limitations, or when it turns out that the
advanced specifications are not correct formalizations of the
intentions of clients and users.

More generally, the correctness problem does not only deal with
specifications, but with any two LoAs defining computational systems,
as the next subsection will examine.

2.3 Specifications and Functions

Fully implemented and constructed computational systems are
technical artifacts, i.e., human-made systems designed and
implemented with the explicit aim of fulfilling specific functions
(Kroes 2012). Technical artifacts so defined include tables,
screwdrivers, cars, bridges, or televisions, and they are distinct
both from natural objects (e.g. rocks, cats, or dihydrogen monoxide
molecules), which are not human-made, and artworks, which do not
fulfill functions. As such, the ontology of computational systems
falls under that of technical artifacts (Meijers 2000) characterized
by a duality, as they are defined by both functional
and structural properties (Kroes 2009, see also the entry on
philosophy of technology).
Functional properties specify the functions the artifact is required
to perform; structural properties express the physical properties
through which the artifact can perform them. Consider a screwdriver:
functional properties may include the function of screwing and
unscrewing; structural properties can refer to a piece of metal
capable of being inserted on the head of the screw and a plastic
handle that allows a clockwise and anticlockwise motion. Functions can
be realized in multiple ways by their structural counterparts. For
instance, the function for the screwdriver could well be realized by a
full metal screwdriver, or by an electric screwdriver defined by very
different structural properties.

The layered ontology of computational systems characterized by many
different LoAs seems to extend the dual ontology defining technical
artifacts (Floridi et al. 2015). Turner (2018) argues that
computational systems are still artifacts in the sense of (Kroes 2009,
2012), as each LoA is a functional level for lower LoAs and a
structural level for upper LoAs:

• the intention expresses the functions that the system must achieve
  and is implemented by the specification;
• the specification plays a functional role, explaining in details
  the concrete functions that the software must implement, and it is
  realized by an algorithm, its structural level;
• the algorithm expresses the procedures that the high-level
  language program, its structural level, must implement;
• instructions in high level language define the functional
  properties for the machine language code, which realizes them;
• machine code, finally, expresses the functional properties
  implemented by the execution level, which expresses physical
  structural properties.

It follows, according to Turner (2018), that structural levels need
not be necessarily physical levels, and that the notion of abstract
artifact holds in computer science. For this reason, Turner (2011)
comes to define high-level language programs themselves as technical
artifacts, in that they constitute a structural level implementing
specifications as their functional level (see
§4.2).

A first consequence is that each LoA – expressing what
function to accomplish – can be realized by a multiplicity of
potential structural levels expressing how those functions
are accomplished: an intended functionality can be realized by a
specification in multiple ways; a computational problem expressed by a
specification has solutions by a multiplicity of different algorithms,
which can differ for some important properties but are all equally
valid (see
§3);
an algorithm may be implemented in different programs, each written
in a different high-level programming language, all expressing the
same program if they implement the same algorithm (Angius and
Primiero 2019); source code can be compiled in a multiplicity of
machine languages, adopting different ISAs (Instruction Set
Architectures); executable code can be installed and run on a
multiplicity of machines (provided that these share the same ISA).

A second consequence is that each LoA as a functional level provides
correctness criteria for lower levels (Primiero 2020). Not just at the
implementation level, correctness is required at any LoA from
specification to execution, and the cause of malfunctions may be
located at any LoA not correctly implementing its proper functional
level (see
§7.3
and Fresco, Primiero (2013)). According to Turner (2018), the
specification level can be said to be correct or incorrect with
respect to intentions, despite the difficulty of verifying their
correctness. Correctness of any non-physical layer can be verified
mathematically through formal verification, and the execution physical
level can be verified empirically, through testing
(§6).
Verifying correctness of specifications with respect to
clients’ intentions would require instead having access to the
mental states of the involved agents.

This latter problem relates to the more general one of establishing
how artifacts possess functions, and what it means that structural
properties are related to the intentions of agents. The problem is
well-known also in the philosophy of biology and the cognitive
sciences, and two main theories have been put forward as solutions.
According to the causal theory of function (Cummins 1975),
functions are determined by the physical capacities of artifacts: for
example, the physical ability of the heart of contracting and
expanding determines its function of pumping blood in the circulatory
system. However, this theory faces serious problems when applied to
technical artifacts. First, it prevents defining correctness and
malfunctioning (Kroes 2010): suppose the call filtering app installed
on our smartphone starts banning calls from contacts in our mobile
phonebook; according to the causal theory of function this would be a
new function of the app. Second, the theory does not distinguish
intended functions from side effects (Turner 2011): in case of a
long-lasting call, our smartphone would certainly start heating;
however, this is not a function intended by clients or developers.
According to the intentional theory of function (McLaughlin
2001, Searle 1995), the function fixed by the designer or the user is
the intended one of the artifact, and structural properties of
artifacts are selected so as to be able to fulfill it. This theory is
able to explain correctness and malfunction, as well as to distinguish
side effects from intended functions. However, it does not say where
the function actually resides, whether in the artifact or in the mind
of the agent. In the former case, one is back at the question of how
artifacts possess functions. In the latter case, a further explanation
is needed about how mental states are related to physical properties
of artifacts (Kroes 2010). Turner (2018) holds that the intuitions
behind both the causal and the intentional theories of function are
useful to understand the relation between function and structure in
computational systems, and suggests that the two theories be combined
into a single one. On the one hand, there is no function without
implementation; on the other hand, there is no intention without
clients, developers, and users.

A similar position can be maintained also for natural computational
systems. Following a causal theory, functions are caused by the
structural level and there seems not to be intended or
specified functions. However, natural computational systems
are characterized by multiple specifiability: a physical or
biological structure may implement different functions, i.e. it can be
specified in multiple ways (Fresco et al. 2021). A straightforward
example is a gate implementing either a Boolean conjunction or a
Boolean inclusive disjunction, depending on which voltage ranges are
interpreted as, or labeled with, true and false. Accordingly, while
the function computed by the system remains indeterminate,
the labeling scheme chosen by an agent fixes it
(Curtis-Trudel 2022).

3. Algorithms

Even though known and widely used since antiquity, the problem of
defining what algorithms are is still open (Vardi 2012). The word
“algorithm” originates from the name of the
ninth-century Persian mathematician Abū Jaʿfar
Muḥammad ibn Mūsā al-Khwārizmī, who
provided rules for arithmetic operations using Arabic numerals.
Indeed, the rules one follows to compute basic arithmetic operations
such as multiplication or division, are everyday examples of
algorithms. Other well-known examples include rules to bisect an angle
using compass and straightedge, or Euclid’s algorithm for
calculating the greatest common divisor. Intuitively, an al