Definition of algorithm

[Mttbnchtt]

Currently the definition of algorithm is: "A Directive Information Content Entity that prescribes the inputs and output of mathematical functions as well as workflow of execution for achieving an predefined objective." It contains a typo: an predefined --> a predefined.

Anyway, the biggest issue is that, I think, the definition is wrong, at least the part about mathematical functions. An algorithm does not prescribe inputs or outputs (in some sense of "prescribe", that is the job of the definition of a function). An algorithm is a finite list of commands 1) each of which requires only a finite amount of information and resources (energy, time, paper, etc.) to be carried out and such that 2) the entire process of implementing the algorithm on a given input is deterministic (i.e. every agent that follows the same algorithm and begins with the same input carries out the same operations producing, along the way, the same results in the same order). Note that an algorithmically specified procedure may not terminate, i.e. the output may not exist. For a reference, you can see Soare, Turing Computability pp. 3 ff.

[mark-jensen]

@Mttbnchtt Thanks for the catch on typo.

An algorithm does not prescribe inputs or outputs

Not sure I completely understand your concern. I agree it doesn't prescribe the specifics of the inputs and outputs. But, at the minimum, doesn’t an algorithm generically prescribe the number, order, and formatting of inputs and outputs?

[swartik]

@mark-jensen I think I agree with @Mttbnchtt. Here's a dictionary definition of algorithm (from the OED):

A procedure or set of rules used in calculation and problem-solving; (in later use spec.) a precisely defined set of mathematical or logical operations for the performance of a particular task.

By these lights, CCO's definition seems awfully specific. What is the motivation for referencing mathematical functions? In practice, only a small fraction of algorithms derive from mathematical functions. In particular, mathematical functions are typically considered stateless, whereas algorithms can modify state.

One can infer an algorithm's inputs and outputs from its set of operations, but to my mind the operations are the fundamental aspect of the concept. CCO, with its "as well as workflow" description, demotes that aspect.

[Mttbnchtt]

Hi @mark-jensen. I still think that an algorithm does not prescribe inputs or outputs. The algorithm is a finite list of rules. These rules will typically be applicable to some inputs and not to some others, but that is not stated in the algorithm. The number of inputs that a function takes is also not necessarily mentioned in an algorithm. We could have a function f(x, y) that takes two input and the algorithm that describes how to compute the result may simply be: copy x on the output slot and halt (there is no mention of the second input). An algorithmically specified function may not have an output (for example, the algorithm may cause the computing agent to loop forever).

It is important to notice that an algorithm is not any list of rules. The list must be finite, the rules (individually but not necessarily collectively) must be finitely implementable, and the process must be deterministic. An additional condition that I forgot before (but it is usually required) is that the list must be consistent: i.e. the algorithm cannot ask the agent to do different things in the same situation.

Finally, this is not required to solve our issue, but it is better to say that explicitly: in classical mathematics, not every function is algorithmically specifiable (there are so-called constructive views of mathematics in which every function is algorithmically specifiable, but they are not mainstream math).

[mark-jensen]

Thanks @Mttbnchtt @swartik for your feedback. I agree that use of mathematical function seems too restrictive. Let's work here to improve the definition.

Note: the CCO term in its current state derives from IAO. A search of their tracker finds several stale issues working to refine their definition with no results. Moreover, there is a clear history of struggle amongst experts in computational theory and philosophy to reach agreement on a universal definition for 'algorithm'. Thus, we should be modest in our goal and aim for stepwise improvement.

First draft at revision:
algorithm = "A Directive Information Content Entity that prescribes a finite sequence of deterministic operations that can be automated to achieve an objective."

Please offer suggestions for improvement

[Mttbnchtt]

Hi @mark-jensen. I think the draft is good. I have three observations:

1. Where I can find the definition of "directive information content entity"?
2. Leaving aside more contentious issues (as you rightly suggest), one part of the draft that still needs attention is "to achieve an objective", where "objective" is defined as follows: A Directive Information Content Entity that prescribes some projected state that some Agent intends to achieve.
   In the context of an algorithm, I think most naturally of an objective as being the output of the process prescribed by the algorithm given a specific input. However, the process prescribed by an algorithm may not have an output (e.g.: write 1, delete 1, repeat).
   The definition of objective is more general than output, and one may think that the carrying out of the process on a given input is the objective, regardless of whether the process terminates or not. This is possible, given the above definition of "objective", although unnatural and, in the end, irrelevant to the definition of algorithm.
3. An algorithm is a finite sequence of instructions. However, the sequence of operations that it prescribes may not be finite (see example above).

I am not familiar with the selected vocabulary of CCOs. Is there a way to re-state the following definitions within the CCOs:
algorithm= a finite sequence of instructions each of which can be automated?

[swartik]

@Mttbnchtt, CCO defines "Directive Information Content Entity" as the superclass of Algorithm and Objective, among other classes. Its definition is:

An Information Content Entity that consists of a set of propositions or images (as in the case of a blueprint) that prescribe some Entity.

@mark-jensen, I'm trying to think of how to rewrite the definition to use as many CCO terms as possible. Unfortunately, CCO doesn't include either "instruction" or "operation". In the sense you intend, they are themselves Directive Information Content Entities.

I think "deterministic" is too strict. "Sort the array" is a legitimate step in an algorithm, but it doesn't tell me whether to use a stable sorting algorithm.

So with those concerns in mind, I propose the following revision:

algorithm = "A Directive Information Content Entity that prescribes a finite sequence of operations that can be automated to achieve an Objective."

This should be accompanied by an elucidation explaining what "finite sequence of operations" means.

If you agree I'll be happy to work on the elucidation. (For the record, I'm still pondering whether I prefer "operation" or "instruction".)

[Mttbnchtt]

Thanks @swartik for the clarification. About the definition of algorithm, there are two major problems the revision that is proposed: "A Directive Information Content Entity that prescribes a finite sequence of operations that can be automated to achieve an Objective".

1. What is finite in an algorithm is the list of prescriptions, not of operations (or, at least, it is ambiguous to say that it is). Under some possible reading, the sequence of operations may be infinite, as long as I can specify that using only finitely many orders. This is an example: (a) add 1, (b) repeat. The list of orders is finite (there are two orders). The list of operations that it prescribes is infinite because one would keep adding 1 forever.

2. Implementing an algorithm may not lead to an output. For example, implementing the algorithm above, one keeps adding 1 and never gives a result. In this sense, it is not clear that the algorithm prescribes something "to achieve an Objective".

3. The notion of instruction (order, command, etc.) is really central to the notion of algorithm. I fear that we will not be able to define algorithm properly if do not use the notion of instruction. Is it htat complicated to add it to the ontology?

[swartik]

@Mttbnchtt,

I think agree with you about "operation" vs. "instruction". However, @mark-jensen proposed "operation", and I would like him to weigh in so I can understand his motivation before I commit.

As for whether repeatedly adding 1 doesn't achieve an objective, I'm not so sure. You are right that it has no output. I could therefore say that your algorithm achieves the objective of demonstrating that an algorithm need not have an output. You as the algorithm's creator must have had an objective in mind when you stated the algorithm. That objective has nothing to do with the instructions' effects.

Alternately, CCO might argue, and quite reasonably I think, that "algorithm" in its context is limited to instructions combined to achieve an objective. Of course, that would have to be stated clearly and explicitly.

[Mttbnchtt]

Thanks @swartik. I see that could be reasonable here to concentrate on algorithm given to produce an objective. s for operation vs instruction, I agree that we should hear from @mark-jensen first.

[mark-jensen]

@swartik @Mttbnchtt Thanks for the thoughtful feedback. Apologies for delay in response.

A Directive ICE is (in a sense) an instruction, or composed of instructions, or commands. What it prescribes are operations, i.e., processes. We can drop use of 'operations' to make it more clear. The question is do we want to restrict algorithms to prescribe only computer processes? I think so.

Iterating:

cco:Algorithm =def "A Directive Information Content Entity that prescribes some Computer Program Execution process and contains a finite sequence of unambiguous instructions in order to achieve some Objective."

And yes, having an objective doesn't necessarily imply an output or termination.

[swartik]

@mark-jensen Your definition definitely improves consistency with CCO.

Is Computer Program Execution a proposed class? I can't find it in either the master branch or bfo2020.

[Mttbnchtt]

Thanks Mark. Just seen this. I will reread the discussion. Will reply later today.

…

On Fri, Jan 22, 2021 at 5:10 PM swartik ***@***.***> wrote: @mark-jensen <https://github.com/mark-jensen> Your definition definitely improves consistency with CCO. Is Computer Program Execution a proposed class? I can't find it in either the master branch or bfo2020. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#46 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AIND3OLR4NOEQBIZUHUOEMLS3HZUNANCNFSM4H2RL22A> .

[Mttbnchtt]

Sorry for replying late. I think that Mark's definition of algorithm is ok now. To be sure I should know the definition of Computer Program Execution though. If it implies that the execution is bounded by the energy of the universe or the life of the universe, which may be finite, then I disagree. For example, given a finite amount of time, there are Turing computable functions that will require longer to compute. Or even more simply, a non-terminating algorithm will run forever but it is still an algorithm.

…

On Thu, 28 Jan 2021 at 13:07, Matteo Bianchetti ***@***.***> wrote: Thanks Mark. Just seen this. I will reread the discussion. Will reply later today. On Fri, Jan 22, 2021 at 5:10 PM swartik ***@***.***> wrote: > @mark-jensen <https://github.com/mark-jensen> Your definition definitely > improves consistency with CCO. > > Is Computer Program Execution a proposed class? I can't find it in either > the master branch or bfo2020. > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#46 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AIND3OLR4NOEQBIZUHUOEMLS3HZUNANCNFSM4H2RL22A> > . >

[mark-jensen]

@swartik My mistake. ComputerProgramExecution isn't in Mid-level CCO. I am tempted to amend the def. to be more general, to not restrict only to operations performed by a CPU, but include potential for other types of processes being prescribed by an algorithm.

cco:Algorithm =def "A Directive Information Content Entity that prescribes some Process and contains a finite sequence of unambiguous instructions in order to achieve some Objective.

@Mttbnchtt I think generalizing to a BFO process also would address your concern of an algorithm prescribing a non-terminating process.