Algorithms and Computability
Last Update: Saturday, 13 April 2024 |
Note 1: Many of these items are online; links are given where they are known. Other items may also be online; an internet search should help you find them.
Note 2: In general, works are listed in chronological order.
(This makes it easier to follow the historical development of ideas.)
General Readings on Computability
§7.2: Functions and Computation
'compute':
The Latin word ' computare', in turn, comes from the
Latin morpheme ' com', meaning "together with", and the
Latin word ' putare', meaning "to cleanse, to prune, to reckon,
to consider, think" (and ' putare' came from a word meaning "clean,
pure"). So, in ancient Rome at least, to "compute" seems to have meant, more or
less, something like:
"to consider or think about things together", "to clear things up together",
or maybe "to reckon with (something)".
'reckon':
'count':
'calculate':
'figure':
The bottom line seems to be this: 'Computation' originally meant something
very closely related to our modern notion of "symbol (that is, shape)
manipulation",
which is another way of describing syntax — the "grammatical" properties
of, and relations among, the symbols of a language. (We discuss syntax
in §§13.2, 15.2.1, 16.10, and 18.8.3.)
On the history of the terms 'computable' vs. 'recursive', see:
We discuss recursive functions in §7.6.
§7.2.3: Functions Described Intensionally:
For more on the notion of understanding in terms of the
internal workings of a black box, see:
which also suggests an analogy between computation and causation.
§7.3.1: Ancient Algorithms:
For more on Al-Khwarizmi and his algorithms, see:
§7.3.2: "Effectiveness":
§7.3.3: Three Attempts at Precision
On Procedures vs. Algorithms:
§7.4.1: Insight 1: Representation:
§7.4.2: Insight 2: Processing:
For another minimal set of operations, see:
A version of Wang's machine, with many examples, is given in
Dennett 2013,
Ch. 24.
§7.4.3: Insight 3: Structure:
§7.4.4: Insight 4: The Church-Turing Computability Thesis:
and that:
for the definition of lambda-definability.
He cites:
for the definition of general recursiveness.
And he cites:
for the proof of their equivalence.
§7.4.5: Insight 5: Implementation:
Physical implementations of computation are discussed in great detail in:
§7.5.1: Basic Programs:
§7.6.1: A Recursive Definition of Natural Numbers:
§7.6.2: Recursive Definitions of Recursive Functions:
A good general overview of recursive functions that is pretty consistent
with the presentation in this section is:
§7.7.1: The Halting Problem:
§7.9: Questions for the Reader
Question 7:
"Many now view computation as a fundamental part of nature, like atoms or
the integers."
Although the text talks about "computing", other terms that are used
to describe more or less the same territory are 'computation' and
'algorithms'. Here, we take a brief detour into the etymology of
these and some related terms.
(We look at the etymology of 'algorithm' in §7.3.1.)
— Fortnow, L. (2010). What is computation? Ubiquity, Article 5,
p. 2.
According to the
OED,
the verb 'to compute' comes from the Latin verb ' computare',
meaning "to calculate, reckon, to count up".
But when people talk about "computing" today, they mean a great deal
more than mere counting. Computing has come to include everything we
can do with computers, including text processing, watching videos, and
playing games. So, clearly, the meaning has been extended to include non-numerical
"reckoning".
The verb 'to reckon' originally meant "to give an account of, recount; to
tell; to describe", and later came to mean "to count, to calculate".
'Reckon' is from an
Indo-European
root 'rek', possibly meaning "to reach" or
"to tell, to narrate, to say" (as in "to recite" or "to recount").
These meanings, in turn, may derive from an earlier meaning "to
arrange", "to put right", "to move in a straight line".
'Count' also came from 'computare' and originally meant
"to enumerate", "to recite a list"
(and, as we just saw, 'recite' is probably related to 'reckon').
Note that when you "count", you "recite" a list of number words.
'Calculate' came from Latin 'calculus'. This certainly did not
mean the contents of a certain high school or college
course that studies the branch of mathematics concerned with
differentiation and integration, and invented by Newton and
Leibniz in the 17th century! Rather, it meant "pebble" or "small stone",
since counting was done with stones originally.
(As a
Rhymes with Orange comic strip from 22 August 2011 put it,
"There is more computing power in this little abacus than in all the giant
rocks we move aorund to do addition.")
Even today, a "calculus" in medicine is an accumulation of minerals in the body,
forming a small, stone-like object. The root 'calc' came from
'calx', meaning "chalk, limestone", and is related to 'calcium'.
The verb 'to figure' means "to use figures to reckon".
The earliest citation in the OED for the noun 'figure'
is from 1225, when it meant "numerical symbol".
A citation from 1250 has the meaning "embodied (human) form".
And a citation from 1300 has the more general meaning of "shape".
(This conversion of the noun 'figure' to a verb is an
example of what Alan Perlis meant when he joked,
"In English, every word can be verbed".)
In order to answer this question, many
legal experts have tried to give a definition of 'algorithm'.
One such
attempt is:
and see:
Advancement of Learning by Lord Bacon; then
search for "A Biliteral Alphabet"
Rapaport, W.J. (2017). On the relation of computing to the world. In
Powers, T.M., editor, Philosophy
and Computing: Essays in Epistemology, Philosophy of Mind, Logic, and
Ethics, pages 29–64. Springer, Cham, Switzerland.
"the correct definition of mechanical computabilty was established beyond any
doubt by Turing"
(Gödel, K. (1938). Undecidable Diophantine propositions. In
Feferman, S.
et al., editors, Kurt Gödel:
Collected Works, Vol. III, pages 164–175.
Oxford University Press, 1995, Oxford, p. 168)
"this definition
… rest[s] on the dubious assumption that there is a finite number
of states of mind" (Shagrir 2006, §1).
Kleene, S.C. (1936). λ-definability and recursiveness. Duke Mathematical
Journal, 2:340–353.
Is our
informal or pre-theoretical conception of logic best captured by
first-order predicate logic or by some other (more powerful?) logic.
and programs that can determine whether a given program halts, see:
—Richard Powers, Orfeo: A Novel (New York:
W.W. Norton, 2014), p. 194.
For more information on relative computability, see
Soare 2009,
Soare 2016,
and
Homer and Selman 2011
Copyright © 2023–2024 by
William J. Rapaport
(rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/OR/A0fr07.html-20240413