Re: What is an algorithm?
Date: Thu, 11 Jun 2015 14:59:27 -0700 (PDT)
Message-ID: <29308cad-27d3-4fb8-a349-4868177da72f_at_googlegroups.com>
The problem of defining the algorithm, I have tried to solve in a different
way than Gurevich. I will mention just a few things that are fundamental.
In my definition of algorithm the main algorithmic structure is a
"sequence". Note that my "sequence" is very different from Gurevich
"sequential algorithm".
In this thread I have already written that in Gurevich's definition of
"sequential algorithm" is not clear what is algorithm. This definition is so
general that also it is not clear what is not "sequential algorithm".
Readers can find the definition of "sequential algorithm" in the following
Gurevich paper: "Sequential State Machines Capture Sequential Algorithms" at
Y. Gurevich home page at MSR.
I will briefly discuss how this paper defined the main term "State". This
concept was introduced under the following axiom:
"4.2 The Abstract State Postulate
Let A be a sequential algorithm.
Postulate 2 (Abstract State)
- States of A are first-order structures. ... "
Here, I'm concentrating only on "states", because it is the most important. The reader can find the details in the above mentioned paper.
"First-order structures" are actually introduced from Model theory. Model
theory is extremely generalized mathematical theory. Therefore, the statement "States of A are first-order structures," is similar to the following sentence "States of A are mathematical structures". That is, this definition has no practical significance. My theory of states is presented in my papers on my site. My Theory of states I explained in detail on this user group. As I wrote Y. Gurevich is good mathematician and he has works that are done in collaboration with famous mathematicians. (look at my thread "The anatomy of plagiarism that was made by authors of "Anchor Modeling", my post on 19 May, 2015. However I will expose here certain matters, which I would call
"unusual".
In addition to the above definition of states of algorithms, Gurevich has the patent that has the name: "State as a first-class citizen of an imperative language". With Gurevich, there are three additional authors of this patent.
What is unusual here is that there are three patents with the same title, the same authors and with different dates. What is surprising is that such an important theoretical results is patented in favor of companies. As far as I understand, these patents were made in favor of Microsoft company.
These patents I have seen at the following address: http://patents.justia.com/inventor/yuri-gurevich
At the beginning of this thread, I have presented Gurevich's definition about states. In this definition, these are states of algorithms.
In my opinion, the algorithms do not have states. In my paper, the programs have states.
In this field about algorithms Y. Gurevich and N. Dershowitz, collaborate in
their papers. However Dershowitz in his paper "Effectiveness" writes:
"States must be comprehensive: they need to incorporate all the relevant
data, when coupled with program..."
Much earlier before this paper I have defined states as a general knowledge
about entities or relationships. Note that the entities and relationships
are much more general categories than algorithms and programs.
Vladimir Odrljin Received on Thu Jun 11 2015 - 23:59:27 CEST