Re: What is an algorithm?

On Thursday, March 27, 2014 9:29:10 AM UTC+1, Nicola wrote:
> In article <76aefd37-be75-4f98-9f55-afed3ddddc9a_at_googlegroups.com>,
>
> vldm10 <vldm10_at_yahoo.com> wrote:
>
>
>
> > 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-
>
> > Turing thesis.
>
>
>
> It would be more appropriate to say that he provides convincing arguments that
>
> the Church-Turing thesis is true. The Church-Turing theory cannot be "proved":
>
> it is not a theorem.

I was on a way, so I could not respond to your post.

Gurevich has one paper that is called "Proving Church's thesis". Y. Gurevich and Nachum Dershowitz have theorems about Church's and Turing's thesis, in their papers. They explained that they use Godel's idea about Church-Turing thesis. Nachum Dershowitz cited the following Godel's idea: "that it might be possible... to state a set of axioms which would embody the generally accepted properties of [effective calculability], and to do something on that basis".

However, as I already wrote I do not believe in Greenvich's general definitions, at all. For example, he defines the state of an algorithm as: "According to the second postulate in the axiomatizations of sequential and synchronous parallel algorithms, the states are (first-order) structures, up to isomorphism." I really can not understand how anyone can implement this definition in the program, which is part of the real world and real business applications.

Regarding the term "effective commutable", as far as I know, in 1936 Church introduced term "effective calculability"; his intention was to introduce finite procedures. However, some mathematicians didn't accept this notation. Godel accepted this term.  

Vladimir Odrljin Received on Sun Apr 06 2014 - 04:28:27 CEST