Re: What is an algorithm?

In article <cdb24099-9b9c-482f-8959-5f60838eb977_at_googlegroups.com>,  Erwin.Smout_at_ikan.be wrote:

> On Thursday, March 27, 2014 9:36:47 AM UTC+1, Nicola wrote:
> > In article <...>,
> >
> > Nicola <...> wrote:
> >
> >
> >
> >
> >
> > > The Church-Turing theory
> >
> >
> >
> > This is "thesis", of course, not "theory".
> >
> > Nicola
> >
> >
> >
>
>
> The following :
>
> http://nanoexplanations.wordpress.com/2011/07/04/a-mathematical-proof-of-the-c
> hurch-turing-thesis/
>
> seems to suggest that a set of axioms was found/conceived/constructed in
> which the thesis became a provable theorem (and indeed a proof was delivered
> too).

Thanks, both the post and the cited paper make a very interesting read. I still believe that it is improper to say that the Church-Turing thesis can be "proved": by axiomatizing the notion of "effective computability", Dershowitz and Gurevich shift the problem to whether _that_ axiomatization captures what is "really" computable. I agree with the quote from Ryan Williams in that post.

I remember reading long time ago about physical theories that would allow an infinite computation to be carried out in a finite amount of time. Would that be possible, our notion of "effective computability" would drastically change. More realistically, probabilistic and quantum computation are good candidates to shake (or reinforce) our beliefs in what is computable. But then, I'm not a philosopher, or a physicist, or an expert in alternative models of computation, so my thoughts are not deep.

In fact, I like database theory because all (or most) objects are finite, yet there is enough complexity to keep me engaged for the time being :)

Nicola

• news://freenews.netfront.net/ - complaints: news_at_netfront.net ---