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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Cognitive Computation
Erschienen in: Cognitive Computation 2/2009

01.06.2009

Ultimate Cognition à la Gödel

verfasst von: Jürgen Schmidhuber

Erschienen in: Cognitive Computation | Ausgabe 2/2009

Einloggen

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

search-config
loading …

Abstract

“All life is problem solving,” said Popper. To deal with arbitrary problems in arbitrary environments, an ultimate cognitive agent should use its limited hardware in the “best” and “most efficient” possible way. Can we formally nail down this informal statement, and derive a mathematically rigorous blueprint of ultimate cognition? Yes, we can, using Kurt Gödel’s celebrated self-reference trick of 1931 in a new way. Gödel exhibited the limits of mathematics and computation by creating a formula that speaks about itself, claiming to be unprovable by an algorithmic theorem prover: either the formula is true but unprovable, or math itself is flawed in an algorithmic sense. Here we describe an agent-controlling program that speaks about itself, ready to rewrite itself in arbitrary fashion once it has found a proof that the rewrite is useful according to a user-defined utility function. Any such a rewrite is necessarily globally optimal—no local maxima!—since this proof necessarily must have demonstrated the uselessness of continuing the proof search for even better rewrites. Our self-referential program will optimally speed up its proof searcher and other program parts, but only if the speed up’s utility is indeed provable—even ultimate cognition has limits of the Gödelian kind.
Vorheriger Artikel Recruitment and Consolidation of Cell Assemblies for Words by Way of Hebbian Learning and Competition in a Multi-Layer Neural Network
Nächster Artikel Time-Scale Feature Extractions for Emotional Speech Characterization

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
Fußnoten
1
Or `Goedel machine’, to avoid the Umlaut. But ‘Godel machine’ would not be quite correct. Not to be confused with what Penrose calls, in a different context, ‘Gödel’s putative theorem-proving machine’ [36]!
 
2
Turing reformulated Gödel’s unprovability results in terms of TMs [74] which subsequently became the most widely used abstract model of computation. It is well known that there are universal TMs that in a certain sense can emulate any other TM or any other known computer. Gödel’s integer-based formal language can be used to describe any universal TM, and vice versa.
 
3
We see that certain parts of the current s may not be directly observable without changing the observable itself. Sometimes, however, axioms and previous observations will allow the Gödel machine to deduce time-dependent storage contents that are not directly observable. For instance, by analyzing the code being executed through instruction pointer IP in the example above, the value of IP at certain times may be predictable (or postdictable, after the fact). The values of other variables at given times, however, may not be deducible at all. Such limits of self-observability are reminiscent of Heisenberg’s celebrated uncertainty principle [16], which states that certain physical measurements are necessarily imprecise, since the measuring process affects the measured quantity.
 
Literatur
1.
Aleksander I. The world in my mind, my mind in the world: key mechanisms of consciousness in humans, animals and machines. Exeter: Imprint Academic; 2005.
2.
Baars B, Gage NM. Cognition, brain and consciousness: an introduction to cognitive neuroscience. London: Elsevier/Academic Press; 2007.
3.
Banzhaf W, Nordin P, Keller RE, Francone FD. Genetic programming—an introduction. San Francisco, CA: Morgan Kaufmann Publishers; 1998.
4.
Bellman R. Adaptive control processes. NY: Princeton University Press; 1961.
5.
Blum M. A machine-independent theory of the complexity of recursive functions. J ACM. 1967;14(2):322–36.CrossRef
6.
Blum M. On effective procedures for speeding up algorithms. J ACM. 1971; 18(2):290–305.CrossRef
7.
Butz M. How and why the brain lays the foundations for a conscious self. Constructivist Found. 2008; 4(1):1–14.
8.
Cantor G. Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen. Crelle’s Journal für Mathematik 1874; 77:258–63.
9.
Chaitin GJ. A theory of program size formally identical to information theory. J ACM. 1975; 22:329–40.CrossRef
10.
Clocksin WF, Mellish CS. Programming in Prolog. 3rd ed. NY: Springer-Verlag; 1987.
11.
Cramer NL. A representation for the adaptive generation of simple sequential programs. In: Grefenstette, JJ, editor, Proceedings of an international conference on genetic algorithms and their applications, Carnegie-Mellon University, July 24–26. Hillsdale, NJ: Lawrence Erlbaum Associates; 1985.
12.
13.
Fitting MC. First-order logic and automated theorem proving. Graduate texts in computer science. 2nd ed. Berlin: Springer-Verlag; 1996.
14.
Gödel K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 1931;38:173–98.CrossRef
15.
Haikonen P. The cognitive approach to conscious machines. London: Imprint Academic; 2003.
16.
Heisenberg W. Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik. Zeitschrift für Physik 1925;33:879–93.CrossRef
17.
Hochreiter S, Younger AS, Conwell PR. Learning to learn using gradient descent. In Lecture Notes on Computer Science 2130, Proceedings of the international conference on artificial neural networks (ICANN-2001). Heidelberg: Springer; 2001. p. 87–94.
18.
Hofstadter DR. Gödel, Escher, Bach: an eternal golden braid. NY: Basic Books; 1979.
19.
Holland JH. Properties of the bucket brigade. In: Proceedings of an international conference on genetic algorithms. Hillsdale, NJ: Lawrence Erlbaum; 1985.
20.
Hutter M. Towards a universal theory of artificial intelligence based on algorithmic probability and sequential decisions. In: Proceedings of the 12th European conference on machine learning (ECML-2001); 2001. p. 226–38 (On J. Schmidhuber’s SNF grant 20-61847).
21.
Hutter M. The fastest and shortest algorithm for all well-defined problems. Int J Found Comput Sci. 2002;13(3):431–43 (On J. Schmidhuber’s SNF grant 20-61847).CrossRef
22.
Hutter M. Self-optimizing and Pareto-optimal policies in general environments based on Bayes-mixtures. In: Kivinen J and Sloan RH, editors. Proceedings of the 15th annual conference on computational learning theory (COLT 2002), Lecture Notes in Artificial Intelligence. Sydney, Australia: Springer; 2002. p. 364–79 (On J. Schmidhuber’s SNF grant 20-61847).
23.
Hutter M. Universal artificial Intelligence: sequential decisions based on algorithmic probability. Berlin: Springer; 2004.
24.
Kaelbling LP, Littman ML, Moore AW. Reinforcement learning: a survey. J AI Res. 1996;4:237–85.
25.
Kolmogorov AN. Grundbegriffe der Wahrscheinlichkeitsrechnung. Berlin: Springer; 1933.
26.
Kolmogorov AN. Three approaches to the quantitative definition of information. Probl Inf Transm. 1965;1:1–11.
27.
Lenat D. Theory formation by heuristic search. Mach Learn. 1983;21.
28.
Levin LA. Universal sequential search problems. Probl Inf Transm. 1973;9(3):265–66.
29.
Levin LA. Laws of information (nongrowth) and aspects of the foundation of probability theory. Probl Inf Transm. 1974;10(3):206–10.
30.
Levin LA. Randomness conservation inequalities: information and independence in mathematical theories. Inf Control. 1984;61:15–37.CrossRef
31.
Li M, Vitányi PMB. An introduction to Kolmogorov complexity and its applications. 2nd ed. NY: Springer; 1997.
32.
Löwenheim L. Über Möglichkeiten im Relativkalkül. Mathematische Annalen. 1915;76:447–70.CrossRef
33.
Mitchell T. Machine learning. NY: McGraw Hill; 1997.
34.
Moore CH, Leach GC. FORTH—a language for interactive computing. Amsterdam: Mohasco Industries Inc.; 1970.
35.
Newell A, Simon H. GPS, a program that simulates human thought. In: Feigenbaum E, Feldman J, editors. Computers and thought. New York: McGraw-Hill; 1963. p. 279–93.
36.
Penrose R. Shadows of the mind. Oxford: Oxford University Press; 1994.
37.
Popper KR. All life is problem solving. London: Routledge; 1999.
38.
Rice HG. Classes of recursively enumerable sets and their decision problems. Trans Am Math Soc. 1953;74:358–66.CrossRef
39.
Rosenbloom PS, Laird JE, Newell A. The SOAR papers. Cambridge: MIT Press; 1993.
40.
Samuel AL. Some studies in machine learning using the game of checkers. IBM J Res Dev. 1959;3:210–29.CrossRef
41.
Schmidhuber J. Evolutionary principles in self-referential learning. Diploma thesis, Institut für Informatik, Technische Universität München; 1987.
42.
Schmidhuber J. Dynamische neuronale Netze und das fundamentale raumzeitliche Lernproblem. Dissertation, Institut für Informatik, Technische Universität München; 1990.
43.
Schmidhuber J. Reinforcement learning in Markovian and non-Markovian environments. In: Lippman DS, Moody JE, Touretzky DS, editors. Advances in neural information processing systems 3 (NIPS 3). San Francisco, CA: Morgan Kaufmann; 1991. p. 500–6.
44.
Schmidhuber J. A self-referential weight matrix. In: Proceedings of the international conference on artificial neural networks. Amsterdam: Springer; 1993. p. 446–51.
45.
Schmidhuber J. Discovering solutions with low Kolmogorov complexity and high generalization capability. In: Prieditis A, Russell S, editors. Machine learning: Proceedings of the twelfth international conference. San Francisco, CA: Morgan Kaufmann Publishers; 1995. p. 488–96.
46.
Schmidhuber J. A computer scientist’s view of life, the universe, and everything. In: Freksa C, Jantzen M, Valk R, editors. Foundations of computer science: potential-theory-cognition, vol 1337. Lecture Notes in Computer Science. Berlin: Springer; 1997. p. 201–8.
47.
Schmidhuber J. Discovering neural nets with low Kolmogorov complexity and high generalization capability. Neural Netw. 1997;10(5):857–73.PubMedCrossRef
48.
Schmidhuber J. Algorithmic theories of everything. Technical Report IDSIA-20-00, quant-ph/0011122, IDSIA, Manno (Lugano), Switzerland. Sections 1–5: see [50]; Section 6: see [51]; 2000.
49.
Schmidhuber J. Sequential decision making based on direct search. In: Sun R, Giles CL, editors. Sequence learning: paradigms, algorithms, and applications. Lecture Notes on AI 1828. Berlin: Springer; 2001.
50.
Schmidhuber J. Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. Int J Found Comput Sci. 2002;13(4):587–612.CrossRef
51.
Schmidhuber J. The speed prior: a new simplicity measure yielding near-optimal computable predictions. In: Kivinen J, Sloan RH, editors. Proceedings of the 15th annual conference on computational learning theory (COLT 2002). Lecture Notes in Artificial Intelligence. Sydney, Australia: Springer; 2002. p. 216–28.
52.
Schmidhuber J. Bias-optimal incremental problem solving. In: Becker S, Thrun S, Obermayer K, editors. Advances in neural information processing systems 15 (NIPS 15). Cambridge, MA: MIT Press; 2003. p. 1571–8.
53.
Schmidhuber J. Towards solving the grand problem of AI. In: Quaresma P, Dourado A, Costa E, Costa JF, editors. Soft computing and complex systems. Coimbra, Portugal: Centro Internacional de Mathematica; 2003. p. 77–97. Based on [58].
54.
Schmidhuber J. Optimal ordered problem solver. Mach Learn. 2004;54:211–54CrossRef
56.
Schmidhuber J. Completely self-referential optimal reinforcement learners. In: Duch W, Kacprzyk J, Oja E, Zadrozny S, editors. Artificial neural networks: biological inspirations—ICANN 2005. LNCS 3697. Berlin, Heidelberg: Springer-Verlag. 2005. p. 223–33 (Plenary talk).
56.
Schmidhuber J. Gödel machines: towards a technical justification of consciousness. In: Kudenko D, Kazakov D, Alonso E, editors. Adaptive agents and multi-agent systems III. LNCS 3394. Berlin: Springer Verlag; 2005. p. 1–23.
57.
Schmidhuber J. Gödel machines: fully self-referential optimal universal self-improvers. In: Goertzel B, Pennachin C, editors. Artificial general intelligence. Berlin: Springer Verlag; 2006. p. 199–226. Preprint available as arXiv:cs.LO/0309048.
58.
Schmidhuber J. The new AI: general & sound & relevant for physics. In: Goertzel B, Pennachin C, editors. Artificial general intelligence. Berlin: Springer; 2006. p. 175–98. Also available as TR IDSIA-04-03, arXiv:cs.AI/0302012.
59.
60.
Schmidhuber J. 2006: Celebrating 75 years of AI—history and outlook: the next 25 years. In: Lungarella M, Iida F, Bongard J, Pfeifer R, editors. 50 Years of artificial intelligence, vol LNAI 4850. Berlin, Heidelberg: Springer; 2007. p. 29–41.
61.
Schmidhuber J. Alle berechenbaren Universen (All computable universes). Spektrum der Wissenschaft Spezial (German edition of Scientific American) 2007;(3):75–9.
62.
Schmidhuber J. New millennium AI and the convergence of history. In: Duch W, Mandziuk J, editors. Challenges to computational intelligence, vol 63. Studies in Computational Intelligence, Springer; 2007. p. 15–36. Also available as arXiv:cs.AI/0606081.
63.
Schmidhuber J, Zhao J, Schraudolph N. Reinforcement learning with self-modifying policies. In: Thrun S, Pratt L, editors. Learning to learn. Netherland: Kluwer; 1997. p. 293–309.
64.
Schmidhuber J, Zhao J, Wiering M. Shifting inductive bias with success-story algorithm, adaptive Levin search, and incremental self-improvement. Mach Learn. 1997;28:105–30.CrossRef
65.
Schmidhuber J, Graves A, Gomez F, Fernandez S, Hochreiter S. How to learn programs with artificial recurrent neural networks. Cambridge: Cambridge University Press; 2009 (in preparation).
66.
Seth AK, Izhikevich E, Reeke GN, and Edelman GM. Theories and measures of consciousness: an extended framework. Proc Natl Acad Sci USA. 2006;103:10799–804.PubMedCrossRef
67.
Siegelmann HT, Sontag ED. Turing computability with neural nets. Appl Math Lett. 1991;4(6):77–80.CrossRef
68.
Skolem T. Logisch-kombinatorische Untersuchungen über Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theorem über dichte Mengen. Skrifter utgit av Videnskapsselskapet in Kristiania, I, Mat.-Nat. Kl., N; 1919;4:1–36.
69.
Sloman A, Chrisley RL. Virtual machines and consciousness. J Conscious Stud 2003;10(4–5):113–72.
70.
Solomonoff RJ. A formal theory of inductive inference. Part I. Inf Control. 1964;7:1–22.CrossRef
71.
Solomonoff RJ. Complexity-based induction systems. IEEE Trans Inf Theory. 1978;IT-24(5):422–32.CrossRef
72.
Solomonoff RJ. Progress in incremental machine learning—preliminary report for NIPS 2002 workshop on universal learners and optimal search; revised September 2003. Technical Report IDSIA-16-03, Lugano: IDSIA; 2003.
73.
Sutton R, Barto A. Reinforcement learning: an introduction. Cambridge, MA: MIT Press; 1998.
74.
Turing AM. On computable numbers, with an application to the Entscheidungsproblem. Proc Lond Math Soc Ser 2. 1936;41:230–67.
75.
Utgoff P. Shift of bias for inductive concept learning. In: Michalski R, Carbonell J, Mitchell T, editors. Machine learning, vol 2. Los Altos, CA: Morgan Kaufmann; 1986. p. 163–90.
76.
Wolpert DH, Macready WG. No free lunch theorems for search. IEEE Trans Evolution Comput. 1997; 1.
77.
Zuse K. Rechnender Raum. Elektronische Datenverarbeitung 1967;8:336–44.
78.
Zuse K. Rechnender Raum. Friedrich Vieweg & Sohn, Braunschweig, 1969. [English translation: Calculating Space]. MIT Technical Translation AZT-70-164-GEMIT. Cambridge, MA: Massachusetts Institute of Technology (Proj. MAC); 1970.
Metadaten
Titel
Ultimate Cognition à la Gödel
verfasst von
Jürgen Schmidhuber
Publikationsdatum
01.06.2009
Verlag
Springer-Verlag
Erschienen in
Cognitive Computation / Ausgabe 2/2009
Print ISSN: 1866-9956
Elektronische ISSN: 1866-9964
DOI
https://doi.org/10.1007/s12559-009-9014-y

Weitere Artikel der Ausgabe 2/2009

Cognitive Computation 2/2009 Zur Ausgabe

OriginalPaper

Time-Scale Feature Extractions for Emotional Speech Characterization

OriginalPaper

Recruitment and Consolidation of Cell Assemblies for Words by Way of Hebbian Learning and Competition in a Multi-Layer Neural Network

OriginalPaper

On the Natural Hierarchical Composition of Cliques in Cell Assemblies

OriginalPaper

Artificial Cognitive Systems: From VLSI Networks of Spiking Neurons to Neuromorphic Cognition

OriginalPaper

Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors

Premium Partner

    Bildnachweise