Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The University of California Statistics Department; where mean is normal, and deviation standard.


devel / comp.arch.embedded / Re: Definition of an Algorithm

SubjectAuthor
* Definition of an AlgorithmRick C
+* Re: Definition of an AlgorithmPaul Rubin
|`* Re: Definition of an AlgorithmRick C
| +* Re: Definition of an AlgorithmDavid Brown
| |`* Re: Definition of an AlgorithmRick C
| | +- Re: Definition of an AlgorithmPaul Rubin
| | +- Re: Definition of an AlgorithmDavid Brown
| | `- Re: Definition of an AlgorithmGeorge Neuner
| `- Re: Definition of an AlgorithmPaul Rubin
`* Re: Definition of an AlgorithmDavid Brown
 `* Re: Definition of an AlgorithmRick C
  +* Re: Definition of an AlgorithmDimiter_Popoff
  |`* Re: Definition of an AlgorithmRick C
  | `- Re: Definition of an AlgorithmDavid Brown
  +* Re: Definition of an AlgorithmNiklas Holsti
  |+- Re: Definition of an AlgorithmDavid Brown
  |`- Re: Definition of an AlgorithmRick C
  +- Re: Definition of an AlgorithmDavid Brown
  `- Re: Definition of an AlgorithmPaul Rubin

1
Definition of an Algorithm

<7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1093&group=comp.arch.embedded#1093

 copy link   Newsgroups: comp.arch.embedded
X-Received: by 2002:ac8:5854:0:b0:39c:dba4:6fa0 with SMTP id h20-20020ac85854000000b0039cdba46fa0mr18471409qth.175.1667358249893;
Tue, 01 Nov 2022 20:04:09 -0700 (PDT)
X-Received: by 2002:a25:8f8f:0:b0:6c1:cd87:e726 with SMTP id
u15-20020a258f8f000000b006c1cd87e726mr19305228ybl.560.1667358249617; Tue, 01
Nov 2022 20:04:09 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border-1.nntp.ord.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.embedded
Date: Tue, 1 Nov 2022 20:04:09 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=63.114.57.174; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 63.114.57.174
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
Subject: Definition of an Algorithm
From: gnuarm.d...@gmail.com (Rick C)
Injection-Date: Wed, 02 Nov 2022 03:04:09 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 34
X-Received-Bytes: 2417
 by: Rick C - Wed, 2 Nov 2022 03:04 UTC

I recall in one of the early computer science classes I took, a professor defined an algorithm in a mathematical definition. She gave a list of properties an algorithm had to have to qualify as an algorithm. She also listed some features that were not required, such as being a computer program.

I recall these features:

1) Output - without output a procedure is pointless.

2) Input - ??? I want to say input is optional. So a set of steps to calculate some number of digits of pi would qualify as an algorithm, in spite of not having inputs.

3) Steps - she used qualifiers that indicated the steps had to be clear and unambiguous.

4) Finite - the steps must come to an end, i.e. at some point the algorithm has to produce the result, it can't be infinite.

I don't recall other qualifications, but I think there is at least one I'm missing. It was not a long list, and, like I've said, I don't think Input was on the list.

The web searches seem to produce some pretty vague, garbage definitions, some even saying it is a computer program, which I'm certain it does not have to be.

Anyone familiar with this?

--

Rick C.

- Get 1,000 miles of free Supercharging
- Tesla referral code - https://ts.la/richard11209

Re: Definition of an Algorithm

<87h6zi2atg.fsf@nightsong.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1095&group=comp.arch.embedded#1095

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: no.em...@nospam.invalid (Paul Rubin)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Tue, 01 Nov 2022 22:18:51 -0700
Organization: A noiseless patient Spider
Lines: 14
Message-ID: <87h6zi2atg.fsf@nightsong.com>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="a4c277599db1974944373a50bcd7f45b";
logging-data="1074668"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Z5IbvX6W5kJux7WZ+UaTe"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:fXzxx89uXnz/41Rr1+qdT0oUDKQ=
sha1:ovotcsGWdmJpvRJd2WfhKUKz4Gs=
 by: Paul Rubin - Wed, 2 Nov 2022 05:18 UTC

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> Anyone familiar with this?

Meh, there is not really an accepted formal definition, and to some
extent it is a philosophy question. The word algorithm comes from
Arabic, but the modern notion of Turing machines is from the 1920s.

There are a bunch of viewpoints on the topic here:

https://en.wikipedia.org/wiki/Algorithm_characterizations

A further take is here:

https://plato.stanford.edu/entries/computer-science/#Algo

Re: Definition of an Algorithm

<94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1097&group=comp.arch.embedded#1097

 copy link   Newsgroups: comp.arch.embedded
X-Received: by 2002:a05:6214:2484:b0:4bb:de5d:b6e4 with SMTP id gi4-20020a056214248400b004bbde5db6e4mr15978816qvb.126.1667367726844;
Tue, 01 Nov 2022 22:42:06 -0700 (PDT)
X-Received: by 2002:a5b:c92:0:b0:688:436c:b2b with SMTP id i18-20020a5b0c92000000b00688436c0b2bmr21696215ybq.436.1667367726588;
Tue, 01 Nov 2022 22:42:06 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.embedded
Date: Tue, 1 Nov 2022 22:42:06 -0700 (PDT)
In-Reply-To: <87h6zi2atg.fsf@nightsong.com>
Injection-Info: google-groups.googlegroups.com; posting-host=63.114.57.174; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 63.114.57.174
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com> <87h6zi2atg.fsf@nightsong.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
Subject: Re: Definition of an Algorithm
From: gnuarm.d...@gmail.com (Rick C)
Injection-Date: Wed, 02 Nov 2022 05:42:06 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2644
 by: Rick C - Wed, 2 Nov 2022 05:42 UTC

On Wednesday, November 2, 2022 at 1:18:56 AM UTC-4, Paul Rubin wrote:
> Rick C <gnuarm.del...@gmail.com> writes:
> > Anyone familiar with this?
>
> Meh, there is not really an accepted formal definition, and to some
> extent it is a philosophy question. The word algorithm comes from
> Arabic, but the modern notion of Turing machines is from the 1920s.
>
> There are a bunch of viewpoints on the topic here:
>
> https://en.wikipedia.org/wiki/Algorithm_characterizations
>
> A further take is here:
>
> https://plato.stanford.edu/entries/computer-science/#Algo

If there's no definition, I guess I need to stop using the term.

The Wikipedia article starts off as a poor substitute for what it's supposed to be, with no reference anywhere in the section. This is one of the worst examples I've ever seen, even for Wikipedia. I'm amazed it was ever allowed. Probably a matter of the camel getting its nose under the tent.

But the section that actually tried to define an algorithm (Features of a good algorithm) seems to hit the nail on the head, as far as I can see. It mentions input though, which I'm pretty sure can be a null set without impacting that the process is an algorithm. So factually, input is not required, and not part of the definition.

--

Rick C.

+ Get 1,000 miles of free Supercharging
+ Tesla referral code - https://ts.la/richard11209

Re: Definition of an Algorithm

<tjt93i$135hd$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1098&group=comp.arch.embedded#1098

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 2 Nov 2022 09:17:54 +0100
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <tjt93i$135hd$1@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<87h6zi2atg.fsf@nightsong.com>
<94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 2 Nov 2022 08:17:54 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="84c97277b00ecefe695f502c294a2caa";
logging-data="1152557"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ChlFl86dVWhsaeHaa8+v9IaZ8/CznMuU="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.9.1
Cancel-Lock: sha1:IzDEIi+bcXwc6wIte18pj823OuQ=
In-Reply-To: <94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
Content-Language: en-GB
 by: David Brown - Wed, 2 Nov 2022 08:17 UTC

On 02/11/2022 06:42, Rick C wrote:
> On Wednesday, November 2, 2022 at 1:18:56 AM UTC-4, Paul Rubin
> wrote:
>> Rick C <gnuarm.del...@gmail.com> writes:
>>> Anyone familiar with this?
>>
>> Meh, there is not really an accepted formal definition, and to
>> some extent it is a philosophy question. The word algorithm comes
>> from Arabic, but the modern notion of Turing machines is from the
>> 1920s.
>>
>> There are a bunch of viewpoints on the topic here:
>>
>> https://en.wikipedia.org/wiki/Algorithm_characterizations
>>
>> A further take is here:
>>
>> https://plato.stanford.edu/entries/computer-science/#Algo
>
> If there's no definition, I guess I need to stop using the term.

If you stopped using a term just because there is no single formal
definition, you'd have to stop saying anything at all. After all,
there's no definition for the terms "definition" or "term".

It just means that if you are writing something that is supposed to be
rigorous, you have to define what /you/ mean by a given term in the
context of the discussion.

Re: Definition of an Algorithm

<tjtaug$13jl1$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1099&group=comp.arch.embedded#1099

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 2 Nov 2022 09:49:19 +0100
Organization: A noiseless patient Spider
Lines: 91
Message-ID: <tjtaug$13jl1$1@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 2 Nov 2022 08:49:20 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="84c97277b00ecefe695f502c294a2caa";
logging-data="1167009"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18MH29FDjvr3JIUaUlG3YEur9iClkhJVbk="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.9.1
Cancel-Lock: sha1:vO1YRym46bqOs3Eoj717u/4VzpI=
In-Reply-To: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
Content-Language: en-GB
 by: David Brown - Wed, 2 Nov 2022 08:49 UTC

On 02/11/2022 04:04, Rick C wrote:
> I recall in one of the early computer science classes I took, a
> professor defined an algorithm in a mathematical definition. She
> gave a list of properties an algorithm had to have to qualify as an
> algorithm. She also listed some features that were not required,
> such as being a computer program.
>

Just remember that any such definition will be a "lie-to-children" - an
oversimplification that covers what you need at the time, but not the
full picture. (That is not a bad thing in any way - it is essential to
all learning. And it's the progress from oversimplifications upwards
that keeps things fun. If you are not familiar with the term
"lie-to-children", I recommend "The Science of the Discworld" that
popularised it.)

> I recall these features:
>
> 1) Output - without output a procedure is pointless.
>
> 2) Input - ??? I want to say input is optional. So a set of steps
> to calculate some number of digits of pi would qualify as an
> algorithm, in spite of not having inputs.

You could argue that there is always some kind of input. For example,
you could say that the digit index or the number of digits is the input
to the "calculate pi" algorithm.

(As an aside, I find it fascinating that there is an algorithm to
calculate the nth digit of the hexadecimal expansion of pi that does not
need to calculate all the preceding digits.)

>
> 3) Steps - she used qualifiers that indicated the steps had to be
> clear and unambiguous.
>
> 4) Finite - the steps must come to an end, i.e. at some point the
> algorithm has to produce the result, it can't be infinite.
>

Is that really true?

If you can accept a "calculate pi" algorithm that does not have an
input, then it is not finite.

I remember a programming task from my days at university (doing
mathematics and computation), writing a function that calculated the
digits of pi. The language in question was a functional programming
language similar to Haskell. The end result was a function that
returned an infinite list - you could then print out as many digits from
that list as you wanted.

So what was the output? What kind of output do you allow from your
algorithms? Does the algorithm have to stop and produce and output, or
can it produce a stream of output underway? Can the output be an
algorithm itself? Is it acceptable (according to your definition) for
the output of a "calculate pi" algorithm to be a tuple of a digit of pi
and an algorithm to calculate the next digit-algorithm tuple?

> I don't recall other qualifications, but I think there is at least
> one I'm missing. It was not a long list, and, like I've said, I
> don't think Input was on the list.
>

Was it "deterministic" ? Not all algorithms are deterministic and
repeatable, but it is often a very useful characteristic, and it might
have been relevant for the course you were doing at the time.

> The web searches seem to produce some pretty vague, garbage
> definitions, some even saying it is a computer program, which I'm
> certain it does not have to be.
>
> Anyone familiar with this?
>

I think it is unlikely that you'll get a perfect match for your
professor's definition, except by luck - because I don't think there
really is a single definition. I don't think there is even a single
consistent definition for your features "output", "input", "steps", or
"finite" (in this context).

That's why Turing went to such effort to define his Turing Machine (and
some other mathematicians of the time came up with alternative
"universal computers"). If you want a rigorous definition, you have to
go back to 0's and 1's and something mathematically precise such as a TM
or universal register machine (which is easier to program than a TM).
Of course, you are then restricting your algorithms - it no longer
includes a recipe for brownies, for example, but it does give you
something you can define and reason about.

Re: Definition of an Algorithm

<0aaffb42-594e-46d6-84a0-6c65a26b7716n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1104&group=comp.arch.embedded#1104

 copy link   Newsgroups: comp.arch.embedded
X-Received: by 2002:a05:620a:cc5:b0:6fa:29f2:53df with SMTP id b5-20020a05620a0cc500b006fa29f253dfmr13585267qkj.194.1667414238688;
Wed, 02 Nov 2022 11:37:18 -0700 (PDT)
X-Received: by 2002:a25:bc02:0:b0:695:652e:72b5 with SMTP id
i2-20020a25bc02000000b00695652e72b5mr24558361ybh.21.1667414238409; Wed, 02
Nov 2022 11:37:18 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.embedded
Date: Wed, 2 Nov 2022 11:37:18 -0700 (PDT)
In-Reply-To: <tjt93i$135hd$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=65.207.89.54; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 65.207.89.54
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<87h6zi2atg.fsf@nightsong.com> <94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
<tjt93i$135hd$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <0aaffb42-594e-46d6-84a0-6c65a26b7716n@googlegroups.com>
Subject: Re: Definition of an Algorithm
From: gnuarm.d...@gmail.com (Rick C)
Injection-Date: Wed, 02 Nov 2022 18:37:18 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 3133
 by: Rick C - Wed, 2 Nov 2022 18:37 UTC

On Wednesday, November 2, 2022 at 4:18:00 AM UTC-4, David Brown wrote:
> On 02/11/2022 06:42, Rick C wrote:
> > On Wednesday, November 2, 2022 at 1:18:56 AM UTC-4, Paul Rubin
> > wrote:
> >> Rick C <gnuarm.del...@gmail.com> writes:
> >>> Anyone familiar with this?
> >>
> >> Meh, there is not really an accepted formal definition, and to
> >> some extent it is a philosophy question. The word algorithm comes
> >> from Arabic, but the modern notion of Turing machines is from the
> >> 1920s.
> >>
> >> There are a bunch of viewpoints on the topic here:
> >>
> >> https://en.wikipedia.org/wiki/Algorithm_characterizations
> >>
> >> A further take is here:
> >>
> >> https://plato.stanford.edu/entries/computer-science/#Algo
> >
> > If there's no definition, I guess I need to stop using the term.
> If you stopped using a term just because there is no single formal
> definition, you'd have to stop saying anything at all. After all,
> there's no definition for the terms "definition" or "term".
>
> It just means that if you are writing something that is supposed to be
> rigorous, you have to define what /you/ mean by a given term in the
> context of the discussion.

Your idea that language is not defined is not valid. They are defined in a dictionary, actually, many, not unlike standards, lol. Terms with jargon meaning need their specific definition in that context, or they have little value.

Much of the engineering and computer science I learned in college was taught like math. Terms were defined, in order to know what is being said. Look at math. It's as much about the definitions as the various rules.

If a term like algorithm is not well defined, then I won't use it in engineering unless I define it first.

--

Rick C.

-- Get 1,000 miles of free Supercharging
-- Tesla referral code - https://ts.la/richard11209

Re: Definition of an Algorithm

<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1105&group=comp.arch.embedded#1105

 copy link   Newsgroups: comp.arch.embedded
X-Received: by 2002:a05:622a:15c8:b0:39c:ea8a:82e3 with SMTP id d8-20020a05622a15c800b0039cea8a82e3mr21056440qty.146.1667414740822;
Wed, 02 Nov 2022 11:45:40 -0700 (PDT)
X-Received: by 2002:a25:9ac6:0:b0:6ca:d6:15e6 with SMTP id t6-20020a259ac6000000b006ca00d615e6mr23865435ybo.420.1667414740563;
Wed, 02 Nov 2022 11:45:40 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.embedded
Date: Wed, 2 Nov 2022 11:45:40 -0700 (PDT)
In-Reply-To: <tjtaug$13jl1$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=65.207.89.54; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 65.207.89.54
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com> <tjtaug$13jl1$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
Subject: Re: Definition of an Algorithm
From: gnuarm.d...@gmail.com (Rick C)
Injection-Date: Wed, 02 Nov 2022 18:45:40 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 6775
 by: Rick C - Wed, 2 Nov 2022 18:45 UTC

On Wednesday, November 2, 2022 at 4:49:26 AM UTC-4, David Brown wrote:
> On 02/11/2022 04:04, Rick C wrote:
> > I recall in one of the early computer science classes I took, a
> > professor defined an algorithm in a mathematical definition. She
> > gave a list of properties an algorithm had to have to qualify as an
> > algorithm. She also listed some features that were not required,
> > such as being a computer program.
> >
> Just remember that any such definition will be a "lie-to-children" - an
> oversimplification that covers what you need at the time, but not the
> full picture.

Sorry, I have no idea what you are talking about.

> (That is not a bad thing in any way - it is essential to
> all learning. And it's the progress from oversimplifications upwards
> that keeps things fun. If you are not familiar with the term
> "lie-to-children", I recommend "The Science of the Discworld" that
> popularised it.)
> > I recall these features:
> >
> > 1) Output - without output a procedure is pointless.
> >
> > 2) Input - ??? I want to say input is optional. So a set of steps
> > to calculate some number of digits of pi would qualify as an
> > algorithm, in spite of not having inputs.
> You could argue that there is always some kind of input. For example,
> you could say that the digit index or the number of digits is the input
> to the "calculate pi" algorithm.

You can argue anything. A procedure to calculate pi without specifying how many digits would not be an algorithm because of the "finite" requirement. It doesn't need an input to set the number of digits if that is built into the procedure.

> (As an aside, I find it fascinating that there is an algorithm to
> calculate the nth digit of the hexadecimal expansion of pi that does not
> need to calculate all the preceding digits.)
> >
> > 3) Steps - she used qualifiers that indicated the steps had to be
> > clear and unambiguous.
> >
> > 4) Finite - the steps must come to an end, i.e. at some point the
> > algorithm has to produce the result, it can't be infinite.
> >
> Is that really true?
>
> If you can accept a "calculate pi" algorithm that does not have an
> input, then it is not finite.

Not true.

If it has no definite end, it is not an algorithm. That's why an operating system is not typically an algorithm, it has no specific termination unless you have a command to shut down the computer, I suppose.

> I remember a programming task from my days at university (doing
> mathematics and computation), writing a function that calculated the
> digits of pi. The language in question was a functional programming
> language similar to Haskell. The end result was a function that
> returned an infinite list - you could then print out as many digits from
> that list as you wanted.

How did it return an infinite list? You mean it returned as many digits as you specified or waited to have calculated? If you have an infinite storage system, that's a pretty remarkable achievement. But I expect it would be powered by an infinite improbability drive.

> So what was the output? What kind of output do you allow from your
> algorithms? Does the algorithm have to stop and produce and output, or
> can it produce a stream of output underway? Can the output be an
> algorithm itself? Is it acceptable (according to your definition) for
> the output of a "calculate pi" algorithm to be a tuple of a digit of pi
> and an algorithm to calculate the next digit-algorithm tuple?
> > I don't recall other qualifications, but I think there is at least
> > one I'm missing. It was not a long list, and, like I've said, I
> > don't think Input was on the list.
> >
> Was it "deterministic" ? Not all algorithms are deterministic and
> repeatable, but it is often a very useful characteristic, and it might
> have been relevant for the course you were doing at the time.

If it's not deterministic, it's not an algorithm. Flipping a coin is not an algorithm.

> > The web searches seem to produce some pretty vague, garbage
> > definitions, some even saying it is a computer program, which I'm
> > certain it does not have to be.
> >
> > Anyone familiar with this?
> >
> I think it is unlikely that you'll get a perfect match for your
> professor's definition, except by luck - because I don't think there
> really is a single definition. I don't think there is even a single
> consistent definition for your features "output", "input", "steps", or
> "finite" (in this context).

Ok, that explains a lot about software development.

> That's why Turing went to such effort to define his Turing Machine (and
> some other mathematicians of the time came up with alternative
> "universal computers"). If you want a rigorous definition, you have to
> go back to 0's and 1's and something mathematically precise such as a TM
> or universal register machine (which is easier to program than a TM).
> Of course, you are then restricting your algorithms - it no longer
> includes a recipe for brownies, for example, but it does give you
> something you can define and reason about.

Nothing useful here. Thanks anyway.

--

Rick C.

-+ Get 1,000 miles of free Supercharging
-+ Tesla referral code - https://ts.la/richard11209

Re: Definition of an Algorithm

<tjuges$181t1$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1107&group=comp.arch.embedded#1107

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: dp...@tgi-sci.com (Dimiter_Popoff)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 2 Nov 2022 21:29:22 +0200
Organization: TGI
Lines: 35
Message-ID: <tjuges$181t1$1@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me>
<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
Reply-To: dp@tgi-sci.com
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 2 Nov 2022 19:29:32 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="44e0ed03721f02561580aff56a42d915";
logging-data="1312673"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18sEoJbHcz/pYc009bzCx0u"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.13.1
Cancel-Lock: sha1:UvRXQTFQXVEVf8WYHe5QW/ZZuUE=
Content-Language: en-US
In-Reply-To: <72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
 by: Dimiter_Popoff - Wed, 2 Nov 2022 19:29 UTC

On 11/2/2022 20:45, Rick C wrote:
> ...
>>>
>>> 2) Input - ??? I want to say input is optional. So a set of steps
>>> to calculate some number of digits of pi would qualify as an
>>> algorithm, in spite of not having inputs.
>> You could argue that there is always some kind of input. For example,
>> you could say that the digit index or the number of digits is the input
>> to the "calculate pi" algorithm.
>
> You can argue anything. A procedure to calculate pi without specifying how many digits would not be an algorithm because of the "finite" requirement. It doesn't need an input to set the number of digits if that is built into the procedure.

Of course it is input. You change the number and the output changes.

> .....
>>>
>>> 4) Finite - the steps must come to an end, i.e. at some point the
>>> algorithm has to produce the result, it can't be infinite.
>>>
>> Is that really true?
>>
>> If you can accept a "calculate pi" algorithm that does not have an
>> input, then it is not finite.
>
> Not true.

Of course it is true. Unless you specify the limits for an operation
which is infinite in nature you have the calculating algorithm
running infinitely.
No need to go about calculating Pi, divide 1 by 3 using the
algorithm taught at primary school using a pencil.

Without giving it much thought I'd say an algorithm is an unambiguous
flowchart made up in order to achieve some goal. Anything more than that
would take some qualifier to the word "algorithm".

Re: Definition of an Algorithm

<jsg050FstuaU1@mid.individual.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1108&group=comp.arch.embedded#1108

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!news.mb-net.net!open-news-network.org!news.mind.de!bolzen.all.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: niklas.h...@tidorum.invalid (Niklas Holsti)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 2 Nov 2022 21:53:04 +0200
Organization: Tidorum Ltd
Lines: 47
Message-ID: <jsg050FstuaU1@mid.individual.net>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me>
<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net p8KfXxwL/Ozc7e/S8mP45gwGkryTrf+ZYdc46IPPfwst7HIVzW
Cancel-Lock: sha1:5Sp1+IzcdeER4K28aEdGAWgBcZU=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:102.0)
Gecko/20100101 Thunderbird/102.2.2
Content-Language: en-US
In-Reply-To: <72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
 by: Niklas Holsti - Wed, 2 Nov 2022 19:53 UTC

On 2022-11-02 20:45, Rick C wrote:
> On Wednesday, November 2, 2022 at 4:49:26 AM UTC-4, David Brown wrote:

[snip]

>> I remember a programming task from my days at university (doing
>> mathematics and computation), writing a function that calculated the
>> digits of pi. The language in question was a functional programming
>> language similar to Haskell. The end result was a function that
>> returned an infinite list - you could then print out as many digits from
>> that list as you wanted.
>
> How did it return an infinite list?

Probably by using a non-strict evaluation order
(https://en.wikipedia.org/wiki/Evaluation_strategy#Non-strict_evaluation)
where a data object can be "unbounded" or "potentially infinite" -- only
the parts of the data structure that are later accessed become "real"
data held in memory.

You could of course say that the part (function) of the program that
produced the potentially infinite list is not an "algorithm" by itself,
and becomes an algorithm only when combined with the part of the program
that outputs a finite part of the list. But that seems too limited,
because it that function is clearly independent of the rest of the
program and implements a well-defined computation.

>> Was it "deterministic" ? Not all algorithms are deterministic and
>> repeatable, but it is often a very useful characteristic, and it might
>> have been relevant for the course you were doing at the time.
>
> If it's not deterministic, it's not an algorithm. Flipping a coin is
> not an algorithm.

Randomized or probabilistic algorithms are a huge research subject with
many practical applications, for example for the approximate solution of
hard optimization problems
(https://en.wikipedia.org/wiki/Randomized_algorithm).

A very simple example is the "random sample consensus" method (RanSaC),
which is often called an "algorithm" although it is not deterministic
(https://en.wikipedia.org/wiki/Random_sample_consensus).

Re: Definition of an Algorithm

<tjulc4$18dkn$4@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1110&group=comp.arch.embedded#1110

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 2 Nov 2022 21:53:24 +0100
Organization: A noiseless patient Spider
Lines: 64
Message-ID: <tjulc4$18dkn$4@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me>
<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
<jsg050FstuaU1@mid.individual.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 2 Nov 2022 20:53:24 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="456a077520b9f8076427452b68dcf6ab";
logging-data="1324695"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ypUnuRaDiqDloqCZE/3/01XwdRJZXgdU="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
Thunderbird/102.2.2
Cancel-Lock: sha1:a4ledR/K8rHzSK4Ju0uSdkccsx0=
Content-Language: en-GB
In-Reply-To: <jsg050FstuaU1@mid.individual.net>
 by: David Brown - Wed, 2 Nov 2022 20:53 UTC

On 02/11/2022 20:53, Niklas Holsti wrote:
> On 2022-11-02 20:45, Rick C wrote:
>> On Wednesday, November 2, 2022 at 4:49:26 AM UTC-4, David Brown
>> wrote:
>
> [snip]
>
>
>>> I remember a programming task from my days at university (doing
>>> mathematics and computation), writing a function that calculated
>>> the digits of pi. The language in question was a functional
>>> programming language similar to Haskell. The end result was a
>>> function that returned an infinite list - you could then print
>>> out as many digits from that list as you wanted.
>>
>> How did it return an infinite list?
>
>
> Probably by using a non-strict evaluation order
> (https://en.wikipedia.org/wiki/Evaluation_strategy#Non-strict_evaluation)
> where a data object can be "unbounded" or "potentially infinite" --
> only the parts of the data structure that are later accessed become
> "real" data held in memory.
>

The more relevant term is "lazy evaluation". It is very common in
functional programming languages, and allows you to work with infinite
lists, infinite mutually recursive functions, and all kinds of fun.

> You could of course say that the part (function) of the program that
> produced the potentially infinite list is not an "algorithm" by
> itself, and becomes an algorithm only when combined with the part of
> the program that outputs a finite part of the list. But that seems
> too limited, because it that function is clearly independent of the
> rest of the program and implements a well-defined computation.
>

The function returns a function as part of the output.

>
>>> Was it "deterministic" ? Not all algorithms are deterministic
>>> and repeatable, but it is often a very useful characteristic, and
>>> it might have been relevant for the course you were doing at the
>>> time.
>>
>> If it's not deterministic, it's not an algorithm. Flipping a coin
>> is not an algorithm.
>
> Randomized or probabilistic algorithms are a huge research subject
> with many practical applications, for example for the approximate
> solution of hard optimization problems
> (https://en.wikipedia.org/wiki/Randomized_algorithm).
>
> A very simple example is the "random sample consensus" method
> (RanSaC), which is often called an "algorithm" although it is not
> deterministic
> (https://en.wikipedia.org/wiki/Random_sample_consensus).
>

All sorts of algorithms are non-deterministic. Pretty much any
algorithm that is executed in parallel parts is going to have
non-deterministic execution, which can result in non-deterministic outputs.

Re: Definition of an Algorithm

<87cza52h8k.fsf@nightsong.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1111&group=comp.arch.embedded#1111

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: no.em...@nospam.invalid (Paul Rubin)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 02 Nov 2022 14:12:27 -0700
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <87cza52h8k.fsf@nightsong.com>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<87h6zi2atg.fsf@nightsong.com>
<94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="a4c277599db1974944373a50bcd7f45b";
logging-data="1327809"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/iB6unYzck8ZDaie4Gn6Q9"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:iKovTnvRDETpOn4TcJcat7d2SQk=
sha1:co30fWV+XpfGrkRSgXaQnEMiKDo=
 by: Paul Rubin - Wed, 2 Nov 2022 21:12 UTC

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> If there's no definition, I guess I need to stop using the term.

I wouldn't say there's no definition. I'd say there's no definition
that everybody agrees on, so if you are trying to make formal claims
about algorithms, you have to be precise. Otherwise, I would say, the
different concepts of algorithm have enough shared features that in most
informal usages, you can use the term without confusion.

The same thing applies to the term "probability", and we all use that
term anyway.

Re: Definition of an Algorithm

<tjumg1$18dkn$5@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1112&group=comp.arch.embedded#1112

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 2 Nov 2022 22:12:33 +0100
Organization: A noiseless patient Spider
Lines: 184
Message-ID: <tjumg1$18dkn$5@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me>
<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 2 Nov 2022 21:12:33 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="456a077520b9f8076427452b68dcf6ab";
logging-data="1324695"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX182lj2l4h0zbWlPZ4HRwyFZhvDuCuSQcco="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
Thunderbird/102.2.2
Cancel-Lock: sha1:RBZzRyGebTzqh6Lo7o0BrUJ3ZkI=
Content-Language: en-GB
In-Reply-To: <72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
 by: David Brown - Wed, 2 Nov 2022 21:12 UTC

On 02/11/2022 19:45, Rick C wrote:
> On Wednesday, November 2, 2022 at 4:49:26 AM UTC-4, David Brown wrote:
>> On 02/11/2022 04:04, Rick C wrote:
>>> I recall in one of the early computer science classes I took, a
>>> professor defined an algorithm in a mathematical definition. She
>>> gave a list of properties an algorithm had to have to qualify as an
>>> algorithm. She also listed some features that were not required,
>>> such as being a computer program.
>>>
>> Just remember that any such definition will be a "lie-to-children" - an
>> oversimplification that covers what you need at the time, but not the
>> full picture.
>
> Sorry, I have no idea what you are talking about.

When you are explaining a complicated subject to someone who does not
know about it (and that's typically the case at school or university),
you simplify - you are not telling the truth, you are telling a "lie to
children". If the professor were to try to tell you all about what she
understood by the meaning of "algorithm", it would take the full course
instead of a class. You were given a "lie to children" - and that is
entirely appropriate.

You appear to be mistaking it for a complete definition, which is less good.

>
>
>> (That is not a bad thing in any way - it is essential to
>> all learning. And it's the progress from oversimplifications upwards
>> that keeps things fun. If you are not familiar with the term
>> "lie-to-children", I recommend "The Science of the Discworld" that
>> popularised it.)
>>> I recall these features:
>>>
>>> 1) Output - without output a procedure is pointless.
>>>
>>> 2) Input - ??? I want to say input is optional. So a set of steps
>>> to calculate some number of digits of pi would qualify as an
>>> algorithm, in spite of not having inputs.
>> You could argue that there is always some kind of input. For example,
>> you could say that the digit index or the number of digits is the input
>> to the "calculate pi" algorithm.
>
> You can argue anything. A procedure to calculate pi without
> specifying how many digits would not be an algorithm because of the
> "finite" requirement. It doesn't need an input to set the number of
> digits if that is built into the procedure.
>

It is most certainly an algorithm - just not a finite algorithm. Your
arguments here are circular.

>
>> (As an aside, I find it fascinating that there is an algorithm to
>> calculate the nth digit of the hexadecimal expansion of pi that does not
>> need to calculate all the preceding digits.)
>>>
>>> 3) Steps - she used qualifiers that indicated the steps had to be
>>> clear and unambiguous.
>>>
>>> 4) Finite - the steps must come to an end, i.e. at some point the
>>> algorithm has to produce the result, it can't be infinite.
>>>
>> Is that really true?
>>
>> If you can accept a "calculate pi" algorithm that does not have an
>> input, then it is not finite.
>
> Not true.

Yes, true - pi is not finite.

It is actually pretty irrelevant whether you consider a way to calculate
the first ten digits of pi as a function "calculate_pi_10()" or as
"calculate_pi(10)". It doesn't matter if the input is fixed in the
algorithm or not.

(Can I assume you have never done any functional programming? You would
find it very enlightening - it is much more appropriate for appreciating
computation theory than imperative languages like C or Forth, or
hardware design languages.)

>
> If it has no definite end, it is not an algorithm. That's why an
> operating system is not typically an algorithm, it has no specific
> termination unless you have a command to shut down the computer, I suppose.
>

Again, you are giving a circular argument. Your objection to unending
algorithms is merely that they don't fit your remembered lesson that
talked about finite algorithms. (An OS would probably be better
described as a collection of algorithms rather than a single algorithm.)

>
>> I remember a programming task from my days at university (doing
>> mathematics and computation), writing a function that calculated the
>> digits of pi. The language in question was a functional programming
>> language similar to Haskell. The end result was a function that
>> returned an infinite list - you could then print out as many digits from
>> that list as you wanted.
>
> How did it return an infinite list? You mean it returned as many
> digits as you specified or waited to have calculated? If you have an
> infinite storage system, that's a pretty remarkable achievement. But I
> expect it would be powered by an infinite improbability drive.
>

No, it returned an infinite list.

I know you are familiar with Python, but I don't know at what level of
detail - let me give a comparison here.

When you write "range(1000000)", Python generates a list of a million
numbers from 0 to 999,999. This takes time and memory. But if you
write "xrange(1000000)", it returns a generator expression, quickly and
efficiently. It only actually generates the numbers when it needs to.

In Haskell, you can write :

numbers = 1 : [x + 1 | x <- numbers]

This would be like "numbers = [1] + [x + 1 for x in numbers]" in Python,
if such recursive statements were allowed.

This is an infinite list - it behaves in all ways as an unending list of
integers.

>
>> So what was the output? What kind of output do you allow from your
>> algorithms? Does the algorithm have to stop and produce and output, or
>> can it produce a stream of output underway? Can the output be an
>> algorithm itself? Is it acceptable (according to your definition) for
>> the output of a "calculate pi" algorithm to be a tuple of a digit of pi
>> and an algorithm to calculate the next digit-algorithm tuple?
>>> I don't recall other qualifications, but I think there is at least
>>> one I'm missing. It was not a long list, and, like I've said, I
>>> don't think Input was on the list.
>>>
>> Was it "deterministic" ? Not all algorithms are deterministic and
>> repeatable, but it is often a very useful characteristic, and it might
>> have been relevant for the course you were doing at the time.
>
> If it's not deterministic, it's not an algorithm. Flipping a coin is not an algorithm.
>

Non-deterministic does not mean random.

>
>>> The web searches seem to produce some pretty vague, garbage
>>> definitions, some even saying it is a computer program, which I'm
>>> certain it does not have to be.
>>>
>>> Anyone familiar with this?
>>>
>> I think it is unlikely that you'll get a perfect match for your
>> professor's definition, except by luck - because I don't think there
>> really is a single definition. I don't think there is even a single
>> consistent definition for your features "output", "input", "steps", or
>> "finite" (in this context).
>
> Ok, that explains a lot about software development.
>

Software development is a pretty big field.

>
>> That's why Turing went to such effort to define his Turing Machine (and
>> some other mathematicians of the time came up with alternative
>> "universal computers"). If you want a rigorous definition, you have to
>> go back to 0's and 1's and something mathematically precise such as a TM
>> or universal register machine (which is easier to program than a TM).
>> Of course, you are then restricting your algorithms - it no longer
>> includes a recipe for brownies, for example, but it does give you
>> something you can define and reason about.
>
> Nothing useful here. Thanks anyway.
>

I can't imagine anything in this thread being "useful" - surely it is
just an interesting discussion?

Re: Definition of an Algorithm

<878rkt2fp9.fsf@nightsong.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1113&group=comp.arch.embedded#1113

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!aioe.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: no.em...@nospam.invalid (Paul Rubin)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 02 Nov 2022 14:45:38 -0700
Organization: A noiseless patient Spider
Lines: 57
Message-ID: <878rkt2fp9.fsf@nightsong.com>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me>
<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="a4c277599db1974944373a50bcd7f45b";
logging-data="1335349"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18N9/sIysBpZI5vY5aXDbDQ"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:0s0aQMfr2o0dUmZdkNozZdApUMA=
sha1:kE3jwS+CxH4H8hzYOB/eS1MJpJY=
 by: Paul Rubin - Wed, 2 Nov 2022 21:45 UTC

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> If it has no definite end, it is not an algorithm. ... If it's not
> deterministic, it's not an algorithm. Flipping a coin is not an
> algorithm.

There are lots of what are called "randomized algorithms" which involve
flipping coins. They are used in practice all the time. An example
might be a Monte Carlo method for computing an integral. Whether
every problem solvable by a randomized algorithm can be solved equally
efficiently by a non-randomized one is a big unsolved problem in CS
theory, called "P vs BPP". If you've heard of the more famous P vs NP
problem, it's sort of similar.

There aren't necessarily termination guarantees either. Tons of
practical cryptography programs somewhere contain a routine to generate,
say, a 100 bit prime number. The method (that I would informally say
is an algorithm) is:

1. Generate a random 1000 bit number by flipping coins.
2. Check whether the resulting number is prime. (There are known
deterministic methods for this, but in practice one often uses
a probabilistic test for this step too).
3. If yes, you are done. Otherwise, go back to step 1 and try again.

You can make a good probabilistic estimate of how long the above method
will take, but obviously there is no definite upper bound, since you can
keep generating composite numbers at step 1.

Almost everything in real-world engineering depends on randomness too.
According to statistical thermodynamics, the air molecules in your room
are moving around at random, and there is a small chance that all of
them could coincidentally travel to one small corner of the room. Your
vacuum cleaner's engineering depends on that not happening, and in
practice it doesn't. Semiconductors depend on the statistical
properties of charge carriers, and all that. Randomness is everywhere,
don't be afraid of it.

> How did it return an infinite list? You mean it returned as many
> digits as you specified or waited to have calculated?

It's a finite data structure that represents an infinite list, just like
a sequence of 32 ones and zeros is a data structure that represents an
integer in a certain range. In Haskell you can say "x = [1,2..]" and
that means x represents the infinite list 1,2,3,4,5..... If you try
to print x, you will see 1,2,3,4,5... spewing onto the terminal similar
to if you ran "1 begin dup . 1+ again" in Forth. More normally you
would say "print (take 5 x)" to print the first 5 elements of x, and
get 1,2,3,4,5.

> If you have an infinite storage system,

There's no infinite storage system, it's more like a symbolic algebra
system that has a symbol representing the exact number pi. If you
actually try to print pi, it will start printing 3.14159... using more
and more computation and storage. But if you say "print cos(pi)", it will
print -1 exactly, that sort of thing. There's no infinite storage, just
some behind the scenes shortcuts.

Re: Definition of an Algorithm

<85436a26-9981-43de-a943-96e80da641f4n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1115&group=comp.arch.embedded#1115

 copy link   Newsgroups: comp.arch.embedded
X-Received: by 2002:a05:622a:450:b0:39d:9a0:3b with SMTP id o16-20020a05622a045000b0039d09a0003bmr21964116qtx.213.1667428015926;
Wed, 02 Nov 2022 15:26:55 -0700 (PDT)
X-Received: by 2002:a25:6dc4:0:b0:6c1:822b:391f with SMTP id
i187-20020a256dc4000000b006c1822b391fmr24333549ybc.586.1667428015708; Wed, 02
Nov 2022 15:26:55 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.embedded
Date: Wed, 2 Nov 2022 15:26:55 -0700 (PDT)
In-Reply-To: <tjuges$181t1$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=65.207.89.54; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 65.207.89.54
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me> <72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
<tjuges$181t1$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <85436a26-9981-43de-a943-96e80da641f4n@googlegroups.com>
Subject: Re: Definition of an Algorithm
From: gnuarm.d...@gmail.com (Rick C)
Injection-Date: Wed, 02 Nov 2022 22:26:55 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 3263
 by: Rick C - Wed, 2 Nov 2022 22:26 UTC

On Wednesday, November 2, 2022 at 3:29:38 PM UTC-4, Dimiter wrote:
> On 11/2/2022 20:45, Rick C wrote:
> > ...
> >>>
> >>> 2) Input - ??? I want to say input is optional. So a set of steps
> >>> to calculate some number of digits of pi would qualify as an
> >>> algorithm, in spite of not having inputs.
> >> You could argue that there is always some kind of input. For example,
> >> you could say that the digit index or the number of digits is the input
> >> to the "calculate pi" algorithm.
> >
> > You can argue anything. A procedure to calculate pi without specifying how many digits would not be an algorithm because of the "finite" requirement. It doesn't need an input to set the number of digits if that is built into the procedure.
> Of course it is input. You change the number and the output changes.

If it's part of the procedure, that's not input by definition.

> >>> 4) Finite - the steps must come to an end, i.e. at some point the
> >>> algorithm has to produce the result, it can't be infinite.
> >>>
> >> Is that really true?
> >>
> >> If you can accept a "calculate pi" algorithm that does not have an
> >> input, then it is not finite.
> >
> > Not true.
> Of course it is true. Unless you specify the limits for an operation
> which is infinite in nature you have the calculating algorithm
> running infinitely.

The procedure can specify a number of digits. Why are you arguing about this???

> No need to go about calculating Pi, divide 1 by 3 using the
> algorithm taught at primary school using a pencil.

Why bother with that? Just define it as 3 and be done!

> Without giving it much thought I'd say an algorithm is an unambiguous
> flowchart made up in order to achieve some goal. Anything more than that
> would take some qualifier to the word "algorithm".

Must be nice to be the guy who makes the definitions.

--

Rick C.

+- Get 1,000 miles of free Supercharging
+- Tesla referral code - https://ts.la/richard11209

Re: Definition of an Algorithm

<818acfb8-4d44-4b6b-9b47-5e9b05015314n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1116&group=comp.arch.embedded#1116

 copy link   Newsgroups: comp.arch.embedded
X-Received: by 2002:a05:6214:1c85:b0:4af:7393:3d91 with SMTP id ib5-20020a0562141c8500b004af73933d91mr24248936qvb.74.1667428208793;
Wed, 02 Nov 2022 15:30:08 -0700 (PDT)
X-Received: by 2002:a81:57d2:0:b0:36b:cc32:a150 with SMTP id
l201-20020a8157d2000000b0036bcc32a150mr25932196ywb.420.1667428208575; Wed, 02
Nov 2022 15:30:08 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.arch.embedded
Date: Wed, 2 Nov 2022 15:30:08 -0700 (PDT)
In-Reply-To: <jsg050FstuaU1@mid.individual.net>
Injection-Info: google-groups.googlegroups.com; posting-host=63.114.57.174; posting-account=I-_H_woAAAA9zzro6crtEpUAyIvzd19b
NNTP-Posting-Host: 63.114.57.174
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me> <72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
<jsg050FstuaU1@mid.individual.net>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <818acfb8-4d44-4b6b-9b47-5e9b05015314n@googlegroups.com>
Subject: Re: Definition of an Algorithm
From: gnuarm.d...@gmail.com (Rick C)
Injection-Date: Wed, 02 Nov 2022 22:30:08 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 3601
 by: Rick C - Wed, 2 Nov 2022 22:30 UTC

On Wednesday, November 2, 2022 at 3:53:10 PM UTC-4, Niklas Holsti wrote:
> On 2022-11-02 20:45, Rick C wrote:
> > On Wednesday, November 2, 2022 at 4:49:26 AM UTC-4, David Brown wrote:
> [snip]
> >> I remember a programming task from my days at university (doing
> >> mathematics and computation), writing a function that calculated the
> >> digits of pi. The language in question was a functional programming
> >> language similar to Haskell. The end result was a function that
> >> returned an infinite list - you could then print out as many digits from
> >> that list as you wanted.
> >
> > How did it return an infinite list?
> Probably by using a non-strict evaluation order
> (https://en.wikipedia.org/wiki/Evaluation_strategy#Non-strict_evaluation)
> where a data object can be "unbounded" or "potentially infinite" -- only
> the parts of the data structure that are later accessed become "real"
> data held in memory.
>
> You could of course say that the part (function) of the program that
> produced the potentially infinite list is not an "algorithm" by itself,
> and becomes an algorithm only when combined with the part of the program
> that outputs a finite part of the list. But that seems too limited,
> because it that function is clearly independent of the rest of the
> program and implements a well-defined computation.

Why would it have to be an algorithm?

> >> Was it "deterministic" ? Not all algorithms are deterministic and
> >> repeatable, but it is often a very useful characteristic, and it might
> >> have been relevant for the course you were doing at the time.
> >
> > If it's not deterministic, it's not an algorithm. Flipping a coin is
> > not an algorithm.
> Randomized or probabilistic algorithms are a huge research subject with
> many practical applications, for example for the approximate solution of
> hard optimization problems
> (https://en.wikipedia.org/wiki/Randomized_algorithm).
>
> A very simple example is the "random sample consensus" method (RanSaC),
> which is often called an "algorithm" although it is not deterministic
> (https://en.wikipedia.org/wiki/Random_sample_consensus).

Yeah, people often misuse terms.

--

Rick C.

++ Get 1,000 miles of free Supercharging
++ Tesla referral code - https://ts.la/richard11209

Re: Definition of an Algorithm

<87sfj10xu9.fsf@nightsong.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1117&group=comp.arch.embedded#1117

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: no.em...@nospam.invalid (Paul Rubin)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Wed, 02 Nov 2022 15:56:46 -0700
Organization: A noiseless patient Spider
Lines: 55
Message-ID: <87sfj10xu9.fsf@nightsong.com>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<87h6zi2atg.fsf@nightsong.com>
<94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
<tjt93i$135hd$1@dont-email.me>
<0aaffb42-594e-46d6-84a0-6c65a26b7716n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader01.eternal-september.org; posting-host="a4c277599db1974944373a50bcd7f45b";
logging-data="1335349"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/lvBvYJhFjlpDhSX5CuaRq"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:a0941zldFsdGaUg87QMj8ButqqE=
sha1:3Beym7kAmC9NMOlW/ibt0P2RKLQ=
 by: Paul Rubin - Wed, 2 Nov 2022 22:56 UTC

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> Much of the engineering and computer science I learned in college was
> taught like math. Terms were defined, in order to know what is being
> said. Look at math. It's as much about the definitions as the
> various rules.

I believe electrical engineers frequently use the Dirac delta function,
whose value is infinite at x=0 and zero everywhere else. When you
convolve it with another function, you get back the function that you
convolved with. But by standard mathematical formalism, there is no
such function as the Dirac delta. That didn't stop physicists and
engineers from using it anyway, starting around the 1920s(?).

A rigorous mathematical formalism for such "functions" was not developed
until the 1950s, called "generalized functions" or "Schwartz
distributions". I'd be very surprised if any engineers ever study that.
They just use the Dirac delta without worrying too much about
mathematical rigor, and as long as they don't go too crazy, it acts the
way they expect it to.

> If a term like algorithm is not well defined, then I won't use it in
> engineering unless I define it first.

Engineering practice by others has not been so careful. You might find
a "definition" of the Dirac delta in an engineering book, but if you
look closely at the mathematical details, it will be hand-wavy or have
gaps. They want mostly to agree on the features that they rely on, and
to not worry about the corner cases that they don't use.

Here's a definitional problem for you. Let's say you flip a coin and
then cover it with your hand, so you don't see how it came up. What is
the probability that it came up heads? One notion is that the
probability is obviously 50%, assuming it was a fair coin. A
conflicting notion is that it is obviously not 50%: the coin has already
been flipped and has landed, so it is either definitely heads or else it
is definitely tails. That is, the probability is either 100% or 0%, and
you simply don't know which.

Those two notions of probability are claled Bayesianism and frequentism.
Philosophers have been arguing about them for 100s of years and they
still haven't stopped. Mathematicians deal with this by treating
probability as a topic in analysis involving measure spaces of yada
yada. But a philosopher might say instead that probability is a
sub-topic in the part of philosophy that deals with the nature of
knowledge, and then the Bayesian view is simply a scheme for saying how
strongly you believe a given proposition.

What I'm saying here is that probability, like algorithm, is another one
of those terms that doesn't have a single, universally accepted,
rigorous definition, but that doesn't stop it from being important
anyway.

Re probability, this article is pretty good:

https://ncatlab.org/nlab/show/Is+probability+theory+a+branch+of+mathematics%3F

Re: Definition of an Algorithm

<tjvvoc$1e85r$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1122&group=comp.arch.embedded#1122

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Thu, 3 Nov 2022 09:56:43 +0100
Organization: A noiseless patient Spider
Lines: 101
Message-ID: <tjvvoc$1e85r$1@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<87h6zi2atg.fsf@nightsong.com>
<94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com>
<tjt93i$135hd$1@dont-email.me>
<0aaffb42-594e-46d6-84a0-6c65a26b7716n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 3 Nov 2022 08:56:44 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="a9e1ce2246d9fa9dbb9199e2ffd342f9";
logging-data="1515707"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+K0hJVWqIcDA5vth0PsDaLY0+LlIzNpjI="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.9.1
Cancel-Lock: sha1:xryVeEfeDKdEnXG+Cm4k8X5N9sU=
In-Reply-To: <0aaffb42-594e-46d6-84a0-6c65a26b7716n@googlegroups.com>
Content-Language: en-GB
 by: David Brown - Thu, 3 Nov 2022 08:56 UTC

On 02/11/2022 19:37, Rick C wrote:
> On Wednesday, November 2, 2022 at 4:18:00 AM UTC-4, David Brown
> wrote:
>> On 02/11/2022 06:42, Rick C wrote:
>>> On Wednesday, November 2, 2022 at 1:18:56 AM UTC-4, Paul Rubin
>>> wrote:
>>>> Rick C <gnuarm.del...@gmail.com> writes:
>>>>> Anyone familiar with this?
>>>>
>>>> Meh, there is not really an accepted formal definition, and to
>>>> some extent it is a philosophy question. The word algorithm
>>>> comes from Arabic, but the modern notion of Turing machines is
>>>> from the 1920s.
>>>>
>>>> There are a bunch of viewpoints on the topic here:
>>>>
>>>> https://en.wikipedia.org/wiki/Algorithm_characterizations
>>>>
>>>> A further take is here:
>>>>
>>>> https://plato.stanford.edu/entries/computer-science/#Algo
>>>
>>> If there's no definition, I guess I need to stop using the term.
>> If you stopped using a term just because there is no single formal
>> definition, you'd have to stop saying anything at all. After all,
>> there's no definition for the terms "definition" or "term".
>>
>> It just means that if you are writing something that is supposed to
>> be rigorous, you have to define what /you/ mean by a given term in
>> the context of the discussion.
>
> Your idea that language is not defined is not valid. They are
> defined in a dictionary, actually, many, not unlike standards, lol.

Dictionaries do not /define/ words, they /describe/ words. They say how
words are used, and what people generally mean when they use the word.
That is viewing the issue from the opposite side - use first, then
definition. For technical terms in technical fields, you define the
term first, then use it.

> Terms with jargon meaning need their specific definition in that
> context, or they have little value.

Yes.

But often the definition is not universally accepted - that's why in
technical papers, standards documents, etc., important terms are defined
in the document. They say exactly what you mean by the term in that
context.

So you can use the word "algorithm" loosely, and people usually know
approximately what you mean. But if you want to be rigorous and rely on
properties that are not always agreed upon, you must define you /you/
will use the term in the particular context.

>
> Much of the engineering and computer science I learned in college was
> taught like math. Terms were defined, in order to know what is being
> said. Look at math. It's as much about the definitions as the
> various rules.
>

Sure. But a lot of these things are simplifications, and sometimes they
will be the particular choice of definition that suits the teacher or
class. It applies to maths, it applies to engineering, computer
science, and any other technical topic.

You probably first learned that "integration" meant "finding the area
under a curve". Then you later learn about complex analysis and
integration in circles around poles of complex functions - the
"definition" of integration that you learned now makes no sense
whatsoever. (It is also meaningless for the Dirac delta function, since
Paul brought that up.)

When you learned about "algorithms" in your early computer science
classes, you similarly got a simplistic view. Since my university
course was more theoretical than yours (AFAIUI), I was probably given a
more advanced and nuanced definition of "algorithm" - and I learned that
there is no single definition. You can keep learning, keep
investigating, keep thinking, and come up with new ways to define such
terms, new subclasses or variants of "algorithm", new characteristics
that can be useful or interesting. It is all "right" - the only thing
that is /wrong/ is to claim that /your/ definition is /the/ definition.

> If a term like algorithm is not well defined, then I won't use it in
> engineering unless I define it first.
>

If you need it to be well defined in the context of what you are doing,
then yes, you need to define what you mean by it. If it doesn't need to
be rigorously defined, then you don't need to do so.

So if you are writing "This is the documentation for the algorithm used
to control the speed of the motor" for some embedded software, then
there is absolutely no need to define the term "algorithm". On the
other hand, if you are writing a paper titled "Proof that there is no
algorithm that can determine the halting state of all possible Turing
Machines", then you absolutely /do/ need to define the term.

Re: Definition of an Algorithm

<tk01f3$1ecq0$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1123&group=comp.arch.embedded#1123

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: david.br...@hesbynett.no (David Brown)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Thu, 3 Nov 2022 10:25:55 +0100
Organization: A noiseless patient Spider
Lines: 92
Message-ID: <tk01f3$1ecq0$1@dont-email.me>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com>
<tjtaug$13jl1$1@dont-email.me>
<72ded909-a5a0-427e-9062-85cf3e8a136fn@googlegroups.com>
<tjuges$181t1$1@dont-email.me>
<85436a26-9981-43de-a943-96e80da641f4n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 3 Nov 2022 09:25:55 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="a9e1ce2246d9fa9dbb9199e2ffd342f9";
logging-data="1520448"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/9Egy0Y8pGryNzvWZjo7UisD2IX31tCnk="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.9.1
Cancel-Lock: sha1:RBQsa78knhp4DxXQ6F6oo4sZB8c=
Content-Language: en-GB
In-Reply-To: <85436a26-9981-43de-a943-96e80da641f4n@googlegroups.com>
 by: David Brown - Thu, 3 Nov 2022 09:25 UTC

On 02/11/2022 23:26, Rick C wrote:
> On Wednesday, November 2, 2022 at 3:29:38 PM UTC-4, Dimiter wrote:
>> On 11/2/2022 20:45, Rick C wrote:
>>> ...
>>>>>
>>>>> 2) Input - ??? I want to say input is optional. So a set of steps
>>>>> to calculate some number of digits of pi would qualify as an
>>>>> algorithm, in spite of not having inputs.
>>>> You could argue that there is always some kind of input. For example,
>>>> you could say that the digit index or the number of digits is the input
>>>> to the "calculate pi" algorithm.
>>>
>>> You can argue anything. A procedure to calculate pi without specifying how many digits would not be an algorithm because of the "finite" requirement. It doesn't need an input to set the number of digits if that is built into the procedure.
>> Of course it is input. You change the number and the output changes.
>
> If it's part of the procedure, that's not input by definition.
>

By /your/ definition only.

In Python (for familiarity), you could have :

mult = lambda x, y : x * y
mult3 = lambda x : mult(3, x)
mult3_5 = lambda : mult3(5)

It makes no difference to the theory or the meaning of "algorithm"
whether the input is part of the function or not. (Of course it makes a
major difference in practical use, but not for the theory.)

If you want to learn more, the term to google about is "currying".

>
>>>>> 4) Finite - the steps must come to an end, i.e. at some point the
>>>>> algorithm has to produce the result, it can't be infinite.
>>>>>
>>>> Is that really true?
>>>>
>>>> If you can accept a "calculate pi" algorithm that does not have an
>>>> input, then it is not finite.
>>>
>>> Not true.
>> Of course it is true. Unless you specify the limits for an operation
>> which is infinite in nature you have the calculating algorithm
>> running infinitely.
>
> The procedure can specify a number of digits. Why are you arguing about this???
>

This is a discussion, not an argument. You brought up a rather
theoretical topic, and people have been discussing it beyond your
current level of familiarity. The sensible reaction is to see what you
can learn from this, or to accept that it is going beyond what you know
about and you are dropping out. This is all very theoretical, with no
practical application (that I can imagine) for the kind of work we
comp.arch.embedded denizens do in real life - either you find these
things interesting and fun to thing about, or you don't. (I hope you
/do/ find it interesting - but I do understand that mathematics and
computational theory is an unusual hobby, even for professional software
and hardware developers.)

You perhaps made the first post thinking there is a nice, simple and
clear definition of "algorithm" and you'd get a nice, simple and clear
answer to which clause you'd forgotten from that long-ago lecture. The
list on Wikipedia of the dozens of mathematicians' definitions of
"algorithm" through the years should have been a clue that things aren't
that simple.

>
>> No need to go about calculating Pi, divide 1 by 3 using the
>> algorithm taught at primary school using a pencil.
>
> Why bother with that? Just define it as 3 and be done!
>

Define 1 / 3 to equal 3? ": 1/3 3 ;" might be acceptable in Forth, but
not in mathematics!

>
>> Without giving it much thought I'd say an algorithm is an unambiguous
>> flowchart made up in order to achieve some goal. Anything more than that
>> would take some qualifier to the word "algorithm".
>
> Must be nice to be the guy who makes the definitions.
>

We all get to make such definitions. The question is whether other
people agree with them or not. Dimiter's suggestion here covers the
lowest common denominator that I expect most people would agree with -
even if it is also common to include other features (such as your own
suggestions of input, output and finiteness).

Re: Definition of an Algorithm

<k0a7mh9pijutbdtl4mir2ohvdi15t3cebv@4ax.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=1125&group=comp.arch.embedded#1125

 copy link   Newsgroups: comp.arch.embedded
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: gneun...@comcast.net (George Neuner)
Newsgroups: comp.arch.embedded
Subject: Re: Definition of an Algorithm
Date: Thu, 03 Nov 2022 08:41:37 -0400
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <k0a7mh9pijutbdtl4mir2ohvdi15t3cebv@4ax.com>
References: <7152c71a-9b8f-4fbd-88e4-b81264c9f242n@googlegroups.com> <87h6zi2atg.fsf@nightsong.com> <94936245-f300-48af-ada6-0b376ca676cfn@googlegroups.com> <tjt93i$135hd$1@dont-email.me> <0aaffb42-594e-46d6-84a0-6c65a26b7716n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: reader01.eternal-september.org; posting-host="0e2129331679e0e1bf5b786d26316626";
logging-data="1549720"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+McsWXmUVkg4iPKkZwr5A+iWgX2AWW0zQ="
User-Agent: ForteAgent/8.00.32.1272
Cancel-Lock: sha1:DL4bMkrfMwxL7D3i9g/s/lHlwzw=
 by: George Neuner - Thu, 3 Nov 2022 12:41 UTC

On Wed, 2 Nov 2022 11:37:18 -0700 (PDT), Rick C
<gnuarm.deletethisbit@gmail.com> wrote:

> [David Brown's] idea that language is not defined is not valid. They
> are defined in a dictionary, actually, many, not unlike standards, lol.
> Terms with jargon meaning need their specific definition in that context,
> or they have little value.

Actually dictionaries REFLECT usage of language rather than defining
it. The meanings of words often differ with locality and often change
over time.

Unfortunately, many dictionaries are "abridged": they contain current
and popular definitions - not necessarily ALL definitions - and
pronunciation keys, but generally nothing of the origins or historical
usages of the words.

To get the history of a word you need either to find an an unabridged
print dictionary, or in an online search you must include the term
"etymology" (and then hope the information is not behind a pay wall).
[www.etymonline.com is free and good for English, but it is limited
and has entries for only a few 100,000 words.]

YMMV,
George

[Last I checked (admittedly some years ago), Webster's unabridged
English dictionary was 26 volumes. Oh, and that only covered the ~1.2
million English words officially recognized at that time ... the
dictionary of English slang was an additional 37 volumes. Altogether
they filled up several shelves in the public library.

Webster's online unabridged dictionary is pay walled.]

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor