Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2022 | OriginalPaper | Buchkapitel

3. Theoretische Grenzen

verfasst von: Klaus Mainzer, Reinhard Kahle

Erschienen in: Grenzen der KI – theoretisch, praktisch, ethisch

Verlag: Springer Berlin Heidelberg

share
TEILEN

Zusammenfassung

Maschinelles Lernen mit probabilistischen Algorithmen erweist sich zum Erlernen elementarer Rechenregeln als ungeeignet. Aber auch bei anspruchsvollen zahlentheoretischen Problemen sind statistische Regelmäßigkeiten nicht zielführend (3.1). Mathematisches Hintergrundwissen ist grundlegend, um Sicherheit in der Kryptologie zu garantieren. Das wird an Beispielen von RSA- und elliptischen Kryptosystemen bis zur Quantenkryptologie (z. B. Shor-Algorithmus) gezeigt. Interaktive Beweissysteme hängen von anspruchsvollen mathematischen Theorien und Theoremen ab (3.2). Das gilt auch für die häufig im Zusammenhang von KI gestellte Frage, ob deterministische Computer Zufall (und damit Kreativität?) und Chaos erzeugen können (3.3-3.4). Am Ende gibt es nicht „die“ Intelligenz. Vielmehr lassen sich Grade der Fähigkeit zur Problemlösung unterscheiden, die von Graden der Berechenbarkeit und Komplexität von Problemen abhängen (3.5).
Fußnoten
1
Dennoch hat die Idee, die dem Sieb des Eratosthenes zugrunde liegt, einen algorithmischen Mehrwert, siehe das Beispiel unten auf S. 64 in der Diskussion kryptographischer Protokolle.
 
2
Tatsächlich gibt es inzwischen Algorithmen, die eine „direkte“ Berechnung der Nachkommastellen von \(\pi \) in hexadezimaler und binärer Schreibweise erlauben, [3, § 1.2]. Damit wird aber noch immer keine Regelmäßigkeit der Nachkommastellen im üblichen Sinne begründet.
 
3
Die folgende Darstellung der Chaostheorie folgt dem Buch K. Mainzer, Information: Algorithmus-Wahrscheinlichkeit-Komplexität-Quantenwelt-Leben-Gehirn-Gesellschaft, Berlin University Press 2016, [26, S. 67 ff.].
 
Literatur
1.
Zurück zum Zitat Reinhard Kahle. (2021). Primzahlen als Herausforderung. In R. Reussner, A. Koziolek, and R. Heinrich, Herausgeber, INFORMATIK 2020, Lecture Notes in Informatics, S. 719–727. Gesellschaft für Informatik. Reinhard Kahle. (2021). Primzahlen als Herausforderung. In R. Reussner, A. Koziolek, and R. Heinrich, Herausgeber, INFORMATIK 2020, Lecture Notes in Informatics, S. 719–727. Gesellschaft für Informatik.
2.
Zurück zum Zitat Richard Hoche, (Hrsg.) (1866). Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II. Teubner. Richard Hoche, (Hrsg.) (1866). Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II. Teubner.
3.
Zurück zum Zitat Lennart Berggren; Jonathan Borwein; Peter Borwein. (2004). A Pamphlet on Pi. In Lennart Berggren, Jonathan Borwein, und Peter Borwein (Herausgeber). Pi: A Source Book. 3. Auflage, Springer, 721–739. Lennart Berggren; Jonathan Borwein; Peter Borwein. (2004). A Pamphlet on Pi. In Lennart Berggren, Jonathan Borwein, und Peter Borwein (Herausgeber). Pi: A Source Book. 3. Auflage, Springer, 721–739.
4.
Zurück zum Zitat Leonhard Euler. (1772). Extrait d’un lettre de M. Euler le pere à M. Bernoulli concernant le Mémoire imprimé parmi ceux de 1771. p. 318. Nouveaux Mémoires de l’Académie royale des Sciences. Berlin, 1774:35–36. Leonhard Euler. (1772). Extrait d’un lettre de M. Euler le pere à M. Bernoulli concernant le Mémoire imprimé parmi ceux de 1771. p. 318. Nouveaux Mémoires de l’Académie royale des Sciences. Berlin, 1774:35–36.
5.
Zurück zum Zitat Hermann Weyl. (1971). Über den Symbolismus der Mathematik und mathematischen Physik. In K. Reidemeister, Herausgeber, Hilbert, S. 20–38. Springer. Hermann Weyl. (1971). Über den Symbolismus der Mathematik und mathematischen Physik. In K. Reidemeister, Herausgeber, Hilbert, S. 20–38. Springer.
6.
Zurück zum Zitat Homeister, M. (2018). Quantum Computing verstehen, Springer: Berlin 5. Aufl., 195–196. Homeister, M. (2018). Quantum Computing verstehen, Springer: Berlin 5. Aufl., 195–196.
7.
Zurück zum Zitat Pomerance, C. (1982). Analysis and comparison of some integer factoring algorithms, in: Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 89–139 Pomerance, C. (1982). Analysis and comparison of some integer factoring algorithms, in: Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 89–139
8.
Zurück zum Zitat Crandall, R.; Pomerance, C. (2001). Prime Numbers: A Computational Perspective. Springer, New York. CrossRef Crandall, R.; Pomerance, C. (2001). Prime Numbers: A Computational Perspective. Springer, New York. CrossRef
9.
Zurück zum Zitat Lenstra, A.K.; Lenstra, H.W. (1993). The Development of the Number Field Sieve, Lecture Notes in Mathematics V, 1554. Lenstra, A.K.; Lenstra, H.W. (1993). The Development of the Number Field Sieve, Lecture Notes in Mathematics V, 1554.
10.
Zurück zum Zitat Werner, A. (2002). Elliptische Kurven in der Kryptographie, Springer, Berlin. CrossRef Werner, A. (2002). Elliptische Kurven in der Kryptographie, Springer, Berlin. CrossRef
12.
Zurück zum Zitat Shor, P.W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, in: SIAM J. Computing 26, 1484–1509 Shor, P.W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, in: SIAM J. Computing 26, 1484–1509
13.
Zurück zum Zitat Ekert, A.,; Jozsa, R. (1996). Quantum computation and Shor’s factoring algorithm, in: Rev. mod. Phys. 68. Ekert, A.,; Jozsa, R. (1996). Quantum computation and Shor’s factoring algorithm, in: Rev. mod. Phys. 68.
14.
Zurück zum Zitat Benenti, G.; Casati, G.; Strini, G. (2008). Principles of Quantum Computation and Information. Vol. I: Basic Concepts, World Scientific Singapore, 161–162. Benenti, G.; Casati, G.; Strini, G. (2008). Principles of Quantum Computation and Information. Vol. I: Basic Concepts, World Scientific Singapore, 161–162.
15.
Zurück zum Zitat Quisquater, J.-J.; Guillou, L. (1990). How to explain zero-knowledge protocols to your children, in: Advances in Cryptology – CRYPTO, 89, Lecture Notes in computer Science 435, 628–631. Quisquater, J.-J.; Guillou, L. (1990). How to explain zero-knowledge protocols to your children, in: Advances in Cryptology – CRYPTO, 89, Lecture Notes in computer Science 435, 628–631.
16.
Zurück zum Zitat Köbler, J.; Beyersdorff, O. (2006). Von der Turingmaschine zum Quantencomputer - ein Gang durch die Geschichte der Komplexitätstheorie, in: W. Reisig, J.-C. Freytag (Hrsg.), Informatik. Aktuelle Themen im historischen Kontext, Springer: Berlin. Köbler, J.; Beyersdorff, O. (2006). Von der Turingmaschine zum Quantencomputer - ein Gang durch die Geschichte der Komplexitätstheorie, in: W. Reisig, J.-C. Freytag (Hrsg.), Informatik. Aktuelle Themen im historischen Kontext, Springer: Berlin.
17.
Zurück zum Zitat Babai, L. (1985). Trading group theory for randomness, in: Proc. 17th ACM Symposium on Theory of Computing, ACM Press, 421–429. Babai, L. (1985). Trading group theory for randomness, in: Proc. 17th ACM Symposium on Theory of Computing, ACM Press, 421–429.
18.
Zurück zum Zitat Goldreich, O.; Micali, S.; Rackoff, C. (1989). The knowledge complexity of interactive proof systems, in: SIAM Journal on Computing 18(2), 186–208. Goldreich, O.; Micali, S.; Rackoff, C. (1989). The knowledge complexity of interactive proof systems, in: SIAM Journal on Computing 18(2), 186–208.
19.
Zurück zum Zitat Goldberg, A.; Sipser, M. (1989). Private coins versus public coins in interactive proof systems, in: S. Micli (Hrsg.), Randomness and Computation, Advances in Computing Research 5, JAI Press, 73–90. Goldberg, A.; Sipser, M. (1989). Private coins versus public coins in interactive proof systems, in: S. Micli (Hrsg.), Randomness and Computation, Advances in Computing Research 5, JAI Press, 73–90.
21.
Zurück zum Zitat Feige, U.; Goldwasser, S.; Lovasz, L.; Safra, S.; Szegedy, M. (1996). Interactive proofs and the hardness of approximating cliques, in: Journal of the ACM 43, 268–292. MathSciNetCrossRef Feige, U.; Goldwasser, S.; Lovasz, L.; Safra, S.; Szegedy, M. (1996). Interactive proofs and the hardness of approximating cliques, in: Journal of the ACM 43, 268–292. MathSciNetCrossRef
22.
Zurück zum Zitat Arora, S.; Safra, S. (1998). Probabilistic checking of proof: A new characterization of NP, in: Journal of ACM 45(1), 70–122. MathSciNetCrossRef Arora, S.; Safra, S. (1998). Probabilistic checking of proof: A new characterization of NP, in: Journal of ACM 45(1), 70–122. MathSciNetCrossRef
23.
Zurück zum Zitat Papadimitriou, C.H.; Yannakakis, M. (1991). Optimization, approximation, and complexity classes, in: Journal of Computer and System Sciences 43(3), 425–440. MathSciNetCrossRef Papadimitriou, C.H.; Yannakakis, M. (1991). Optimization, approximation, and complexity classes, in: Journal of Computer and System Sciences 43(3), 425–440. MathSciNetCrossRef
24.
Zurück zum Zitat Nissan, N.; Widgerson, A. (1994). Hardness vs. randomness, in: Journal of Computer and System Sciences 49(2), 149–167 Nissan, N.; Widgerson, A. (1994). Hardness vs. randomness, in: Journal of Computer and System Sciences 49(2), 149–167
25.
Zurück zum Zitat Impagliazzo, R.; Widgerson, A. (1997). P=BPP unless E has sub-exponential circuits: derandomizing the XOR lemma, in: Proc. 29th ACM Symposium on Theory of Computing, ACM Press, 220–229. Impagliazzo, R.; Widgerson, A. (1997). P=BPP unless E has sub-exponential circuits: derandomizing the XOR lemma, in: Proc. 29th ACM Symposium on Theory of Computing, ACM Press, 220–229.
26.
Zurück zum Zitat Mainzer, K. (2016). Information: Algorithmus-Wahrscheinlichkeit-Komplexität-Quantenwelt-Leben-Gehirn-Gesellschaft. Berlin. Mainzer, K. (2016). Information: Algorithmus-Wahrscheinlichkeit-Komplexität-Quantenwelt-Leben-Gehirn-Gesellschaft. Berlin.
27.
Zurück zum Zitat Dershowitz, N. (2005). The four sons of Penrose. In G. Sutcliffe and A. Voronkov (Eds.), Proceedings of the Eleventh Conference on Logic Programming for Artificial Intelligence and Reasoning (LPAR) (Montego Bay, Jamaica), Volume 3835 of Lecture Notes in Artificial Intelligence, pp. 125–138. Springer. Dershowitz, N. (2005). The four sons of Penrose. In G. Sutcliffe and A. Voronkov (Eds.), Proceedings of the Eleventh Conference on Logic Programming for Artificial Intelligence and Reasoning (LPAR) (Montego Bay, Jamaica), Volume 3835 of Lecture Notes in Artificial Intelligence, pp. 125–138. Springer.
28.
Zurück zum Zitat Mainzer, K. (2018). The Digital and the Real World. Computational Foundations of Mathematics, Science, Technology, and Philosophy, World Scientific Singapore. Mainzer, K. (2018). The Digital and the Real World. Computational Foundations of Mathematics, Science, Technology, and Philosophy, World Scientific Singapore.
29.
Zurück zum Zitat Hidary, J.D. (2019). Quantum Computing: An Applied Approach, Springer: Cham, 20–21. CrossRef Hidary, J.D. (2019). Quantum Computing: An Applied Approach, Springer: Cham, 20–21. CrossRef
30.
Zurück zum Zitat Solovay, R.; Strassen, V. (1977). A fast Monte-Carlo test for primality, in: SIAM Journal on Computing 6, 84–85. MathSciNetCrossRef Solovay, R.; Strassen, V. (1977). A fast Monte-Carlo test for primality, in: SIAM Journal on Computing 6, 84–85. MathSciNetCrossRef
31.
Zurück zum Zitat Toda, S. (1991). PP is as hard as the polynomial-time hierarchy, in: SIAM Journal on Computing 20, 865–877. MathSciNetCrossRef Toda, S. (1991). PP is as hard as the polynomial-time hierarchy, in: SIAM Journal on Computing 20, 865–877. MathSciNetCrossRef
32.
Zurück zum Zitat Adleman, L.; Huang, M. (1987). Recognizing primes in random polynomial time, in: Proc. 19th ACM Symposium on theory of computing, ACM Press, 462–469. Adleman, L.; Huang, M. (1987). Recognizing primes in random polynomial time, in: Proc. 19th ACM Symposium on theory of computing, ACM Press, 462–469.
33.
Zurück zum Zitat Rabin, M.O. (1980). Probabilistic algorithm for testing primality, in: Journal of Number Theory 12(1), 128–138. MathSciNetCrossRef Rabin, M.O. (1980). Probabilistic algorithm for testing primality, in: Journal of Number Theory 12(1), 128–138. MathSciNetCrossRef
34.
Zurück zum Zitat Mainzer, K. (2020). Quantencomputer. Von der der Quantenwelt zur Künstlichen Intelligenz, Springer: Berlin. CrossRef Mainzer, K. (2020). Quantencomputer. Von der der Quantenwelt zur Künstlichen Intelligenz, Springer: Berlin. CrossRef
Metadaten
Titel
Theoretische Grenzen
verfasst von
Klaus Mainzer
Reinhard Kahle
Copyright-Jahr
2022
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-65011-0_3

Premium Partner