Re: What is an algorithm?
Date: Tue, 15 Apr 2014 05:18:39 -0700 (PDT)
Message-ID: <abca8ac6-8bef-49ed-9a5c-5739fd7b7ca5_at_googlegroups.com>
On Wednesday, March 26, 2014 11:47:18 AM UTC+1, vldm10 wrote:
>
> 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.
With regard to this Y. Gurevich's text it turns out that it looks, like I do not
know what I am doing.
Now I will briefly explain my approach to algorithms, using an example. As we
know for a formal theory (formal system), we need the following: a finite set of
symbols (alphabet), a set of axioms, and a set of inference rules. While I was a
student, one of my professors presented the following example of a formal theory
(system):
1. There is only one symbol in this theory. It is the following symbol: a. 2. There is only one axiom in this theory. It is the following axiom: a. 3. There is only one rule in this theory. It is the following rule: F ----- , ( F is a formula in the theory)Faa
Now, for example, we can prove that aaaaa is a theorem. Proof :
a (because "a" is the given axiom), aaa (by applying of the given inference rule), aaaaa (by applying of the inference rule). Note that this is only possible proof.
We can prove the following meta-sentence: "F is theorem iff the number of occurrences of a in the corresponding formula is odd". So we can notice that the theory is decidable.
We can choose the following interpretation: " Formula aaaa...a is understood as a natural number, that corresponds to the number of occurrences of a in the formula.
Note that we work only with finite programs. If one wants to consider this example as an infinite case then he can apply Mathematical induction.
In my paper "Semantic databases and semantic machines", section 7.5 at http://www.dbdesign11.com , I introduced a certain formal system for structural programming, with defined alphabet, set S, and one inference rule.
In this system, each step in the construction of the algorithm is completely defined. As I mentioned in my paper, these structures are from "Structural Programming". They are applied in real practice, today, in more than 90% of programs and business applications. So my solution is related to the vast amount of real-life solutions. In Y. Gurevich papers I didn't notice steps in algorithms. There are only states which are totally generalized in some general language. It seems to me that Y. Gurevich not differ steps and states.
One can ask what we can prove in my formal system. What is the purpose of this formal system? In this formal system I can prove that every algorithm in structural programming is sequence.
Why the sequence is important? As I already wrote in my paper (see section 7.6) the sequence retain and keep inheritance in programs (algorithms) that have changes. In real life companies have huge programs which are important and which are enormous. Sometimes a program can have more than 500 pages. Make changes in this type of programs is very difficult, sometimes it is impossible. Sometimes, one must do a new application and throw all the money and work that is spent for the existing application that was built and repaired for years. The formal system which was introduced in my paper completely support changes in logic on formal way. It enables to keep (inherit) some blocks of the existing logic, change some blocks of the logic and add new blocks of a logic - in formal way. In my opinion this philosophy of changes and preservation of hereditary traits in logic of programs and algorithms is similar to the philosophy of changes and preservation of hereditary traits in human DNA.
The above example and this formal system for algorithms show that formal systems, steps of an algorithm, proofs, effective calculability, and decidability are interrelated things.
On the other hand we have "history", which can be applied when we need "history". Note that the database solution enables some useful things. For example, it can execute "history" which is determined beforehand (many times). A database also can contain many "histories". My database solution is event oriented rather than time oriented. Thus, with respect to the Y. Gurevich's text at the beginning of this message, I am not sure that he understand the role of "history" in algorithms.
Vladimir Odrljin Received on Tue Apr 15 2014 - 14:18:39 CEST