| Home | About | Subscribe | Search | Member Area |
Humanist Discussion Group, Vol. 33, No. 693.
Department of Digital Humanities, King's College London
Hosted by King's Digital Lab
www.dhhumanist.org
Submit to: humanist@dhhumanist.org
[1] From: Jeffrey Binder
Subject: Re: [Humanist] 33.688: recipes and algorithms: why not interactive? (141)
[2] From: Willard McCarty
Subject: recipes and algorithms (64)
--[1]------------------------------------------------------------------------
Date: 2020-03-25 15:48:19+00:00
From: Jeffrey Binder
Subject: Re: [Humanist] 33.688: recipes and algorithms: why not interactive?
(This is my first time posting on this listserv—hi everyone!)
Perhaps it would be helpful to distinguish algorithms as instructions for a
programmer—as recipes for writing code—from algorithms as objects of
mathematical analysis. If one thinks of an algorithm as akin to a recipe, then
there is nothing to prevent one from writing an algorithm that includes
interaction with an environment. But in terms of the mathematical theory of
algorithms, there are advantages to excluding such interaction.
In computer science, algorithms are classified by their “asymptotic behavior,”
meaning how quickly their time and memory requirements increase as the input
gets larger. (See https://en.wikipedia.org/wiki/Complexity_class.) An algorithm
is classified as O(n) if the running time rises linearly with the input size; it
is O(n^2) if it goes up quadratically, O(2^n) if exponentially, etc. The
asymptotic behavior is generally determined through a prioristic mathematical
analysis, not through empirical measurement. Searching an unsorted list is
typically O(n), but searching a sorted list can be done in O(log n) time.
Efficient sorting algorithms are usually O(n log n). This is an important
consideration in programming because algorithms with poor asymptotic behavior
are often so slow that they are effectively useless.
The problem is that there is no straightforward way to apply this theory to
procedures that can interact with an environment in arbitrary ways, since the
environment can introduce unpredictable factors into the behavior of the
process. There have been some attempts to address the input-at-beginning
limitation in computer science; a procedure that gets its input bit by bit is
called an “online algorithm" (see
https://en.wikipedia.org/wiki/Online_algorithm). But these revisions can only go
so far—evaluating the behavior of a process mathematically requires some degree
of abstraction, and abstraction is an imagined severing from the world.
Best,
Jeffrey M. Binder
Center for Humanities and Information
Pennsylvania State University
> On Mar 25, 2020, at 2:34 AM, Humanist wrote:
>
> Humanist Discussion Group, Vol. 33, No. 688.
> Department of Digital Humanities, King's College London
> Hosted by King's Digital Lab
> www.dhhumanist.org
> Submit to: humanist@dhhumanist.org
>
>
>
>
> Date: 2020-03-24 15:23:03+00:00
> From: Henry Schaffer
> Subject: Re: [Humanist] 33.684: recipes and algorithms
>
> Why can't "interact while they compute"? I need to start with figuring out
> what is an algorithm. Perhaps this definition will suffice: "In mathematics
> and computer science, an algorithm is a finite sequence of well-defined,
> computer-implementable instructions, typically to solve a class of problems
> or to perform a computation.[1][2] Algorithms are always unambiguous and
> are used as specifications for performing calculations, data processing,
> automated reasoning, and other tasks."
> https://en.wikipedia.org/wiki/Algorithm
>
> An algorithm usually has an "Input" step (e.g. see the Input box in the
> figure in the flow chart in the link above). It also has an "Output" (e.g.
> labelled "PRINT" in that flow chart.) It can have more than one input or
> output - and they are inherently separated in time. (The time is not
> specified, and it certainly depends on the speed of computation, but we
> don't pretend that computation doesn't take any time, and, anyhow, an
> algorithm can have a "wait" statement.
>
> Therefore, I don't see any barrier keeping an algorithm from getting some
> input, computing some output, getting some more input, computing something
> about the change from the previous input, and outputting something about
> that, ...
>
> Isn't the algorithm interacting with the external world? I claim it is.
>
> --henry
>
> On Tue, Mar 24, 2020 at 6:09 AM Humanist wrote:
>
>> Humanist Discussion Group, Vol. 33, No. 684.
>> Department of Digital Humanities, King's College London
>> Hosted by King's Digital Lab
>> www.dhhumanist.org
>> Submit to: humanist@dhhumanist.org
>>
>>
>>
>>
>> Date: 2020-03-23 06:50:09+00:00
>> From: Willard McCarty
>> Subject: recipes and algorithms
>>
>> Those who bake and/or cook as well as write code will be interested in
>> Warren Sack's discussion of algorithms as recipes, mostly in Chapter 4
>> of The Software Arts (2019), beginning thus:
>>
>>> Algorithms as Recipes
>>>
>>> So, if algorithms are not mathematics or logic, then what are they?
>>> Algorithms are part and parcel with what historian of science Pamela
>>> Long describes as the long history of writings from and about the
>>> mechanical arts, including "ancient writings related to technical
>>> production, such as Hellenistic engineering books, as well as
>>> writings tied to political and military praxis, including Xenophon's
>>> Oeconomicus and Roman agricultural writings." This tradition
>>> includes medieval guild regulations and continues on into today's
>>> language of patent law and how-to books, and, crucially, this
>>> tradition of the mechanical arts also includes recipes and
>>> cookbooks.
>>>
>>> Knuth recognizes this direct connection to the arts but does not
>>> pursue it with any rigor. In chapter 1 of the first volume of The Art
>>> of Computer Programming, Knuth compares algorithms to recipes,
>>> asserts that "a computer programmer can learn much by studying a good
>>> recipe book ," and then admits that "the author has barely resisted
>>> the temptation to name the present volume 'The Programmer's
>>> Cookbook.'...
>>
>> His aim is to open up the gulf between algorithms as self-contained
>> automatic machines and software more broadly conceived. In "Interactive
>> foundations of computing" (1998), Peter Wegner likewise argues that,
>>
>>> Dumb algorithms become smart agents (embedded systems) when enhanced
>>> by interaction. Algorithms are 'dumb' and 'blind' because they cannot
>>> interact while they compute: they are autistic in precluding
>>> interaction. In contrast, interactive systems model an external
>>> reality more demanding and expressive than inner algorithmic
>>> transformation rules.
>>
>> More on this topic would surely be welcome in our respective isolations.
>>
>> Yours,
>> WM
>> --
>> Willard McCarty (www.mccarty.org.uk/),
>> Professor emeritus, Department of Digital Humanities, King's College
>> London; Editor, Interdisciplinary Science Reviews
>> (www.tandfonline.com/loi/yisr20) and Humanist (www.dhhumanist.org)
--[2]------------------------------------------------------------------------
Date: 2020-03-25 07:20:45+00:00
From: Willard McCarty
Subject: recipes and algorithms
This in response to Henry's challenge. Forgive, if you will,
a semi-educated attempt to muddle my way to an understanding
of 'algorithm'. So here goes.
A. Consider the following pseudo-code:
LOAD X
ADD 1 TO X
STORE X
This I assume to be an algorithm.
B. Now let's assume further that there's some external
variable, say TEMPERATURE, which is read from a thermometer.
Adding this to the pseudocode, we introduce some
interactivity:
LOAD X
READ TEMPERATURE
ADD TEMPERATURE TO X
STORE X
Is this still strictly speaking an algorithm? How about this,
which requests input from a user:
LOAD X
ACCEPT WORD
PRINT WORD
C. Now consider this recipe:
Assemble:
1/4 cup of olive oil
4 cloves of garlic sliced in half
1 350z can of (preferably) Italian plum tomatoes
3 basil leaves, washed, patted dry and chopped
1/2 teaspoon of oregano
salt & pepper to taste
Follow these steps:
(1) place garlic and olive oil in a large sauce pan;
(2) turn heat to medium ans cook until garlic is soft and lightly browned;
(3) crush the tomatoes and add with their juices;
(4) fill empty tomato can 1/4 of the way with water and pour in with
tomatoes;
(5) add basil, oregano, salt and pepper;
(6) bring to a boil, then lower heat to a simmer and cook until
thickened, approximately 20 to 30 minutes.
The differences are huge and illuminating. Does the second example
above open the door to the third?
Yours,
WM
--
Willard McCarty (www.mccarty.org.uk/),
Professor emeritus, Department of Digital Humanities, King's College
London; Editor, Interdisciplinary Science Reviews
(www.tandfonline.com/loi/yisr20) and Humanist (www.dhhumanist.org)
_______________________________________________
Unsubscribe at: http://dhhumanist.org/Restricted
List posts to: humanist@dhhumanist.org
List info and archives at at: http://dhhumanist.org
Listmember interface at: http://dhhumanist.org/Restricted/
Subscribe at: http://dhhumanist.org/membership_form.php
Editor: Willard McCarty (King's College London, U.K.; Western Sydney University, Australia)
Software designer: Malgosia Askanas (Mind-Crafts)
This site is maintained under a service level agreement by King's Digital Lab.