[FOM] What Is an Agorithm?

[Victor Makarov]

An answer to this question was given recently by Yiannis Moschovakis in his 
paper"What is an algorithm?"[3] - "algorithms are definable recursors". 
Another answer was given by Yuri Gurevich in [2] - a sequential algorithm is 
an Abstract State Machine (states are first-order structures).

However, I am not completely satisfied with these answers, because before 
writing an algorithm we must already know objects (numbers, strings, graphs, 
...) the algorithm is working with. But what does mean "know objects" in 
mathematical terms? It means that we must have an axiomatic theory of these 
objects (that is, the Number Theory, the Theory of Finite Sequences, the 
Graph Theory, ...). Never an algorithm is working with "entirely arbitrary 
objects".

I am trying to elaborate this idea in my forthcoming paper "Predicate Logic 
with Definitions and the General Concept of Algorithm" - see an extended 
abstract of this paper at my Web page (under #7):

http://home.nyu.edu/~yvm204/vm/vm.htm

The beginning of the paper is also below:

0. Introduction

Development of more general (and more suitable for applications) precise 
concepts of algorithm is important both for mathematics and computer science 
[1, 2, 3]. In [4] the following concept of abstract algorithm was suggested:
   Any algorithm is defined in a certain mathematical theory (for example, 
graph algorithms in the graph theory). That is, the concept of algorithm is 
inseparable from the concept of mathematical theory and actually is 
subordinate to it because before the development of an algorithm we should 
have a mathematical theory. An algorithm is a definition (of some special 
kind) in this theory.
   The aim of this paper is to suggest a new (more precise and simple 
comparing to the author’s previous papers [4, 5]) practical formalism – 
Predicate Logic with Definitions (or D-logic or simply DL) – for defining 
mathematical theories and writing definitions inside the theories. DL is a 
modification of the first-order logic by adding to its main syntactic 
constructs – terms and formulas – a new syntactic construct, called 
definition. As an example, we show that the abstract state machines of 
Gurevich[2] can be naturally represented in DL.

    1. Mathematical theories

   To make the concept of abstract algorithm precise, we at first should 
have a precise definition of the concept “mathematical theory”. Fortunately, 
the last century’s work on the foundations of mathematics has provided such 
a definition [6, p. 215], accepted by the most of mathematicians:
   A mathematical theory T is an extension of the first-order theory ZFC 
(Zermelo-Fraenkel set theory with the axiom of choice) by adding to ZFC a 
finite number of new constants c1, … , ck and an axiom A, implicitly 
defining these constants.
   In DL, the theory T can be defined in the following way:
                              T := def[c1, …ck; A];
The name of the theory T must be an unique identifier, the constant names 
c1, …,ck are identifiers or operators (an operator is a finite sequence of 
such symbols as +, -, *,&, … ).
   Let z be any tuple (z1, …, zk) where z1, …, zk are some terms, and the 
formula A1 is the result of substitution in the formula A the terms z1, …, 
zk instead of the constants c1, …ck , respectively. The tuple z is called a 
model of the theory T if the formula A1 is a theorem (note that this 
definition differs from the definition of model in the model theory).
  The formula A1 can be written in DL as Subst(A, T, z) where Subst is a 
standard symbol of DL and appropriate axioms for substitution are provided 
in D-logic.
   The statement “z is a model of the theory T” (which can be expressed by 
the formula A1) can also be written is DL as “z in T”. The statement “the 
theory T is consistent” can be written as “E[T]”. Note that the formula “z 
in T -> E[T]” is a theorem of D-logic.

The formula E[T] can be translated into the classical first-order logic as 
Ey1 …EykA1 where y1, …,yk are new variable names and A1 = Subst(A, T, (y1, 
…,yk) ).

References

[1] A.N. Kolmogorov and V.A. Uspenski. On the definition of algorithm. 
Uspekhi Mat. Nauk, 13 (1958), 3-28 (Russian).
[2] Yuri Gurevich. Sequential Abstract State Machines Capture Sequential 
Algorithms. ACM Transactions on Computational Logic, vol. 1, no. 1 (July 
2000), pp. 77-111.  Also:
http://research.microsoft.com/~gurevich/Opera/141.pdf
[3] Yannis N. Moschovakis. What Is an Algorithm? Mathematics Unlimited – 
2001 and beyond, ed. by B. Engquist and W. Schmid, Springer, 2001, pp. 
919-936. Also see:
http://www.math.ucla.edu/~ynm/papers.htm.
[4] Victor Makarov. Towards a theory of abstract algorithms. 
Nauchno-Technicheskaya Informatsiya, ser. 2, 1982, N9, pp. 35-40 (Russian). 
Also see:
http://home.nyu.edu/~yvm204/vm/vm.htm
[5] Victor Makarov. MSL – A Mathematical Specification Language, in:  
“Logical Foundations of Computer Science – Tver’92”, Lecture Notes in 
Computer Science, Vol. 620 (1992), pp. 305-313.
[6] Dieudonne J.A. A Panorama of Pure Mathematics. New York: Academic Press, 
1982.


The URL address of the paper is:

http://home.nyu.edu/~yvm204/vm/DL-alg.htm

I would be very grateful for any comments.
Thanks in advance,
Victor Makarov, Brooklyn (NY)







_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online  
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963