Editing Algorithm (section)

== History ==
{{Missing information|1=section|2=20th and 21st century development of computer algorithms|date=October 2023}}

=== Ancient algorithms ===
Step-by-step procedures for solving mathematical problems have been recorded since antiquity. 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> the Ifa Oracle (around 500 BC),<ref>{{Cite journal |last=Zaslavsky |first=Claudia |date=1970 |title=Mathematics of the Yoruba People and of Their Neighbors in Southern Nigeria |url=https://www.jstor.org/stable/3027363 |journal=The Two-Year College Mathematics Journal |volume=1 |issue=2 |pages=76–99 |doi=10.2307/3027363 |jstor=3027363 |issn=0049-4925}}</ref> [[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> [[Chinese mathematics|Chinese mathematics (around 200 BC and later)]],<ref>{{Cite journal |date=1999 |editor-last=Chabert |editor-first=Jean-Luc |title=A History of Algorithms |url=https://link.springer.com/book/10.1007/978-3-642-18192-4 |journal=SpringerLink |language=en |doi=10.1007/978-3-642-18192-4|isbn=978-3-540-63369-3 }}</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 ancient [[Mesopotamia]]n mathematics. A [[Sumer]]ian clay tablet found in [[Shuruppak]] near [[Baghdad]] and dated to {{Circa|2500 BC}} describes 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" />

The first cryptographic algorithm for deciphering encrypted code was developed by [[Al-Kindi]], a 9th-century Arab mathematician, in ''A Manuscript On Deciphering Cryptographic Messages''. He gave the first description of [[cryptanalysis]] by [[frequency analysis]], the earliest codebreaking algorithm.<ref name="Dooley" />

=== Computers ===

==== Weight-driven clocks ====
Bolter credits the invention of the weight-driven clock as "the key invention [of [[Europe in the middle ages|Europe in the Middle Ages]]]," specifically the [[verge escapement]] mechanism<ref>Bolter 1984:24</ref> producing the tick and tock of a mechanical clock. "The accurate automatic machine"<ref>Bolter 1984:26</ref> led immediately to "mechanical [[automata theory|automata]]" in the 13th century and "computational machines"—the [[difference engine|difference]] and [[analytical engine]]s of [[Charles Babbage]] and [[Ada Lovelace]] in the mid-19th century.<ref>Bolter 1984:33–34, 204–206.</ref> Lovelace designed the first algorithm intended for processing on a computer, Babbage's analytical engine, which is the first device considered a real [[Turing-complete]] computer instead of just a [[calculator]]. Although the full implementation of Babbage's second device was not realized for decades after her lifetime, Lovelace has been called "history's first programmer".

==== Electromechanical relay ====
Bell and Newell (1971) write that the [[Jacquard loom]], a precursor to [[Hollerith card]]s (punch cards), and "telephone switching technologies" led 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. By the late 19th century, the [[ticker tape]] ({{circa|1870s}}) was in use, as were Hollerith cards (c. 1890). 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. These led to the invention of the digital adding device by [[George Stibitz]] in 1937. While working 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><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 [[Turing machines]] of 1936–37 and 1939.