Re: Is "infinite processes" allowed in algorithm for construction?

mareg_at_mimosa.csv.warwick.ac.uk
Date: 07/16/04 

Date: Fri, 16 Jul 2004 08:21:23 +0000 (UTC)

In article <4TGJc.28230$RD4.1822336@news20.bellglobal.com>,
        "Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> writes:
>
>""H. Shinya"" <erdosfan@yahoo.com> wrote in message
>news:200407151637.i6FGblR14486@proapp.mathforum.org...
>> Is it allowed that in algorithm for constructing something (any
>geometrical objects, for example) one includes "do --- indefinitely"?
>>
>> H. Shinya
>>
>
>By definition, a formal algorithm must complete in a finite amount of time
>(steps). However, many common computer applications are not technically
>algorithms because they often a) are long lived processes (ie: may 'run
>indefinitely' like http server daemons), b) they interact with the external
>environment after they have started (ie: word processor).

There is also a standard notion of a "probabilistic algorithm" which does
not fit the formal definition of an algorithm, because typically a
probabilistic algorithm iterates continually and has a known (or bounded
below) probability p > 0 of returning an answer on each iteration.
(Alternatively, it may be guaranteed to return an answer within a finite time,
but the answer might be wrong.)

Derek Holt.

Relevant Pages