Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Conceptual Confluence in 1936: Post and Turing Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Algorithms: From Al-Khwarizmi to Turing and Beyond

Author : Wolfgang Thomas

Published in: Turing’s Revolution

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The foundational work of Alan Turing and contemporaries on computability marked a turning point in the development of mathematical sciences: It clarified in a rather absolute sense what is computable in the setting of symbolic computation, and it also opened the way to computer science where the use of algorithms and the discussion on their nature was enriched by many new facets. The present essay is an attempt to address both aspects: We review the historical development of the concept of algorithm up to Turing, emphasizing the essential role that logic played in this context, and we discuss the subsequent widening of understanding of “algorithm” and related “machines”, much in the spirit of Turing whose visions we see realized today.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Conceptual Confluence in 1936: Post and Turing
next chapter The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?
Footnotes
1
On the occasion of the Alan Turing Year 2012, a new presentation of Turing’s work, including hitherto unpublished papers, is available in the volume [5].
 
2
Among the more comprehensive sources we mention [6].
 
3
For an interesting account on the “House of Wisdom”, we recommend [11].
 
4
For a more detailed summary of Al Khwarizmi’s life see, e.g., [27].
 
5
A full presentation in facsimile with transcription to Latin is given in [26]; a translation to English in [2].
 
6
Leibniz wrote this letter [13] of 1671 to a duke and not to a colleague; hence he used German rather than Latin, with some Latin words inserted: “In Philosophia habe ich ein Mittel funden, dasjenige was Cartesius und andere per Algebram et Analysin in Arithmetica et Geometria gethan, in allen scientien zuwege zu bringen per Artem Combinatoriam […]. Dadurch alle Notiones compositae der ganzen welt in wenig simplices als deren Alphabet reduciret, und aus solches alphabets combination wiederumb alle dinge, samt ihren theorematibus, und was nur von ihnen zu inventiren müglich, ordinata methodo, mit der zeit zu finden, ein weg gebahnet wird.”
 
7
“Verbi gratia quia Homo est Animal rationale (et quia Aurum est metallum ponderosissimum) hinc si sit Animalis (metalii) numerus a ut 2 (m ut 3) Rationalis (ponderosissimi) vero numerus r ut 3 (p ut 5) erit numerus hominis seu h idem quot ar id est in hoc exemplo 2,3 seu 6 (et numerus auri solis s idem quot mp id est in hoc exemplo 3,5 seu 15.”
 
8
From [14]: “Nam ubi semel a Missionariis haec lingua introduce poterit, religio vera quae maxime rationi consentanea est, stabilia erit et non magis in posterum metuanda erit Apostasia, quam ne hominess Arithmeticam et Geometriam, quam semel dedicere, mox damnent.”
 
9
From [14]: “Aliquot selectos homines rem intra quinquennium absolvere posse puto; intra biennium autem doctrinas, magis in vita frequentalas, id est Moralem et Metaphysicam, irrefragabile calculo exhibebunt.”
 
10
“Eine Lösung dieser Aufgabe im allgemeinsten Falle dürfte vielleicht mit unüberwindlichen Schwierigkeiten verbunden sein.”
 
11
Cited from [10, p. 117].
 
12
F. Rieger, Das Gesicht unserer Gegner von morgen, Frankfurter Allgemeine Zeitung, 20th Sept. 2012.
 
13
G. Baum, Wacht auf, es geht um die Menschenwürde, Frankfurter Allgemeine Zeitung, 16th June 2013.
 
14
“Freiheit gegen Algorithmen”, Spiegel Online, 21st June 2013.
 
15
This aspect, with a focus on the role of algorithmic game theory, is developed at length by F. Schirrmacher, a leading German journalist, in [20], a bestseller on the German book market.
 
Literature
1.
L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. 21, 1–46 (1989)MathSciNetCrossRef
2.
J.N. Crossley, A.S. Henry, Thus spake al-Khwārizmī: a translation of the text of Cambridge University Library Ms. Ii.vi.5. Hist. Math. 17, 103–131 (1990)CrossRef
3.
A. Church, A note on the Entscheidungsproblem. J. Symb. Log. 1, 40–41 (1936)CrossRef
4.
A. Church, in: Summaries of the Summer Institute of Symbolic Logic. Application of recursive arithmetic to the problem of circuit synthesis, vol. I (Cornell University, Ithaca, 1957), pp. 3–50
5.
B. Cooper, J.V. Leeuwen (eds.), Alan Turing: His Work and Impact (Elsevier, Amsterdam, 2013)MATH
6.
M. Davis, The Universal Computer – The Road from Leibniz to Turing. Turing Centennial Edition (CRC Press, Boca Raton, 2012)
7.
K. Gödel, Remarks before the Princeton bicentennial conference on problems in mathematics, in Kurt Gödel, Collected Works, ed. by S. Feferman et al., vol. II (Oxford University Press, Oxford, 1990), pp. 150–153
8.
Y. Gurevich, Sequential abstract-state machines capture sequential algorithms. ACM Trans. Comput. Log. 1, 77–111 (2000)MathSciNetCrossRef
9.
H. Herring (ed.), G.W. Leibniz Schriften zur Logik und zur philosophischen Grundlegung von Mathematik und Naturwissenschaft (lat. u. deutsch) (Suhrkamp, Frankfurt, 1996)
10.
11.
J. Al-Khalili, The House of Wisdom: How Arabic Science Saved Ancient Knowledge and Gave Us the Renaissance (Penguin Press, New York, 2011)
12.
S.C. Kleene, Representation of events in nerve nets and finite automata, in Automata Studies, ed. by C.E. Shannon, J. McCarthy (Princeton University Press, Princeton, 1956), pp. 3–41
13.
G.W. Leibniz, Brief an Herzog Johann Friedrich von Braunschweig-Lüneburg (Okt. 1671), in Philosophische Schriften von Gottfried Wilhelm Leibniz, ed. by C.I. Gerhardt, vol. 1 (Weidmannsche Buchhandlung, Berlin, 1875), pp. 57–58
14.
G.W. Leibniz, Anfangsgründe einer allgemeinen Charakteristik, in [9], pp. 39–57
15.
G.W. Leibniz, Ein nicht unelegantes Beispiel abstrakter Beweisführung, in [9], pp. 153–177
16.
G.W. Leibniz, Elemente eines Kalküls, in [9], pp. 67–91
17.
E.L. Post, Finite combinatory processes – formulation 1. J. Symb. Log. 1, 103–105 (1936)CrossRef
18.
E.L. Post, Recursively enumerable sets of positive integers and their decision problems. Bull. Am.. Math. Soc. 50, 284–316 (1944)MathSciNetCrossRef
19.
20.
F. Schirrmacher, EGO: Das Spiel des Lebens (Karl Blessing-Verlag, München, 2013)
21.
M. Steinby, W. Thomas, Trees and term rewriting in 1910: on a paper by Axel Thue. Bull. Eur. Assoc. Theor. Comput. Sci. 72, 256–269 (2000)MathSciNet
22.
W. Thomas. Infinite games and verification, in Proceedings of International Conference on Computer Aided Verification CAV’02. Lecture Notes in Computer Science, vol. 2404 (Springer, Berlin, Heidelberg, New York, 2002), pp. 58–64
23.
A. Thue, Über die Lösung eines Spezialfalls eines allgemeinen logischen problems. Kristiania Videnskabs-Selskabets Skrifter. I. Mat. Nat. Kl. 1910, No. 8
24.
A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42, 230–265 (1936)MathSciNetMATH
25.
26.
K. Vogel, Mohammed ibn Musa Alchwarizmi’s Algorismus. Das früheste Lehrbuch zum Rechnen mit indischen Ziffern (Zeller, Aalen, 1963)
27.
H. Zemanek, Dixit algorizmi: his background, his personality, his work, and his influence, in Algorithms in Modern Mathematics and Computer Science, ed by A Ershov, D Knuth. Proceedings, Urgench, Uzbek SSR, 16–22 September 1979. Springer Lecture Notes in Computer Science, vol. 122 (Springer, Berlin, 1981), pp. 1–81
Metadata
Title
Algorithms: From Al-Khwarizmi to Turing and Beyond
Author
Wolfgang Thomas
Copyright Year
2015
Publisher
Springer International Publishing
Book
Turing’s Revolution

Print ISBN: 978-3-319-22155-7

Electronic ISBN: 978-3-319-22156-4

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-22156-4_2

Premium Partner

    Image Credits