Re: What is an algorithm?
Date: Sun, 8 Jun 2014 13:45:46 -0700 (PDT)
Message-ID: <fd9b9f62-b1cd-4a13-ac45-95f61fe52e70_at_googlegroups.com>
On Tuesday, April 15, 2014 2:18:39 PM UTC+2, vldm10 wrote:
In this post I would like to summarize the main ideas of my paper, which is
related to algorithms, programs, states and databases. My paper was published at
http://www.dbdesign11.com on 1. April 2012. (Section 7 was published on 10.
April 2014.)
1. In section 7.1 I wrote "Here we will deal with imperative programming
languages". With this sentence I clearly declared that I don't believe in a
universal theory of algorithms. Instead of the universal theory of algorithms, I
presented algorithms from structural programming. So, I presented only one class
of algorithms. This class makes the vast of today's algorithms.
2. Defining an algorithm as a concept, I have introduced a semantic approach to
algorithms.
3. In my solution, each algorithm has a basic discrete "blocks"of which it is
built. For this basic "blocks", I took the basic structures of structural programming. To these structures I added the construction of "assignment".Note that I introduced a new definition of the assignment. All the basic algorithmic blocks mast be precisely and completely defined.
4. In section 7.1 I presented the following definition of a program: "A program
is a mathematical function, which has a clearly defined procedure, domain and
range". As I wrote, this procedure is determined by the corresponding
algorithm, i.e. by 4 algorithmic procedures of structural programming, one
rule and the assignment.
Since I define programs as functions, then these basic algorithmic blocks
become rules" in the corresponding functions. (Note that I did not write that
functions are programs. I wrote that programs are functions.)
5. In 2005 I introduced the theory about states.
So, the above five points define algorithms and programs for the mentioned class of algorithms. I didn't described "start" and "end" of the algorithm because it was done by programmers in the fifties of the twentieth century. The "arrow" in the algorithm means next step.
(a) Y. Gurevich tried to define the algorithm and program in his papers. However, in my opinion, these definitions are not good. The most important thing in his papers is the states of the algorithm. For example, in his important paper "Sequential Abstract State Machines Capture Sequential Algorithms", on page 9, he wrote: "States of A are first order structures". Here " A" is a shortcut for an algorithm. However, the algorithm is not defined. The states are not defined, at all! Later on page 15, he introduced the definition of the algorithm, which is based on the undefined states of the algorithm!?
Please note that A. Tarski introduced structures in Model Theory and the structures are related to the interpretation function.
(b) On page 18 in his mentioned paper, Y. Gurevich defined the program as
follows: A sequential Program P of vocabulary G is just a rule of vocabulary G. My definition of the program is done in section 7.1: A program is mathematical function, which has a clearly defined procedure, domain and range. What is the difference between my definition and Y. Greenwich's definition of the function. The differences are as follows:
(i) I define a program as a function, Gurevich defined a program as a rule.
(ii) I use the definition of a function that is based on a rule. It seems
similar to Greenwich's definition, but it is not. My definition of a program has rules which correspond to the algorithmic structures of the corresponding algorithm. These algorithmic structures are precisely defined in the structural programming. Gurevich rules are undefined terms.
In my post on this user group from 20 January 2008 (see thread "Function") I
explained that the definition of function which is based on "rule" has
drawbacks: "Definition1: A function from A to B is a rule that assigns, to each
member of set A , exactly one member of set B.
Counter - example: In a theater we can imagine a function from the set of
visitors to the set of seats in the theatre. However we can`t say what is the
rule here. This is weak side of Definition1. ..."
(iii) In my approach, programs are instances of algorithms. Algorithms are
concepts, programs are entities. Note that an algorithm sometimes can be just an
idea. V. Gurevich claims that the algorithms are entities. However it is counter-factual with the basics of semantics. A name denotes an entity.
My solution, which combines programs and databases enables determination the future events that are determined by these programs. My solution also provides history of past events that are stored in the database. Received on Sun Jun 08 2014 - 22:45:46 CEST