|
=== Ancient algorithms ===
Since antiquity, step-by-step procedures for solving mathematical problems have been attestedrecorded. This includes in [[Babylonian mathematics]] (around 2500 BC),<ref name="Springer Science & Business Media">{{cite book |last1=Chabert |first1=Jean-Luc |title=A History of Algorithms: From the Pebble to the Microchip |date=2012 |publisher=Springer Science & Business Media |isbn=9783642181924 |pages=7–8}}</ref> [[Egyptian mathematics]] (around 1550 BC),<ref name="Springer Science & Business Media" /> [[Indian mathematics]] (around 800 BC and later),<ref name=":6">{{cite book |last1=Sriram |first1=M. S. |editor1-last=Emch |editor1-first=Gerard G. |editor2-last=Sridharan |editor2-first=R. |editor3-last=Srinivas |editor3-first=M. D. |title=Contributions to the History of Indian Mathematics |date=2005 |publisher=Springer |isbn=978-93-86279-25-5 |page=153 |chapter-url=https://books.google.com/books?id=qfJdDwAAQBAJ&pg=PA153 |language=en |chapter=Algorithms in Indian Mathematics}}</ref><ref>Hayashi, T. (2023, January 1). [https://www.britannica.com/biography/Brahmagupta Brahmagupta]. Encyclopedia Britannica.</ref> [https://www.jstor.org/stable/3027363 Thethe Ifa Oracle] (around 500 BC), [[Greek mathematics]] (around 240 BC),<ref name="Cooke2005">{{cite book|last=Cooke|first=Roger L.|title=The History of Mathematics: A Brief Course|date=2005|publisher=John Wiley & Sons|isbn=978-1-118-46029-0}}</ref> and [[Arabic mathematics]] (around 800 AD).<ref name="Dooley">{{cite book |last1=Dooley |first1=John F. |title=A Brief History of Cryptology and Cryptographic Algorithms |date=2013 |publisher=Springer Science & Business Media |isbn=9783319016283 |pages=12–3}}</ref>
The earliest evidence of algorithms is found in the Babylonian mathematics of ancient [[Mesopotamia]] (modern Iraq). A [[Sumer]]ian clay tablet found in [[Shuruppak]] near [[Baghdad]] and dated to {{Circa|2500 BC}} describeddescribes the earliest [[division algorithm]].<ref name="Springer Science & Business Media" /> During the [[First Babylonian dynasty|Hammurabi dynasty]] {{Circa|1800|1600 BC|lk=no}}, [[Babylonia]]n clay tablets described algorithms for computing formulas.<ref>{{cite journal |last1=Knuth |first1=Donald E. |date=1972 |title=Ancient Babylonian Algorithms |url=http://steiner.math.nthu.edu.tw/disk5/js/computer/1.pdf |url-status=dead |journal=Commun. ACM |volume=15 |issue=7 |pages=671–677 |doi=10.1145/361454.361514 |issn=0001-0782 |s2cid=7829945 |archive-url=https://web.archive.org/web/20121224100137/http://steiner.math.nthu.edu.tw/disk5/js/computer/1.pdf |archive-date=2012-12-24}}</ref> Algorithms were also used in [[Babylonian astronomy]]. Babylonian clay tablets describe and employ algorithmic procedures to compute the time and place of significant astronomical events.<ref>{{cite book |last=Aaboe |first=Asger |author-link=Asger Aaboe |title=Episodes from the Early History of Astronomy |date=2001 |publisher=Springer |isbn=978-0-387-95136-2 |place=New York |pages=40–62}}</ref>
Algorithms for arithmetic are also found in ancient [[Egyptian mathematics]], dating back to the [[Rhind Mathematical Papyrus]] {{Circa|1550 BC|lk=no}}.<ref name="Springer Science & Business Media" /> Algorithms were later used in ancient [[Hellenistic mathematics]]. Two examples are the [[Sieve of Eratosthenes]], which was described in the ''[[Introduction to Arithmetic]]'' by [[Nicomachus]],<ref>{{cite web |last=Ast |first=Courtney |title=Eratosthenes |url=http://www.math.wichita.edu/history/men/eratosthenes.html |url-status=live |archive-url=https://web.archive.org/web/20150227150653/http://www.math.wichita.edu/history/men/eratosthenes.html |archive-date=February 27, 2015 |access-date=February 27, 2015 |publisher=Wichita State University: Department of Mathematics and Statistics}}</ref><ref name="Cooke2005" />{{rp|Ch 9.2}} and the [[Euclidean algorithm]], which was first described in ''[[Euclid's Elements]]'' ({{circa|300 BC|lk=no}}).<ref name="Cooke2005" />{{rp|Ch 9.1}}Examples of ancient Indian mathematics included the [[Shulba Sutras]], the [[Kerala school of astronomy and mathematics|Kerala School]], and the [[Brāhmasphuṭasiddhānta]].<ref name=":6" />
==== Weight-driven clocks ====
Bolter credits the invention of the weight-driven clock as "Thethe key invention [of Europe in the Middle Ages],". In particular, he creditsspecifically the [[verge escapement]] mechanism<ref>Bolter 1984:24</ref> that provides us with the tick and tock of a mechanical clock. "The accurate automatic machine"<ref>Bolter 1984:26</ref> led immediately to "mechanical [[automata theory|automata]]" beginning in the 13th century and finally to "computational machines"—the [[difference engine]] and analytical engines of [[Charles Babbage]] and Countess [[Ada Lovelace]], in the mid-19th century.<ref>Bolter 1984:33–34, 204–206.</ref>. Lovelace is credited with the first creation of an algorithm intended for processing on a computer—Babbagecomputer, Babbage's analytical engine, which is the first device considered a real [[Turing-complete]] computer instead of just a [[calculator]]—and. Lovelace is sometimes called "history's first programmer" as a result, though a full implementation of Babbage's second device would not be realized until decades after her lifetime.
==== Electromechanical relay ====
Bell and Newell (1971) indicatewrite that the [[Jacquard loom]] (1801), a precursor to [[Hollerith card]]s (punch cards, 1887), and "telephone switching technologies" were the roots of a tree leadingled to the development of the first computers.<ref>Bell and Newell diagram 1971:39, cf. Davis 2000</ref> By the mid-19th century, the [[telegraph]], the precursor of the telephone, was in use throughout the world, its discrete and distinguishable encoding of letters as "dots and dashes" a common sound. By the late 19th century, the [[ticker tape]] ({{circa|1870s}}) was in use, as was the use ofwere Hollerith cards in the(c. 1890 U.S. census). Then came the [[teleprinter]] ({{circa|1910|lk=no}}) with its punched-paper use of [[Baudot code]] on tape.
Telephone-switching networks of [[relays|electromechanical relays]] (were invented in 1835). wasThese behindled to the workinvention of the digital adding device by [[George Stibitz]] (in 1937), the inventor of the digital adding device. As heWhile workedworking in Bell Laboratories, he observed the "burdensome'" use of mechanical calculators with gears. "He went home one evening in 1937 intending to test his idea... When the tinkering was over, Stibitz had constructed a binary adding device".<ref>Melina Hill, Valley News Correspondent, ''A Tinkerer Gets a Place in History'', Valley News West Lebanon NH, Thursday, March 31, 1983, p. 13.</ref> The mathematician [[Martin Davis (mathematician)|Martin Davi]]s supported the particular importance of the electromechanical relay.<ref>Davis 2000:14</ref>
=== Formalization ===
[[File:Diagram for the computation of Bernoulli numbers.jpg|thumb|[[Ada Lovelace]]'s diagram from "[[Note G]]", the first published computer algorithm]]
In 1928, a partial formalization of the modern concept of algorithms began with attempts to solve the ''[[Entscheidungsproblem]] ''(decision problem) posed by [[David Hilbert]]. Later formalizations were framed as attempts to define "[[effective calculability]]"<ref>Kleene 1943 in Davis 1965:274</ref> or "effective method".<ref>Rosser 1939 in Davis 1965:225</ref> Those formalizations included the [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] recursive functions of 1930, 1934 and 1935, [[Alonzo Church]]'s [[lambda calculus]] of 1936, [[Emil Post]]'s [[Formulation 1]] of 1936, and [[Alan Turing]]'s [[turingTuring machines]] of 1936–37 and 1939.
==Representations==
|
