Answers.Body: <p>I found <a href="https://math.stanford.edu/~feferman/papers/dichotomy.pdf" rel="nofollow noreferrer">this paper</a> by mathematician and philosopher <em>Solomon Feferman</em> on <em>Gödel's 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems</em>, while reading the following Wikipedia article</p>
  
  <blockquote>
    <p><a href="https://en.wikipedia.org/wiki/Philosophy_of_artificial_intelligence" rel="nofollow noreferrer">Philosophy of artificial intelligence</a>,</p>
  </blockquote>
  
  <p>whose abstract gives us (as expected) a high-level idea of what's discussed in the same:</p>
  
  <blockquote>
    <p>This is a critical analysis of the first part of Gödel's 1951 Gibbs lecture
    on certain philosophical consequences of the incompleteness theorems.</p>
    
    <p>Gödel's discussion is framed in terms of a distinction between <em>objective
    mathematics</em> and <em>subjective mathematics</em>, according to which the former
    consists of the truths of mathematics in an absolute sense, and the latter
    consists of all humanly demonstrable truths. </p>
    
    <p>The question is whether these coincide; if they do, no formal axiomatic system (or <em>Turing machine</em>) can comprehend the mathematizing potentialities of human
    thought, and, if not, there are absolutely unsolvable mathematical
    problems of diophantine form.</p>
    
    <p>Either ... the human mind ... infinitely surpasses the powers of any
    finite machine, or else there exist absolutely unsolvable diophantine
    problems.</p>
  </blockquote>
  
  <p>which may be of interest, at least philosophically, to the research in AI. I'm afraid this paper may be similar to the article you're linking to regarding Lucas and Penrose philosophical "attempts" or arguments.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-04-27T01:55:54.303Z
Answers.LastActivityDate: 2017-04-27T02:08:45.147Z
Answers.LastEditDate: 2017-04-27T02:08:45.147Z
Answers.UserDisplayName: nbro
Answers.Body: <p>I've written an extensive article on this some twenty years ago, which was published in <em>Engineering Applications of Artificial Intelligence 12 (1999) 655-659</em>. It's fairly technical and <a href="http://www.christianjongeneel.nl/gepubliceerde-boeken/goedel-pro-and-contra-ai-dismissal-of-the-case/" rel="nofollow noreferrer">you can read it in full</a> on my personal website, but here's the conclusion:</p>
  
  <blockquote>
    <p>In the above it was shown that there are infinitely many proof
    constructions to Gödel’s theorem – in contrast to the single one that
    was used in discussions on artificial intelligence so far. Though all
    constructions that have been actually disclosed can be imitated by a
    computer, it is evident that there are constructions that have not
    been disclosed yet. Our analysis has shown that there might exist
    constructions that might only be discovered by a human. This is a
    small and definitely unprovable ‘maybe’ that depends on the limits of
    human imagination.</p>
    
    <p>Hence, people arguing for the mathematical equivalence of humans and
    machines must ultimately rely on their belief in a limited mind, which
    implies that their conclusion is contained in their assumption. On the
    other hand, people advocating the superiority of humans must assume
    this superiority in their mathematical arguments, ultimately only
    deriving the conclusion that was already present in their system of
    reasoning from the very start.</p>
    
    <p>So, it is not possible to produce (meta)mathematically sound arguments
    concerning the relation between the human mind and the Turing Machine
    without making an assumption on the human mind that is at the same
    time the conclusion of the argument. Therefore, the matter is
    undecidable.</p>
  </blockquote>
  
  <p>Disclaimer: I have left academia since, so I do not know of contemporary thinking.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-01T12:43:51.997Z
Answers.LastActivityDate: 2017-05-01T12:43:51.997Z
Answers.UserDisplayName: cjbj
Answers.Body: <p>Definitely there are a lot of implications for AI, including:</p>
  
  <ol>
  <li><p><a href="https://en.wikipedia.org/wiki/First-order_logic" rel="nofollow noreferrer">Inference with first-order-logic is semi-decidable</a>. This is a big disappointment for all the folks that wanted to use logic as a primary AI tool.</p></li>
  <li><p>Basic equivalence of two first-order logic statements is undecidable, which has implications for knowledge-based systems and databases. For example, optimisation of database queries is an undecidable problem because of this.</p></li>
  <li><p><a href="https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html" rel="nofollow noreferrer">Equivalence of two context-free grammars is undecidable</a>, which is a problem for formal linguistic approach toward language processing</p></li>
  <li><p>When doing planning in AI, just finding a feasible plan is undecidable for some planning languages that are needed in practice.</p></li>
  <li><p>When doing automatic program generation - we are faced with a bunch of decidability results, since any reasonable programming language is as powerful as a Turing machine.</p></li>
  <li><p>Finally, all non-trivial questions about an expressive computing paradigm, such as Perti nets or cellular automata, are undecidable.</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-13T10:32:08.923Z
Answers.Text: @randomsurfer_123 For completeness and to increase the reliability of this answer, can you please provide a link to a source that supports each of your claims?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-18T23:34:49.203Z
Answers.Text: two/three years later, i haven't been able to verify these results. however, i am also under the impression that these results are fairly standard. most or all of these should be covered in a good math-logic textbook (A Friendly Introduction to Mathematical Logic perhaps?)
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-25T11:56:04.970Z
Answers.Text: Can anyone provide a source for this? Or a point of the finger towards some relevant text.
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-04-24T10:49:22.320Z
Answers.LastActivityDate: 2020-05-13T10:27:32.927Z
Answers.LastEditDate: 2020-05-13T10:27:32.927Z
Answers.UserDisplayName: randomsurfer_123
Body: <p><em>Note: My experience with Gödel's theorem is quite limited: I have read Gödel Escher Bach; skimmed the 1st half of Introduction to Godel's Theorem (by Peter Smith); and some random stuff here and there on the internet. That is, I only have a vague high level understanding of the theory.</em> </p>
  
  <p>In my humble opinion, Gödel's incompleteness theorem (and its many related Theorems, such as the Halting problem, and Löbs Theorem) are among the most important theoretical discoveries. </p>
  
  <p>However, its a bit disappointing to observe that there aren't that many (at least to my knowledge) theoretical applications of the theorems, probably in part due to 1. the obtuse nature of the proof 2. the strong philosophical implications people aren't willing to easily commit towards.</p>
  
  <p>Despite that, there are still some attempts to apply the theorems in a philosophy of mind / AI context. Off the top of my head:</p>
  
  <ul>
  <li><p><a href="http://www.iep.utm.edu/lp-argue/" rel="nofollow noreferrer">The Lucas-Penrose Argument</a>: which argues that the mind is not implemented on a formal system (as in computer). (Not a very rigour proof however) </p></li>
  <li><p>Apparently, some of the research at MIRI uses Löbs Thereom, though the only example I know of is <a href="http://intelligence.org/files/ProgramEquilibrium.pdf" rel="nofollow noreferrer">Löbian agent cooperation.</a></p></li>
  </ul>
  
  <p>These are all really cool, but are there some more examples? Especially ones that are actually seriously considered by the academic community.</p>
  
  <p>See also <a href="https://philosophy.stackexchange.com/q/305">What are the philosophical implications of Gödel's First Incompleteness Theorem?</a></p>
  
Tags: <philosophy><research><theory-of-computation><incompleteness-theorems>
Title: What are some implications of Gödel's theorems on AI research?
UserDisplayName: k.c. sayz 'k.c sayz'
ThreadText: # What are some implications of Gödel's theorems on AI research?
  
  (Asked by: username_0 on 2017-04-23)
  
  *Note: My experience with Gödel's theorem is quite limited: I have read Gödel Escher Bach; skimmed the 1st half of Introduction to Godel's Theorem (by Peter Smith); and some random stuff here and there on the internet. That is, I only have a vague high level understanding of the theory.*
  
  In my humble opinion, Gödel's incompleteness theorem (and its many related Theorems, such as the Halting problem, and Löbs Theorem) are among the most important theoretical discoveries.
  
  However, its a bit disappointing to observe that there aren't that many (at least to my knowledge) theoretical applications of the theorems, probably in part due to 1. the obtuse nature of the proof 2. the strong philosophical implications people aren't willing to easily commit towards.
  
  Despite that, there are still some attempts to apply the theorems in a philosophy of mind / AI context. Off the top of my head:
  
  * [The Lucas-Penrose Argument](http://www.iep.utm.edu/lp-argue/): which argues that the mind is not implemented on a formal system (as in computer). (Not a very rigour proof however)
  * Apparently, some of the research at MIRI uses Löbs Thereom, though the only example I know of is [Löbian agent cooperation.](http://intelligence.org/files/ProgramEquilibrium.pdf)
  
  These are all really cool, but are there some more examples? Especially ones that are actually seriously considered by the academic community.
  
  See also [What are the philosophical implications of Gödel's First Incompleteness Theorem?](https://philosophy.stackexchange.com/q/305)
  
  **Tags:** philosophy, research, theory-of-computation, incompleteness-theorems
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2017-04-24. Score: 7 | Accepted answer
  
  Definitely there are a lot of implications for AI, including:
  
  1. [Inference with first-order-logic is semi-decidable](https://en.wikipedia.org/wiki/First-order_logic). This is a big disappointment for all the folks that wanted to use logic as a primary AI tool.
  2. Basic equivalence of two first-order logic statements is undecidable, which has implications for knowledge-based systems and databases. For example, optimisation of database queries is an undecidable problem because of this.
  3. [Equivalence of two context-free grammars is undecidable](https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html), which is a problem for formal linguistic approach toward language processing
  4. When doing planning in AI, just finding a feasible plan is undecidable for some planning languages that are needed in practice.
  5. When doing automatic program generation - we are faced with a bunch of decidability results, since any reasonable programming language is as powerful as a Turing machine.
  6. Finally, all non-trivial questions about an expressive computing paradigm, such as Perti nets or cellular automata, are undecidable.
  
  > **Comments:**
  > **username_0**: Can anyone provide a source for this? Or a point of the finger towards some relevant text.  
  > **username_1**: @randomsurfer_123 For completeness and to increase the reliability of this answer, can you please provide a link to a source that supports each of your claims?  
  > **username_0**: two/three years later, i haven't been able to verify these results. however, i am also under the impression that these results are fairly standard. most or all of these should be covered in a good math-logic textbook (A Friendly Introduction to Mathematical Logic perhaps?)  
  
  ---
  
  ### Answer by username_1 on 2017-04-27. Score: 1
  
  I found [this paper](https://math.stanford.edu/~feferman/papers/dichotomy.pdf) by mathematician and philosopher *Solomon Feferman* on *Gödel's 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems*, while reading the following Wikipedia article
  
  > [Philosophy of artificial intelligence](https://en.wikipedia.org/wiki/Philosophy_of_artificial_intelligence),
  
  whose abstract gives us (as expected) a high-level idea of what's discussed in the same:
  
  > This is a critical analysis of the first part of Gödel's 1951 Gibbs lecture
  > on certain philosophical consequences of the incompleteness theorems.
  >
  > Gödel's discussion is framed in terms of a distinction between *objective
  > mathematics* and *subjective mathematics*, according to which the former
  > consists of the truths of mathematics in an absolute sense, and the latter
  > consists of all humanly demonstrable truths.
  >
  > The question is whether these coincide; if they do, no formal axiomatic system (or *Turing machine*) can comprehend the mathematizing potentialities of human
  > thought, and, if not, there are absolutely unsolvable mathematical
  > problems of diophantine form.
  >
  > Either ... the human mind ... infinitely surpasses the powers of any
  > finite machine, or else there exist absolutely unsolvable diophantine
  > problems.
  
  which may be of interest, at least philosophically, to the research in AI. I'm afraid this paper may be similar to the article you're linking to regarding Lucas and Penrose philosophical "attempts" or arguments.
  
  
  ---
  
  ### Answer by username_2 on 2017-05-01. Score: 1
  
  I've written an extensive article on this some twenty years ago, which was published in *Engineering Applications of Artificial Intelligence 12 (1999) 655-659*. It's fairly technical and [you can read it in full](http://www.christianjongeneel.nl/gepubliceerde-boeken/goedel-pro-and-contra-ai-dismissal-of-the-case/) on my personal website, but here's the conclusion:
  
  > In the above it was shown that there are infinitely many proof
  > constructions to Gödel’s theorem – in contrast to the single one that
  > was used in discussions on artificial intelligence so far. Though all
  > constructions that have been actually disclosed can be imitated by a
  > computer, it is evident that there are constructions that have not
  > been disclosed yet. Our analysis has shown that there might exist
  > constructions that might only be discovered by a human. This is a
  > small and definitely unprovable ‘maybe’ that depends on the limits of
  > human imagination.
  >
  > Hence, people arguing for the mathematical equivalence of humans and
  > machines must ultimately rely on their belief in a limited mind, which
  > implies that their conclusion is contained in their assumption. On the
  > other hand, people advocating the superiority of humans must assume
  > this superiority in their mathematical arguments, ultimately only
  > deriving the conclusion that was already present in their system of
  > reasoning from the very start.
  >
  > So, it is not possible to produce (meta)mathematically sound arguments
  > concerning the relation between the human mind and the Turing Machine
  > without making an assumption on the human mind that is at the same
  > time the conclusion of the argument. Therefore, the matter is
  > undecidable.
  
  Disclaimer: I have left academia since, so I do not know of contemporary thinking.
  
  
  ---
  
  