Subject: Computing Functions & Boehm-Jacopini
From: "William J. Rapaport" <rapaport@buffalo.edu>
Date: Thu, 11 Feb 2010 10:55:18 -0500 (EST)

Bill Duncan (wdduncan@buffalo.edu) writes:
"One of the entities I argued for in my hardware/software paper
[Duncan 2009, @
http://www.cse.buffalo.edu/~rapaport/584/whatisacomprog.html#duncan09]
was a "computational function". A function, in [the basic formal
ontology] BFO [see http://www.ifomis.org/bfo], is a realizable entity.
That is, it is an entity which is manifested in an occurrent or process
(i.e., it unfolds in time). For example, a hammer has a function to
drive nails. This function is manifested in the process of driving
nails. My purpose in postulating a "computational function" was to
describe the kinds of entities which inhere in a piece of computing
hardware. That is, the kinds of things a piece of hardware does in
process of computing.

"The Boehm-Jacopini Theorem came to mind. It occurred to me that the
grammar rules required for sequence, selection, and repetition may be
describing functions (in the BFO sense). That is, for example,
sequence is a function (I realize this is an odd way to talk) which is
realized when a program is executed. This idea may also perhaps be
extended to recursive functions and the operations of a Turning
Machine. Any thoughts on this?"

Reply:  
I think you're conflating two distinct (albeit related) notions of
"function". As you use it in "computational function", I think you mean
something like "purpose", whereas as it is used in math and CS, it
means "set of ordered pairs such that no two pairs have the same first
member" (as we discussed in class; see
http://www.cse.buffalo.edu/~rapaport/computation.html )

That said, there may indeed be a connection of some kind, though I
strongly suspect that BFO would categorize them differently. For one
thing, the concept that is formalized in a Turing machine is that of
"algorithm". An algorithm is a procedure for computing (or "processing"
or "manipulating" or "converting", etc.) an input into an output. So
mathematical functions don't "unfold in time", but algorithms do.
Still, algorithms are not "purposes", though they *have* a purpose: An
algorithm is designed for the purpose of solving a particular problem.

========================================================================
Subject: Re: Computing Functions & Boehm-Jacopini
From: "William J. Rapaport" <rapaport@buffalo.edu>
Date: Thu, 11 Feb 2010 10:59:14 -0500 (EST)

Bill Duncan (wdduncan@buffalo.edu) responds to my reply:
'Yes, I am using the term "function" to mean something like "purpose"
as opposed to the mathematical sense of "function". For a full
description of what a "function" is in BFO, here is list of relevant
BFO definitions (see http://jowl.ontologyonline.org/bfo.html):

continuant: An entity that exists in full at any time in which it
exists at all, persists through time while maintaining its identity and
has no temporal parts.

independent continuant: A continuant [snap:Continuant] that is a
bearer of quality and realizable entity entities, in which other
entities inhere and which itself cannot inhere in anything.

dependent continuant: A continuant that is either dependent on one or
other independent continuant bearers or inheres in or is borne by other
entities.

specifically dependent continuant: A continuant that inheres in or is
borne by other entities. Every instance of A requires some specific
instance of B which must always be the same.

realizable: A specifically dependent continuant that inheres in
continuant entities and are not exhibited in full at every time in
which it inheres in an entity or group of entities. The exhibition or
actualization of a realizable entity is a particular manifestation,
functioning or process that occurs under certain circumstances.

function: A realizable entity the manifestation of which is an
essentially end-directed activity of a continuant entity in virtue of
that continuant entity being a specific kind of entity in the kind or
kinds of contexts that it is made for.

'A somewhat subtle point which follows from these definitions is that
functions are non-temporal entities (i.e., functions do not have
temporal parts). If this seems odd, consider (again) the example of a
hammer. It has a function to drive nails. This function inheres in the
hammer even when the hammer is sitting in the tool box. The function,
however, is actualized in the process of driving nails.

'Let me now return to Boehm-Jacopini ... For brevity, I will focus on
the sequence criterion of the theorem. I take this to mean that the
grammatical rules allow for the generation of multiple statements (or
valid strings). For example, the grammar for C allows the generation of
the following statements (separated by the ";"):

int i;
i = 12;
printf("7 + 5 = %i", i);

'In this example, it seems to me there are two senses of "sequence" at
work. One is, of course, the mathematical sense. This is just a list of
statements which can be generated by the grammatical transformation
rules of C. In this sense of "sequence", the actualization of these
statements is not a temporal entity. However, I wonder how this sense
of "sequence" can actually compute anything. Rather, for computation to
occur, these statements have to be carried out (i.e., actualized) in a
temporal process. It is this sense of "sequence" which may tie in with
BFO's sense of "function".

'Lastly, in regards to algorithms, I agree that the execution of an
algorithm unfolds in time. However, I think it may be more on target to
say that an implementation of an algorithm unfolds in time. For
example, an algorithm to sort numbers may or may not be in a form which
is machine executable (or translatable into a form which is machine
executable). That is, whether or not an algorithm is machine
executable, is an accidental property, not a necessary property. I
consider implementations of algorithms which are machine executable to
be computer programs, although I am unsure if all computer programs are
algorithms.'

Rapaport will reply in a later posting. 

========================================================================
Subject: Re: Computing Functions & Boehm-Jacopini
From: "William J. Rapaport" <rapaport@buffalo.edu>
Date: Thu, 11 Feb 2010 14:36:34 -0500 (EST)

Rapaport's reply to Bill Duncan's response to Rapaport's reply to
Duncan's comment about "functions":

Bill Duncan presented a list of definitions of technical terms as used
in the BFO formal ontology. Some of these definitions are hard to
follow (and I know they're not Duncan's definitions, but belong to
BFO): What does it mean to be a "bearer of quality"? What are
"realizable entity entities"? What does it mean for an entity to
"inhere in" another entity? What does it mean for one entity to be
"dependent on" another? What does it mean for one entity to be "borne
by" another? And so on.

The BFO definition of "function" is: "A realizable entity the
manifestation of which is an essentially end-directed activity of a
continuant entity in virtue of that continuant entity being a specific
kind of entity in the kind or kinds of contexts that it is made for."

Independently of what those technical terms mean, it seems that a
function of an entity, according to BFO, is an "end-directed
activity"--i.e., what I earlier called a "purpose"--of that entity.

Then Duncan said:
	the grammar for C allows the generation of the
	following statements (separated by the ";"):

	int i;
	i = 12;
	printf("7 + 5 = %i", i);

	In this example, it seems to me there are two senses of
	"sequence" at work. One is, of course, the mathematical sense.
	This is just a list of statements which can be generated by the
	grammatical transformation rules of C. In this sense of
	"sequence", the actualization of these statements is not a
	temporal entity. However, I wonder how this of sense of
	"sequence" can actually compute anything. Rather, for
	computation to occur, these statements have to be carried out
	(i.e, actualized) in a temporal process. It is this sense of
	"sequence" which may tie in with BFO's sense of "function".

I (Rapaport) agree that a sequence in the sense of a list doesn't
compute anything. The B-J idea of a sequence is one *operation*--or one
*computation*--followed by another. But I don't see how that is a
"function" in the sense of a "purpose". I do see how such a sequence of
computations can *have* a function, i.e., can *have* a purpose.

Later, Duncan says:
"I agree that the execution of an algorithm unfolds in time. However, I
think it may be more on target to say that an implementation of an
algorithm unfolds in time. For example, an algorithm to sort numbers
may or may not be in a form which is machine executable (or
translatable into a form which is machine executable). That is, whether
or not an algorithm is machine executable is an accidental property,
not a necessary property. I consider implementations of algorithms
which are machine executable to be computer programs, although I am
unsure if all computer programs are algorithms."

Here, Duncan is correctly distinguishing between an algorithm
considered as a textual statement describing a procedure and an
algorithm as the procedure actually being carried out. I agree that
this is an important distinction, but I don't quite see how it's
connected to the two senses of "function". (Later, we'll be reading a
paper by James H. Fetzer that makes a similar distinction, although
many people make a 3-way distinction: between an abstract *algorithm*,
its implementation as a computer *program* written in a particular
programming language, and the implementation of that program as a
running *process* on a particular computer.)

========================================================================

Discussion continued at:
http://www.cse.buffalo.edu/~rapaport/584/S10/EMAIL/20100216-CompgFns-Boehm-Jacopini.txt