28 ms·
1931: Kurt Gödel shows limits of math, logic, computing, AI
- m4rtink 5y agoAs a sidenote, my alma mater, Faculty of Informatics in Brno, Czech Republic, has Goedel depicted on its insignia, as he was active in the city: https://www.em.muni.cz/udalosti/698-insignie-fakulty-informatiky https://www.em.muni.cz/udalosti/698-insignie-fakulty-informa...
- erichahn 5y agoWhat most ppl don't notice is that Gödels incompleteness theorems are themselves expressible only in a logic system capable of expressing Peano arithmetic. Now this means that they apply to themselves which means that we cannot know if they are made up from a axiomatic system that can prove anything.
- kaba0 5y agoI’m not too knowledgeable on the topic, but Gödel’s proof uses a smaller logic system — on which a meta-language can be used to prove consistency/completeness. It is precisely about not being able to prove these properties “from within”.
- erichahn 5y agoWhich one? I don't think so tbh because his proof uses PA.
- kyberias 5y agoIt's very easy for you to check this from his 1931 article.
- erichahn 5y agoIf you figure this out correctly you can claim the third incompleteness theorem. (If I am right)
- ProfHewitt 5y agoResults in [Gödel 1931] depend on existence of proposition I'mUnprovable. Since, the proposition doesn't exist in foundations, the results in [Gödel 1931] do not hold for foundations.
- ProfHewitt 5y agoYes, it is very easy to check that [Gödel 1931] was for a system for the foundation of mathematics.
- ProfHewitt 5y agoThe reason that [Gödel 1931] was influential was that it claimed to prove incompleteness for a system for the foundations of mathematics. 1st-order systems such a PA were introduced later and quickly shown to be inadequate for the foundations of mathematics.
- ProfHewitt 5y agoAs explicitly stated in the title [Gödel 1931] for a system for the foundation of mathematics.
- dandanua 5y agoIt's ok to use logic to prove theorems in logic. We also use thinking to deduce some facts about our thinking. Self-reference is not always paradoxical. In a higher-order logic some self-referential definitions are legitimate.
- erichahn 5y agoYes and then you can do self-referential statements again which leads you to the conclusion that Gödels theorems are provable only in a system that cannot prove its own consistency.
- dandanua 5y agoTrue, but it's not a logical paradox. The fact that a system can't prove its own consistency doesn't imply that this system is inconsistent. The fact that Godel's theorems are provable only in such systems also doesn't imply that they are wrong. From the common sense the whole situation looks paradoxical, indeed. To prove consistency of some theory we have to use some stronger theory, to prove consistency of that theory we need even stronger theory and so on. Perhaps, the best way to realize why there is no paradox is the following: Our memory is finite. As well as our thinking. But the total number of true facts about mathematics is infinite. By constructing theories we are trying to compress the infinite number of true facts into some finite form. Godel's theorem says it's impossible. And it looks quite natural from this perspective.
- erichahn 5y agoI never said it is a paradox. I never said that PA or Q is inconsistent. I said that they cannot prove their own consistency by Gödels theorem. Hence we don't know if Gödels theorem was formalized in an inconsistent system. Honestly it would be weird if the incompleteness theorems don't apply to themselves.
- ProfHewitt 5y agoThe logical contradiction is that allowing the [Gödel 1931] proposition I'mUnprovable into foundations makes the foundations inconsistent.
- bidirectional 5y agoIt's not Peano arithmetic, it is basically 'enough of' arithmetic for Goedel's methods to apply. Robinson arithmetic is weaker than PA but Goedel still applies. Goedel's argument is basically a meta-argument about any mathematical system which is rich enough to describe useful mathematics, it does not rely on any particular axiomatisation, rather it applies to all axiomatisations with a few simple features.
- erichahn 5y ago"it does not rely on any particular axiomatisation" -- OK, what does it rely on then?
- carnitine 5y agoThe axioms allowing one to express enough of arithmetic for Goedel’s methods to apply. As the comment says.
- erichahn 5y agoI think if Gödels proof needs Q then that is OK. Q cannot prove its own consistency. Which means there is no way of telling that Gödels theorems are proved in a theory that is inconsistent (where everything is true).
- rssoconnor 5y agoWhile it is true that Goedel's theorem applies to weak systems such as Robinson Arithmetic (and any decidable extensions there of), The proof of Goedel's result itself requires at least some amount of induction. As a consequence the minimum system that Goedel's second incompleteness applies to is stronger than the minimum system that the first incompleteness theorem applies to.
- IngoBlechschmid 5y agoThis is not quite true, Gödel's incompleteness theorems can luckily be formalized in extremely weak fragments of Peano arithmetic such as primitive recursive arithmetic (PRA) with its very limited induction principle. :-) The only position on the philosophy of mathematics I know which does not accept PRA is ultrafinitism.
- erichahn 5y agoCan you provide a paper or book on this?
- ProfHewitt 5y agoProblem with 1st-order PRA is that it is too weak to serve as foundation of mathematics.
- littlecranky67 5y agoVeritasium recently released a very good video that explains Gödels incompletenes theorem such that even I could understand it: https://www.youtube.com/watch?v=HeQX2HjkcNo https://www.youtube.com/watch?v=HeQX2HjkcNo
- rottc0dd 5y agoThere is a little great book called "Godel's proof" by Nagel and Newman[1]. And definitely requires some focus but readable nevertheless. [1] https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371/ref=sr_1_1?crid=O3X5VYL776HD&dchild=1&keywords=godel%27s+proof&qid=1623923185&sprefix=godel%27s%2Caps%2C409&sr=8-1 https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081... Edit : removed a line
- deleted 5y ago[deleted]
- ruste 5y agoI second this! I spent a few days of summer vacation in highschool slowly working my way through this and it was mind expanding.
- alok-g 5y agoA good book as such. However, whereas the authors claim that they outline the proof in chapter 6, that chapter fell short of it with key aspects of the proof missing. Overall, I was disappointed.
- sillysaurusx 5y agoIn traditional HN style, I will now thumb my nose at Vertasium's excellent video due to him skipping over how godel came up with the proof. He built up the whole damn video for that one moment, when he says "And godel went through all this trouble to come up with this card..." and flips over the card. But how godel did it is at least as cool as the proof itself. I'm mostly being tongue in cheek with the Veritasium nose-thumbing. But if you saw it and want to understand it more deeply (and in my opinion more satisfyingly), I recommend "What Godel Discovered": https://news.ycombinator.com/item?id=25115746 https://news.ycombinator.com/item?id=25115746 It explains Godel's proof using Clojure. Quite accurately, too. The thread is also hilarious. Shoutout to the MIT professor who took offense at someone linking to his wikipedia page: "Wikipedia is contentious and often potentially libelous." ... and then you check his wikipedia page, and it's a super positive article about all of his discoveries and life's work.
- deleted 5y ago[deleted]
- masswerk 5y agoFun fact, on the PDP-7, there was a rare case of completeness, where the instruction "-0" not only encodes itself, but also operationally loads itself. For details see: https://www.masswerk.at/nowgobang/2019/pdp7-by-law https://www.masswerk.at/nowgobang/2019/pdp7-by-law
- bonoboTP 5y agoHow can you leave out von Neumann from such a list? Also, I feel like Schmidhuber tends to be German-speaking-centric. And overall, acknowledging that this is his signature shtick and it's good to have a voice like this too, he does a lot of anachronistic reinterpretations of early discoveries in light of later results. It streamlines the story as if it was always headed towards the today, culling aspects that didn't pan out or magnifying aspects that were at the time more minor and not considered the central issue or angle.
- weinzierl 5y ago> "How can you leave out von Neumann from such a list?" When I read the title: "1931: Kurt Gödel shows limits of math, logic, computing, AI" my head automatically completed it with "John von Neumann approves." I always found it fascinating and a sign of von Neumann's greatness how quickly he not only understood the consequences of Gödel's discovery but also that he immediately and publicly accepted them.
- ProfHewitt 5y agoIt is particularly ironic that Gödel deceived von Neumann about having already developed an important proof for [Gödel 1931]. The deception was discovered years after both had died. See [von Plato 2018]
- bumbledraven 5y agovon Plato, "In Search of the Sources of Incompleteness", Proc. Int. Cong. of Math, Vol. 4 (2018) (https://eta.impa.br/dl/209.pdf https://eta.impa.br/dl/209.pdf), p 4087: > A shadow is cast on Gödel’s great achievement; there is no way of undoing the fact that Gödel played a well-planned trick to persuade von Neumann not to publish.
- P-NP 5y agoVon Neumann is actually mentioned 3 times in the text and in the references.
- 5y ago
- ccity88 5y agoSee Veritasium's video, he goes into depth about Godel's theorems: https://www.youtube.com/watch?v=HeQX2HjkcNo https://www.youtube.com/watch?v=HeQX2HjkcNo
- ProfHewitt 5y agoVeritasium missed that existence of the [Gödel 1931] proposition I'mUnprovable leads to inconsistency in foundations by the following simple proof: Ever since Euclid, it has been a fundamental principle that a theorem can be used in a proof (the principle of TheoremUse), that is, {⊢((⊢Ψ)⇒Ψ)} [cf. Artemov and Fitting 2019]. However, by [Gödel 1931], ⊢(¬I’mUnprovable⇔⊢I’mUnprovable). Consequently, ⊢(¬I’mUnprovable⇒I’mUnprovable) by TheoremUse. • Therefore ⊢I’mUnprovable using ProofBySelfContradiction {⊢((⊢(¬Ψ⊢Ψ)) ⇒ ⊢Ψ)} with Ψ being I’mUnprovable. • Thus, I’mUnprovable using TheoremUse {⊢((⊢Ψ)⇒Ψ)} with Ψ being I’mUnprovable. Consequently, ⊬I’mUnprovable using ⊢(I’mUnprovable⇔⊬I’mUnprovable) Having both ⊢I’mUnprovable and ⊬I’mUnprovable is a contradiction in foundations.
- sillysaurusx 5y agoDear Professor Hewitt, I’m sorry for my comment at https://news.ycombinator.com/item?id=27537500 https://news.ycombinator.com/item?id=27537500. In hindsight, I realize now that it sounded like I was making fun of you. I didn’t intend to do that at all. I think your concerns about Wikipedia were surprising, and I only meant to express surprise. Thank you for taking the time to patiently explain to everyone your ideas about improbability. It takes a lot of courage to present an argument the way you’ve been doing in these threads. And you present your proofs in mathematical form here, which is rare, and worthy. (I’m posting this here simply because it’s your most recent comment, so that you’re likely to see it. I wasn’t quite sure where to put it.) Have a wonderful week.
- ProfHewitt 5y agoThank you very much sillysaurusx!
- mseepgood 5y ago(1931) This is old news.
- skissane 5y ago> Thus he identified fundamental limits of algorithmic theorem proving, computing, and any type of computation-based AI Fundamental limits presuming one has arbitrarily high (but finite) quantities of time and space with which the computations can be performed. Given in real world computation we will never have either, the fundamental limits of real-world computation are a lot less (even infinitely less) than those given by Gödel's work. Also, demonstrations of the theoretical limits of computation (Gödel, Turing, etc) often make the assumption that we only have finite (even if arbitrarily large) resources, and that true contradictions (dialetheias) are disallowed. If we give up either (or both) of those of two assumptions, we can compute beyond those limits. It may be objected that computations beyond those limits are not physically realisable; but, almost all computations within those limits are not physically realisable either, so how much significance does that objection actually have?
- Valmar 5y agoIt's a harsh, but true reality that with only have finite quantities of time and space, especially in real world computation. The assumption of finite resources is also a harsh, but true reality. There are many things that fundamentally defy any form of computation. Things which cannot create mathematical formulae to represent, nor create algorithms for. For a major example, we cannot translate the mental activities of conscious, aware living beings into any sort of computable form, as these activities are not algorithmic in nature. They aren't random, nor deterministic ~ rather, they are indeterministic, following no rigid patterns. Even the most complex, complicated computer program follows an algorithm, which is ultimately deterministic. Even if you throw in some random inputs at some parts, the algorithm still acts deterministically. Perhaps the only really indeterministic part in an algorithm's behaviour might be hardware level bugs and errata which interfere with the otherwise very predictable algorithm.
- amanaplanacanal 5y ago> For a major example, we cannot translate the mental activities of conscious, aware living beings into any sort of computable form, as these activities are not algorithmic in nature. They aren't random, nor deterministic ~ rather, they are indeterministic, following no rigid patterns. How could you possibly know that? Following no known patterns, maybe.
- truth_ 5y agoIf you want to learn thoroughly about Godel's Incompleteness Theorem, and all its implications, nothing is better than Godel, Escher, Bach: An Eternal Golden Braid by Hofstadter. This book is quite outdated in both approaches and ideas about computers, and computer-aided approaches to Artificial Intelligence, this book still has to offer a lot. It is one of the most impactful books I have read.
- ruslan 5y agoFascinating book indeed. I read it when I was a student some twenty years ago, I had been astonished by simple and clever trick Godel used to prove his theorem - to digitize everything, then operate with just numbers.
- alok-g 5y agoDoes it explain the proof itself in it's full glory? I had read "Godel's Proof" by Ernest Nagel et al [1] and it fell short. [1] https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/0814758371/ https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/08147583...
- truth_ 5y agoYou mention in another comment that it skipped some part of the proof and that you were disappointed. Do you still recommend the book?
- alok-g 5y agoIf you are mathematically-inclined and are looking forward to understanding the proof itself, the book won't do much better than the following video [1] taken from a comment in this thread [2]. Disappointed, I attempted to read Godel's original papers. That has it's own challenge as it refers to Principia Mathematica. I started reading that. Only to fimd that it uses older mathematical notation not in use today. In short, I haven't found any source that explains the proof in reasonable detail. If you want to understand the thought process of axiomatic reasoning (and with less extrapolations to consciousness et al) it is a good book. Note: I had read a long time back, so do not remember the details. [1] https://www.youtube.com/watch?v=HeQX2HjkcNo https://www.youtube.com/watch?v=HeQX2HjkcNo [2] https://news.ycombinator.com/user?id=littlecranky67 https://news.ycombinator.com/user?id=littlecranky67
- truth_ 5y agoI appeciate how Schmidhuber puts focus on non-US-centric history of Deep Learning and modern AI. He sometimes overdoes these. Even when something is not related to Deep Learning and modern AI. He tries to push very narrow and one-sided views without much room for nuance. For example- "Turing used his (quite inefficient) model only to rephrase the results of Gödel and Church on the limits of computability." He is trying to say that Turing did nothing new, his work is a mere extension of Godel's (!), and he only accounted for practical computational reality. That is not true. He goes on further by saying, "Later, however, the simplicity of these machines made them a convenient tool for theoretical studies of complexity." Like, Turing and Church's work was only good for that. I digress. I believe that Turing's work is more seminal and paved the way for modern general computers. Another bit here says "The formal models of Gödel (1931-34), Church (1935), Turing (1936), and Post (1936) were theoretical pen & paper constructs that cannot directly serve as a foundation for practical computers." It is putting the works of Turing, Post, Church, and Godel all together. Like they are the same. I see the logic as they are all impractical, but they are different levels of impractical. Putting them all under one bracket like that makes no sense. I respect Schmidhuber a lot, but some of his behaviour is borderline childish which are more pronounced in his claims about AI history. You should be skeptical about what he says (and what anyone says). Despite all this, I did not know many things written in this article. I learned a lot and had fun reading it. I first read about Zuse in Isaacson's Innovators book. Did not know that he used a high-level language for a chess program. Fascinating. He is very underrated.
- maweki 5y agoBoth the discovery of Lambda Calculus and the Turing Machine as models of computation are quite important and immediately useful, I'd say. Though very formal, just a little bit of syntactic sugar and eye-squinting make for useful programming constructs and more or less direct lines to early as well as modern programming languages.
- ProfHewitt 5y agoDevelopment of Lambda Calculus [Church 1931] and Turing Machine [Turing 1936] were fundamental achievements. However, they are inadequate models of computation because there are digital computations they cannot implement. See the following for an example: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021
- denton-scratch 5y agoI have relied on Douglas Hofstadter and Roger Penrose for explanations of Gödel's theorem. Hofstadter is easier - Gödel Escher and Bach. Penrose's explanation is dryer, but more direct - The Emperor's New Mind. I understand the idea of Gödel numbering; I understand Cantor's diagonal slash; but I struggle to assemble the components into a proof that convinces me. I think I just lack the cerebral capacity.
- pmmck 5y agoFor me the click came while finishing To Mock a Mockinbird by Raymond Smullyan. https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird Smullyan "tricks" you into deriving the Gödel Incompleteness Theorem from the BCKW combinator calculus.
- alok-g 5y agoDoes either (claims to) explain the proof itself in it's full glory? I had read "Godel's Proof" by Ernest Nagel et al [1] and it fell short. [1] https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/0814758371/ https://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/08147583...
- denton-scratch 5y agoI'm not sure about "claims to". I have misplaced my copy of the Penrose book. Hofstadter's book is humorous, despite its weight. It doesn't purport to be a canonical explanation of the theorem. Both books are ultimately focused on the nature of consciousness, although from quite different perspectives. In both cases, the theorem is presented as one element of an argument. It's interesting that two sophisticated writers with wildly different opinions about consciousness have both leaned on Gödel to back their arguments. There's nothing in the theorem that shouts "This is about consciousness!"
- alok-g 5y agoPenrose's argument linking consciousness to Godel's theorems makes little sense to me. https://en.m.wikipedia.org/wiki/Penrose–Lucas_argument https://en.m.wikipedia.org/wiki/Penrose–Lucas_argument Thanks for answering my question. I am guessing that neither book would explaim the proof in detail.
- asimpletune 5y agoHonest question, is the incompleteness theorem ever used for anything?
- ffhhj 5y agoA strong AI would need a theory of incompleteness in order to save time when solving problems, and that's not as simple as saying "this program is taking more than a second to finish, I quit!". There must be some intuition to make the decision.
- musicale 5y agoI'm puzzled as to why we'd somehow expect so much more of artificial intelligence than we expect of natural intelligence, or that we somehow don't expect to be able to develop artificial intuition systems. My own intuition ;-) is that intuition seems to derive more from pattern matching than from logic.
- ProfHewitt 5y agoWork on the incompleteness theorem is valuable in preventing successful next generation cyberattacks. See the following: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021 PS. This link has been posted to this discussion several times. However, there doesn't seem to be any means to hyperlink contributions within this discussion :-(
- tovej 5y agoTangentially related: the book "Gödel, Escher, Bach: an Eternal Golden Braid" by Douglas Hofstadter is a computer science classic that deals with incompleteness among other things (mostly self-references in formal systems) in a fun way.
- b3kart 5y agoSchmidhuber has done a lot of important, fundamental work, at the time when none of it was “cool”, but whenever I stumble upon his writing it always reads like a bad history book, where when and who are more important than what or why. I get (and moderately support) his obsession with proper attribution, but I wish he first talked about ideas, and then delved into the intricate historical details.
- ProfHewitt 5y agoMathematical foundations are indeed incomplete, that is, there are true propositions, which are unprovable. However, [Gödel 1931] failed to prove incompleteness of foundations using the nonexistent proposition I'mUnprovble. The [Gödel 1931] attempt to construct I'mUnprovable using fixed points fails because it violates restrictions on orders of propositions. The Gödel number of a proposition left out its order. Furthermore, existence of I'mUnprovable would have the unfortunate consequence that foundations are inconsistent. It is worth noting that the proposition I'mUnprovable is of no practical importance in mathematical foundations. Consequently its nonexistence does not much matter. See the following for further explanation: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021
- jkhdigital 5y agoNice to hear from you again, Carl. Your comments about inconsistent foundations brings to mind the Univalent Foundations approach to mathematics--can you comment on how your research relates to univalent foundations and homotopy type theory?
- ProfHewitt 5y agoThanks jkhdigital! Of course, mathematical foundations must not be inconsistent. Homotopy type theory is an attempt address issues of equality in type theory.
- rssoconnor 5y agoFor the record, Gödel proposition can be constructed[1] in the same manner that Quines[2] can be constructed. I myself have formalized[3] the first incompleteness theorem in the Coq proof assistant, and many others have as well in various proof assistants. You can find specific and concrete instance of a Gödel proposition written by Stephen Lee at <http://tachyos.org/godel/Godel_statement.html http://tachyos.org/godel/Godel_statement.html>. It really is not that large of a proposition. I'm not sure how you can claim that proposition that I can see with my own eyes does not exist. [1] http://r6.ca/blog/20190223T161625Z.html http://r6.ca/blog/20190223T161625Z.html [2] https://en.wikipedia.org/wiki/Quine_(computing) https://en.wikipedia.org/wiki/Quine_(computing) [3] https://github.com/coq-community/goedel https://github.com/coq-community/goedel
- scotty79 5y agoFor me it just means that math is just like the code. If you start defining stuff and cross-calling it without special care you will end up in trouble in form of infite loop or recursion or in case of math, a paradox. From what I understand it is that you might reason about but not prove that statement "this statement is not provable" must be true but thus unprovable. Godel's result shows that if you are willing to assume axioms that let you do arithemetics, statement equivalent to this paradoxical one just crops up. For me it just means that you need to put additional restrictions of what you can do in math so that kind of statement is excluded from math. Same way that "set of all sets that are not their own elements" got excluded from consideration by more carefully defining what set theory is involved with.
- ProfHewitt 5y agoGood point, scotty79! In fact the [Gödel 1941] proposition I'mUnprovable does not exist in mathematical foundations.
- magneticnorth 5y ago>> For me it just means that you need to put additional restrictions of what you can do in math so that kind of statement is excluded from math. The thing about Godel's proof is that he didn't just come up with one example of a "this statement is not provable" sentence; he proved that any sufficiently complex math system will have unprovable sentences (some true, some false, some you'll never be able to know). And "sufficently complex" is not all that complex! So if you want to be able to do calculus, or even most arithmetic, you can't just "put additional restrictions ... so that kind of statement is excluded from math."
- scotty79 5y agoSure you can. Just ban the concept of provability from your math language (or some elements that lead to it). Same way like they banned weird kinds of sets and started talking about set families instead of sets of sets. If you declare that set being its own element is nonsensical statement you no longer have a paradox with set of sets that are not their own elements. Base assumption of math is that correctly constructed mathematical statement is not nonsensical. It must be true or false or not determined by current set of axioms. And I think that assumption of sensibility of any math statement leads to paradoxes.
- warmfuzzykitten 5y agoI don't understand how Gödel showed limits of AI, or even addressed AI in its modern incarnation, which has little to do with logic. Perhaps some more knowledgeable reader can elucidate?
- YeGoblynQueenne 5y agoWithout getting too technical, if AI must run on a computer, and there are programs that computers cannot compute, then there are limits to what AI can compute, or in other words think (because it's an AI; so to think, it computes). As a very crude example of this kind of limitation, I'm sure I've read a hundred Sci-Fi stories where the humans defeat the AI by posing to it an unsolvable problem, usually a variation of the "liar's paradox", e.g. "this statement is false" (which btw is used by Gödel in his proof). So a human traipses over to the superintelligent AI and blurts "I always lie". Then the AI spends an aeon processing the sentence and then blows up. Even worse, intelligence itself may turn out to be an uncomputable program that cannot be executed on a computer. In that case- no AI.
- visarga 5y agoThe scenarios you described are not realistic. There's no AI getting stuck into a loop by a tricky question, not even GPT-3. Any solution would take into consideration its computation cost. AlphaGO for example would evaluate 50K board states per move, it won't go into a 3^361 recursion. In general when the problem is so hard evolutionary methods are suitable. They naturally blend the notion of cost with that of search and cope better with deceptive objectives.
- deleted 5y ago[deleted]
- YeGoblynQueenne 5y agoYour turn of phrase "there's no AI getting stuck..." has me stuck. Are you assuming that there exist "AIs", as in artificially intelligent entities, like the kind imagined by science fiction writers and (some) AI researchers, alike? To clarify, there are no such systems. "AI" is the name of a research field, not any ability that characterises a class of systems currently known. This suffices to explain why there is, indeed "no AI getting stuck inot a loop by a tricky question". Because there is "no AI" at all, certainly not of the kind that can understand a "tricky question" sufficiently well to stumble on the paradox inside it. For example, GPT-3 has no ability to process "this sentence is false" in such a way as to decide its truth. AlphaGo is not capable of processing language at all, it is only capable of playing board games and it isn't even capable of playing board games by reasoning, only by search. AlphaGo searches a game tree structured as a directed graph, without loops so it's hard to see how it could get stuck on recursive paradoxes anyway. In general, such systems as exist today do not have the mathematical properties of the formal systems described by Gödel, Church and Turing. They don't even have memories. So they are, let's say immune to incompleteness, because they're not even incomplete.
- YeGoblynQueenne 5y ago>> The machine was still considered impressive decades later when the AI pioneer Norbert Wiener played against it at the 1951 Paris conference,[AI51][BRO21] [BRU1-4] which is now often viewed as the first conference on AI—though the expression "AI" was coined only later in 1956 at another conference in Dartmouth by John McCarthy. In fact, in 1951, much of what's now called AI was still called Cybernetics, with a focus very much in line with modern AI based on deep neural networks.[DL1-2][DEC] Yeess, that's true. John McCarthy named "AI". And he wisely set the foundations of the field in the work of his thesis advisor, Alonzo Church, and the mathematicians of his generation, and the ones before, all the way back to Gödel. That is to say, McCarthy set the foundations of AI in mathematical logic, the branch of mathematics that began in antiquity by Aristotle, flourished in the Middle Ages, the Rennaissance and the Enlightenment with the works of Arab and Christian scholars, reached its peak with Leibniz and was finally exalted with the work of Frege, Russel, Whitehead, Hilbert, Tarski, Skolem, Herbrand, Gödel himself, Church, Turing and others. The branch of mathematics that gave us digital computers, much like Jurgen Schmidhuber points out in his article. It is this work that is the only, well, logical, foundation of artificial intelligence. That suffices to explain why the earlier "cyerbnetics" branch of research fell through: because unlike McCarthy's AI, it was not grounded in solid theoretcial foundations that had already yielded such monumental results in mathematics and computer science. And it is the foundations of AI in logic that AI research must return to, eventually, because it makes no sense to throw out two thousand years of progress, just because an intellectual midget by the name of Sir James Lighthill wrote a report. It would be even worse to throw out such richess of knowledge in return for the ability to put bunny noses and ears on selfies with "neural networks".
- P-NP 5y agoGood point. Where exactly does mathematical logic end and AI begin?
- YeGoblynQueenne 5y agoIf you want my opinion, far from one another. It's an accident of history that logic, a branch of mathematics, was lumped together with the fuzzy, hardly scientific goals of the AI project. It's all the fault of McCarthy, of course. Oh, sure, McCarthy is one of my science heroes. But it is because of him that reserach that firmly belonged to mathematics and computer science in the broad sense, particularly the research on automated theorem proving, the natural continuation of the work of Gödel, Church and Turing, was lumbered with the goal of somehow showing that it can compute intelligence. I mean, why is the ability to prove sentences in a formal languages a necessary requirement for intelligence? As far as I can tell, most humans do fine without it and so do basically all non-human animals that have anything remotely recognisable as intelligence. Why is the ability to play chess a prerequisite of intelligence, for that matter, or the ability to predict protein structure? All those are typical tasks of AI as a field of research, because they happen to be "things that one can do with computers", i.e. computable computations. But what do they have to do with intelligence? What the hell even is intelligence? Turing gave us a model of computing machines and if one assumes that intelligence is a computable function, then it makes sense to try and compute it with a machine, but isn't that assumption the first thing we should test, before jumping right in and doing all the things we'd do if we knew it for sure to be true? And if it was true, wouldn't we have seen some progress towards that goal, after 70 years of study? I'm speaking in this as someone who entered AI research because of my interest in logic programming and automated theorem proving, and mathematical logic in general. I am not interested in creating "AIs" one bit and yet, here I am, studying for a PhD in what is traditionally an AI subject. That's just dumb. Logic should have stayed where it belongs, in mathematics. But... McCarthy was Church's student, so it was natural for him to set down the foundations of the field to the seminal work of his advisor, and others like him. Kind of like he was so keen on chess as an AI task- because he liked to play chess. At least McCarthy's personal preferences did help to build a foundation of AI on theory, like I say in my comment above, so, for a while at least, it could have been less fuzzy and throw-stuff-at-the-wall-to-see-what-sticks-y than (most of) it is currently.
- ur-whale 5y agoSchmidhuber certainly can't be accused of not being consistent ... article is basically yet another long rant about people not getting the credit they deserve. At this point, it looks like this theme has become a very central piece of his mental world.
- ProfHewitt 5y agoContra Schmidhuber's article, [Turing 1936] was correct in its statement that the proof of computational undecidability of the halting problem is very different from [Gödel 1931] attempted proof of inferential undecidability using the (nonexistent) proposition I'mUnprovable.