Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Prolog Kapitel lesen Erstes Kapitel lesen

2024 | OriginalPaper | Buchkapitel

12. Berechenbarkeit: Post, Gödel, Church, Turing (und viele andere)

verfasst von : William D. Brewer

Erschienen in: Kurt Gödel

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Zusammenfassung

Kurt Gödels Arbeit hatte weitreichende Auswirkungen, über die eher spezialisierten Bereiche der mathematischen Logik und Grundlagen der Mathematik hinaus. Es war schon lange ein Traum von Wissenschaftlern, Mathematikern und Philosophen, ‚Rechenmaschinen‘ zu bauen, die im einfachsten Fall mathematische Berechnungen automatisieren würden: zunächst die einfachen Operationen von Addition und Multiplikation. Nach der Entwicklung von Präzisionsuhrwerken im späten 17. Jahrhundert schien dieser Traum in greifbarer Nähe zu sein. Gödels zeitweiliger Held Gottfried Wilhelm Leibniz baute tatsächlich eine solche Rechenmaschine (um 1670–1700) mit Zahnrädern und Sperrklinken, sowie eine Verschlüsselungsmaschine. Seine Rechenmaschine (Multiplikationsmaschine) erweiterte Ideen, die von Blaise Pascal vorgeschlagen wurden, und wurde als ‚Stepped Reckoner‘ bezeichnet (siehe Abb. 12.1). Leibniz selbst wird mit der eher elitären Aussage zitiert: „... es ist unter der Würde ausgezeichneter Männer, ihre Zeit mit Berechnungen zu verschwenden, wenn jeder Bauer die Arbeit mit Hilfe einer Maschine genauso präzise erledigen könnte“.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Übergangsjahre, 1935–39 – eine Zeit der Unsicherheit
Nächstes Kapitel 1940: Eine lange Reise nach Osten in den Westen
Fußnoten
1
Siehe Kidwell und Williams (1992).
 
2
Siehe Copeland et al., (Hrsg., 2013) (CPS), Ref. 39 in Anhang B.
 
3
Dieses Problem wurde zuerst von Leibniz behandelt, der eine Maschine konstruieren wollte, die den Wahrheitswert einer beliebigen Aussage in der symbolischen Logik feststellen könnte (er versuchte später, eine solche Maschine zu entwickeln).
 
4
Die Dissertation wurde in den Proceedings of the London Mathematical Society veröffentlicht; vgl. Turing (1939).
 
5
[Turing (1954)]: ‚Solvable and unsolvable problems‘, ein populärwissenschaftlicher Artikel in der Science News (1954).
 
6
Vgl. Davis (1982).
 
7
Siehe M. Davis, Einleitung zu [Gödel *193?] in den Collected Works, Vol. III (1995), S. 156–163.
 
8
Church (1937).
 
9
Hier aus Stillwell (2004), S. 9 adaptiert.
 
10
Siehe Post (1936).
 
11
Schmidhuber (2021); im Internet bei: https://​people.​idsia.​ch/​~juergen/​goedel-1931-begruender-theoretische-informatik-KI.​html (angesehen am 15.11.2021), und siehe auch den Artikel in der FAZ, 16.06.2021: 
‚Als Kurt Gödel die Grenzen des Berechenbaren entdeckte‘. [Schmidthuber (2021)].
 
12
Sieg (2005), S. 180.
 
13
Gödel (1934), in Davis (Hrsg., 1965), S. 44. Diese Fußnote ist berühmt/berüchtigt, da sie zuerst als Vorwegnahme von Churchs Thesis interpretiert wurde. Gödel hat später dieser Idee widersprochen, wie von Sieg (2005, Fußnote [11] auf S. 181) klargestellt: „Godel wies in den 60er-Jahre mit Nachdruck [die Idee] zurück (in einem Brief an Martin Davis), dass seine Formulierung eine Form von Churchs Thesis vorwegnimmt: er war nicht überzeugt, dass sein Begriff der Rekursion der allgemeinste wäre“.
 
14
Vgl. Wang (1974), Ref. 2 im Anhang B, S. 325.
 
15
Nagel und Newman (1956), zitiert von S. 86.
 
16
Vgl. Lucas (1961).
 
17
Siehe z. B. H.T. Siegelmann, ‚Computation Beyond the Turing Limit‘, in: Science, Band 238, Nr. 28 (2012), S. 632–637; oder auch J. Cabessa und H.T. Siegelmann, ‚The Computational Power of Interactive Recurrent Neural Networks‘, in: Neural Computation, Band 24, Nr. 4 (1995), S. 996–1019.
 
18
Vgl. Davis (1993).
 
19
Wir sind diesem Satz bereits in Kap. 10 begegnet (Abschnitt über ‚Gödels erster Aufenthalt am IAS‘). Dawson und andere Autoren haben darauf hingewiesen, dass er nicht eindeutig ist (aufgrund der Platzierung eines Kommas im englischen Original, nach dem Wort ‚Platonism‘) – vielleicht wegen Gödels mangelnde Erfahrung mit der englischen Sprache zu jener Zeit.
 
Literatur
Chaitin 2007: ‘Thinking about Gödel and Turing’. Gregory J. Chaitin, World Scientific, Singapore (2007). ISBN 9-812-7-0897-9.
Church 1936: ‘An Unsolvable Problem of Elementary Number Theory’. Alonzo Church, in: der American Journal of Mathematics, Band 58, Nr. 2 (1936), S. 345–363.
Church 1937: ‚Rezension von “On Computable Numbers, with an Application to the Entscheidungsproblem”, by A.M. Turing‘. Alonzo Church, in: Journal of Symbolic Logic, Band 2, Nr. 1 (1937), S. 42–43.
Copeland et al., Hrsg. (2013): ‘Computability: Turing, Gödel, Church and Beyond’. B. Jack Copeland, Carl J. Posy, und Oron Shagrir, Hrsg., MIT Press, Cambridge MA (2013). ISBN 978-0-262-0-1899-3. Siehe auch Anhang B, Ref. 39 (CPS).
Davis, Hrsg. (1965): The Undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Hrsg. Martin Davis, Raven Press, Hewlitt NY (1965). ISBN: 0-486-43228-9.
Davis 1982: ‘Why Gödel Didn’t Have Church’s Thesis’. Martin Davis, in: Information and Control, Band 54 (1982), S. 3–24.
Davis 1993: ‘How subtle is Gödel’s theorem? More on Roger Penrose’. Martin Davis, in: Behavioral and Brain Sciences, Band 16 (1993), S. 611–612.
Feferman 1995: ‘Penrose’s Gödelian argument: A Review of Shadows of the Mind by Roger Penrose’. S. Feferman, in: Psyche, Band 2, Nr. 7 (1995), S. 21–32.
Franzén 2005: ‘Gödel’s Theorem. An Incomplete Guide to its Use and Abuse’. Torkel Franzén, CRC Press (2005). ISBN 978-1-56881-238-0.
Gödel 1930: ‚Die Vollständigkeit der Axiome des logischen Funktionenkalküls‘. Kurt Gödel, in: Monatshefte für Mathematik und Physik, Band 37 (1930), S. 349–360. Siehe auch Anhang A.
Gödel 1931: ‚Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I‘. Kurt Gödel, in: Monatshefte für Mathematik und Physik, Band 38 (1931), S. 173–198.
Gödel 1933: ‘The present situation in the foundations of mathematics’. Kurt Gödel, Collected Works, Band III, [Gödel *1933o]. Oxford University Press (1995), S. 45–53.
Gödel 1934: ‘On undecidable propositions of formal mathematical systems’. Kurt Gödel, seine ‘Princeton-Vorträge’. Veröffentlicht in Davis (Hrsg., 1965), S. 39–74.
Gödel 1939: ‘Consistency-proof for the generalized continuum-hypothesis’. Kurt Gödel, in: Bulletin of the American Mathematical Society, Band 45 (1939), S. 93.
Gödel 1939b: Gödel’s Lectures on Logic, Notre Dame (1939). Herausgegeben von Miloš Adžić und Kosta Došen, in: The Bulletin of Symbolic Logic, Band 22, Nr. 4 (Dez. 2016), S. 469–481.
Gödel 1951: ‘Some basic theorems on the foundations of mathematics and their implications’. Kurt Gödel, in den Collected Works, Band III, S. 304–323. [Gödel *1951].
Hilbert u. Ackermann 1928: Grundzüge der theoretischen Logik (HA). David Hilbert und Wilhelm Ackermann. Springer-Verlag, Heidelberg/Berlin (1928). Wiederaufgelegt 1959. Englische Übersetzung: Principles of Mathematical Logic, Hilbert u. Ackermann, Übers. L.M. Hammond, G.G. Leckie, und F. Steinhardt. AMS Chelsea Publishing, Providence RI (1999). ISBN 978-0-8218-2024-7.
Hintikka 2005: ‘What Platonism? Reflections on the thought of Kurt Gödel’. Jaakko Hintikka, in: Revue internationale de philosophie, Band 2005/4 (Nr. 234), S. 535–552.
Hofstadter 1979: Gödel, Escher, Bach. An Eternal Golden Braid. Douglas R. Hofstadter, Penguin Philosophy Series (1979) (reprinted 1980). ISBN: 978-0-465-02685-2. GEB was re-issued in 1999. Siehe Ref. 3 in Anhang B. Die erste deutsche Auflage erschien 1985; vgl. Anhang B.
Hofstadter 2007: ‘I am a Strange Loop‘. Douglas R. Hofstadter, Basic Books, NY (2007). ISBN: 978-0-465-03078-1. Deutsche Auflage s. Anhang B, Ref. 3.
Kidwell u. Williams 1992: 'The Calculating Machines', Hrsg. P.A. Kidwell und M.R. Williams, MIT Press, Cambridge MA und London (1992). ISBN: 0-262-13278-8. Original: 'Die Rechenmaschinen und ihre Entwicklungsgeschichte', Ernst Martin, Burghagen (1925), 1936 u. 1992 wieder aufgelegt.Kleene u. Post 1954: ‘The upper semi-lattice of degrees of recursive unsolvability’. S.C. Kleene mit E.L. Post, in: Annals of Mathematics, Band 59 (1954), S. 379–407.
Lucas 1961: ‘Minds, Machines, and Gödel’. John R. Lucas, in: Philosophy, Band XXXVI (1961), S. 112–127. Wiederverwendet in Büchern von 1963 und 1964.
Nagel u. Newman 1956: Gödel’s Proof. Ernest Nagel und James R. Newman, in Scientific American, Band 194, Nr. 6 (June 1956), S. 71–90.
Nagel u. Newman 1958: Gödel’s Proof. Ernest Nagel and James R. Newman. NYU Press, 2001. (Ursprünglich 1958 publiziert; wiederaufgelegt 2001, 2005, 2008). ISBN 978-0-814-75816-8.
Post 1936: ‘Finite combinatory Processes – Formulation 1.’. Emil L. Post, in: The Journal of Symbolic Logic, Band 1, Nr. 3 (Sept. 1936), S. 103–105.
Post 1944: ‘Recursively enumerable sets of positive integers and their decision problems’. Emil Leon Post, in: Bulletin of the American Mathematical Society, Band 50, Nr. 5 (1944), S. 284–316.
Sieg 2005: ‘Only Two Letters: The Correspondence between Herbrand and Gödel’. Wilfried Sieg, in: The Bulletin of Symbolic Logic, Band 11, Nr. 2 (June 2005), S. 172–184.
Sieg 2006: ‘Gödel on Computability’. Wilfried Sieg, in: Philosophia Mathematica, Band 14, Nr. 2 (2006), S. 189–207.
Stillwell 2004: ‘Emil Post and His Anticipation of Gödel and Turing’. John Stillwell, in: Mathematics Magazine, Band 77, Nr. 1 (February 2004), S. 3–14.
Turing 1936: ‘On Computable Numbers, with Application to the “Entscheidungsproblem”’. Alan M. Turing, in: Proceedings of the London Mathematical Society, Band 42 (1937), S. 230–265. (Eingereicht am 28. Mai 1936).
Turing 1939: ‘Systems of logic based on ordinals’. A.M. Turing, in: The Proceedings of the London Mathematical Society (Serie 2), Band 45 (1939), S. 161–228.
Turing 1950: ‘Computing Machinery and Intelligence’. Alan M. Turing, in: Mind. A Quarterly Review of Psychology and Philosophy, Band LIX, Nr. 236 (October 1950), S. 433–460.
Turing 1954: ‘Solvable and unsolvable problems’. Alan M. Turing, in: Science News, Band 31 (1954), S. 7–23.
Wang 1974: From Mathematics to Philosophy, Hao Wang. Routledge (1974). ISBN 978-1138-68773-8.
Metadaten
Titel
Berechenbarkeit: Post, Gödel, Church, Turing (und viele andere)
verfasst von
William D. Brewer
Copyright-Jahr
2024
Buch
Kurt Gödel

Print ISBN: 978-3-031-43150-0

Electronic ISBN: 978-3-031-43151-7

Copyright-Jahr: 2024

DOI
https://doi.org/10.1007/978-3-031-43151-7_12

Premium Partner

    Bildnachweise