What is an algorithm?
Date: Wed, 26 Mar 2014 03:47:18 -0700 (PDT)
Message-ID: <76aefd37-be75-4f98-9f55-afed3ddddc9a_at_googlegroups.com>
I found on the Web papers that are trying to give a definition of the algorithm. The papers are from Yuri Gurevich, Microsoft Research. Roughly speaking Y. Gurevich is working on the definition of the algorithm. He proved the Church- thesis.
Since this is the group for database theory, I will roughly present basic ideas of these works:
- In 1933 Godel developed ideas of computability and recursive function.
- In 1936 A. Church introduced his thesis. Church's student Kleene determined extended version that all effectively computable partial functions are recursive.
- In 1936 A. Turing introduced "Turing Machines". Turing thesis is that any effectively computable function is Turing computable.
- In 1953 Andrey Kolmogorov analyzed just algorithms. He determined that every algorithm has the following characteristics: Sequentially, Elementary steps and Locality. (This is Y. Gurevich terminology).
- Church-Turing thesis determines that if a function is effectively calculable,
then the same calculation can also be carried out by a Turing machine as well
as by a recursively definable function, and by lambda-function.
In fact Church-Turing thesis states that all three computation processes are
equivalent. This is thesis and it is not theorem, because the main term
"computable" is intuitive.
In Gurevich`s paper "Foundational analyses of computation", on page 13, I found the following text: "Note that, according to the sequential-time constraint, the next state TA(X) of an algorithm A depends only on the current state X of A. The executor does not need to remember any history (even the current position in the program); all that is reflected in the state. " As far as I know, I am the only one who wrote about history of algorithms. To be precise, I wrote about the history of events in the algorithmic process. It is done in my paper "Semantic databases and semantic machines" and presented on the user group. If Y. Gurevich is referring to my paper, then I have to say that he does not understand the "history". In my paper, "history" does not specify the execution of an algorithm or program. History is related to database theory. In my paper the algorithm is precisely determined by the structures of structural programming. Note also that we do not need to speak about one algorithm, as it is the case with Gurevich's theoretical approach related to the algorithms. We can speak about sets of algorithms. For example OS Windows has thousands of programs. These programs can be interconnected to establish interactions with one another. So we can speak about Entity/Relationship model for programs. Note also that it can be a single computer with multiple operating systems. This Gurevich criticism was the main reason that I post this response. But let me give some other reasons for this post. As I said before, Gurevich is trying to define the algorithm. When we have a definition of the algorithm, we can accurately determine what is "computability" and then prove Church-Turing thesis. Gurevich's papers are related to aforementioned mathematicians. It is well known that Church, Godel, Turing and Kolmogorov belong to the group of the best mathematicians of 20 century. They have done pioneering work in era when there were no computers. But today's computer science needs better theoretical results. Fifty years ago R. Montague wrote: "Discussion of Church's thesis has suffered for luck of precise general framework within which it could be conducted." It seems to me that Gurevich work is ambiguous and vague. He uses the notations and definitions that are too broad. For example, he defines state as follows: "The states of a computational sequence can be arbitrary first-order structures."
In contrast to Gurevich`s definition, my definition of state is very accurate and complete. It determines the identification of both: the entity and states of the entity. It includes structural knowledge which is decomposed on the corresponding atomic structures, etc. I usually use knowledge about the entity, knowledge about its attributes and knowledge about its data. However, to these structures of knowledge, I can add any other structure of knowledge. In this way, a construction of knowledge is flexible. The attributes, entities, relationships and states are represented with concepts. I use Frege's definition of the concept with the addition of my procedures for identification.
In his last two papers, Gurevich begins to change the basics of his theory of algorithms. In his last two papers "Foundational analysis of computation" and "Semantics-to-syntax analyses of algorithm" Gurevich changes some of his basic assumptions about algorithms. Semantics now start to affects fundamental nature of algorithms. Now, the world "semantics" appears in the title of the paper. He also introduced term "species of algorithms" to mean a class of algorithms. However in his previous papers, he writes in terms of general algorithms. Note also that definitions of these terms already exist in my papers.
1.
In my paper "Semantic databases and semantic machines", presented at
http://www.dbdesign11.com I wrote in section 7 the following: "Here we will deal
with imperative programming languages." With this sentence I determined one
class of algorithms. Here I concentrated on algorithms that belong to so-called
structural programming. Here I have made clear distance from "classical"
approach to algorithms. As I already mentioned classical approach is based on
intuitive (undefined) term of computation. The classical approach tries to
define some kind of general theory for algorithms. My approach here is related
to one specific kind of algorithms. This kind of algorithms (and the
corresponding programming languages), in my opinion can be built as theory. So
the term "species of algorithms" is not about terminology. It is about
fundamentals of algorithms and I did it in my paper. It is about the following:
Do you believe that there is a general theory of algorithms covering all the
algorithms? Or you do not believe that there is such a general theory.
2.
In the paper "Semantics-to-syntax analyses of algorithms" Gurevich tries to
introduce some semantics. Note that in my paper, I have already fully introduced
semantics. I use semantic approach. I do not use Axioms. As far as I understand
the math, the main application of the axioms is in a proof.
In my paper "Semantic databases and semantic machines", section 7.2, I defined algorithm as a concept and I introduced the program that satisfy the algorithm, as the corresponding entity.
In my opinion Gurevich has some mistakes related to basics things in semantic. For example, he determined algorithm as an entity. In my opinion this is serious mistake.
3.
In my data model I have only two kinds of events that are related to changes of
states of entities and relationships. In my paper "Some ideas about a new Data
Model" from 2005, posted at http://www.dbdesign10.com , section 1, I wrote
about these two events:
There are only two kinds of events in the real world:
(i) An event which causes new information
(ii) An event which causes some existing information to not be valid after this
event.
Only these two events can change the state of an entity. Obviously, only the assignment of a value to a variable can change a state of an entity. In my paper "Semantic databases and semantic machines", section 7.3, I defined assignments as only atomic command in the programming languages. I also defined assignment of value to a variable as the binding of names. As far as I now this is a new definition for assignment.
In his paper "Foundational Analyses of computation", section 5.1, Gurevic changed his definition of states and gives a whole new meaning to the change of states of algorithm. He wrote: " the states can be faithfully represented by first-order structures of a fixed vocabulary in such a way that transitions become just set of assignments."
Vladimir Odrljin Received on Wed Mar 26 2014 - 11:47:18 CET