[FOM] What Is an Agorithm?
Victor Makarov
viktormakarov at hotmail.com
Thu May 1 17:35:08 EDT 2003
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
More information about the FOM
mailing list