Body: <p>Lets say we have a oracle <span class="math-container">$S$</span> that, given any function <span class="math-container">$F$</span> and desired output <span class="math-container">$y$</span>,  can find an input <span class="math-container">$x$</span> that causes <span class="math-container">$F$</span> to output <span class="math-container">$y$</span> if it exists, or otherwise returns nil. I.e.:</p>
  
  <p><span class="math-container">$$S(F, y) = x \implies F(x) = y$$</span>
  <span class="math-container">$$S(F, y) = nil \implies !\exists  x \hspace{10px}s.t.\hspace{10px} F(x) = y$$</span></p>
  
  <p>And <span class="math-container">$S$</span> takes <span class="math-container">$1$</span> millisecond to run (plus the amount of time it takes to read the input and write the output), regardless of <span class="math-container">$F$</span> or <span class="math-container">$y$</span>. <span class="math-container">$F$</span> is allowed to include calls to <span class="math-container">$S$</span> in itself.</p>
  
  <p>Clearly with this we can solve any NP-Complete problem in constant time (plus the amount of time it takes to read the input and write the output), and in fact we can go further and efficiently solve any optimization problem:</p>
  
  <pre><code>def IsMin(Cost, MeetsConstraints, x):
    def HasSmaller(y):
      return MeetsConstraints(x) and Cost(y) &lt; Cost(x) and y != x
    return MeetsConstraints(x) and S(HasSmaller, True) == nil
  
  def FindMin(Cost, MeetsConstraints):
    def Helper(x):
      return IsMin(Cost, MeetsConstraints, x)
    return S(Helper, True)
  </code></pre>
  
  <p>Which means we can do something like:</p>
  
  <pre><code>def FindSmallestRecurrentNeuralNetworkThatPerfectlyFitsData(Data):
    def MeetsConstraints(x):
      return IsRecurrentNeuralNetwork(x) and Error(x, Data) == 0
    return FindMin(NumParamaters, MeetsConstraints)
  </code></pre>
  
  <p>And something similar for any other kind of model (random forest, random ensemble of functions, etc.). We can even solve the halting problem with this, which probably means that there is some proof similar to the halting problem proof that shows such an oracle could not exist. Lets assume this exists anyway, as a thought experiment. </p>
  
  <p>But I'm not sure how to take it from here to something that achieves endless self improvement. What exactly the "singularity" even means I suppose is tricky to define formally, but I'm interested in any simple definitions, even if they don't quite capture it.</p>
  
  <p>A sidenote, here is one more function we can do:</p>
  
  <pre><code>IsEquivalent(G, H):
      def Helper(x):
        return G(x) != H(x)
      return P(Helper, True) == nil
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T22:27:49.293Z
Comments.Text: "_Clearly with this we can solve any NP-Complete problem_". Note that, in principle, you can  already solve any NP-complete problem, but you need exponential time to do so, unless someone proves $P = NP$: in that case, there would a polynomial-time solution for each NP-complete problem.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T22:32:05.950Z
Comments.Text: In general, in this question, you're talking about something you don't even know well. So, your assumptions and conclusions will likely not lead anyone anywhere. I would encourage you to read the book "Introduction to the Theory of Computation" by Sipser before trying to understand if the singularity is possible.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T22:38:15.273Z
Comments.Text: AFAIK, the singularity is not even a well defined or mathematically formalised problem. You may want to attempt to do that. But I guess you will need to work hard.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T22:55:39.053Z
Comments.Text: @nbro sorry, I added an edit to clarify what I meant (with this oracle, we would do it very efficiently). I'm not sure where you are getting your assumptions that I don't know these things well: I have read through all of Sipser (it is a good recommendation) and understand complexity classes and such. I'm even a published author in multiple computer science academic conferences.
  
  I know such an oracle (probably) isn't possible, but I don't see why such a thought experiment isn't interesting regardless? There are all kinds of questions we study in computer science about oracles.
Comments.UserDisplayName: Phylliida
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T22:59:01.883Z
Comments.Text: @nbro "the singularity is not even a well defined or mathematically formalised problem" I agree. Another way to phrase my question could be "what kind of self-improving behavior could we get with such an oracle, and how close does this behavior match common intuitions of what the 'singularity' might be?"
Comments.UserDisplayName: Phylliida
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T23:06:36.257Z
Comments.Text: I think a better question on this website would be: "Can we define the AI singularity mathematically"? You may want to have a look at [AIXI](https://en.wikipedia.org/wiki/AIXI). Anyway, I think that the oracle (as you define it) would just provide speed of learning.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T23:21:36.873Z
Comments.Text: [Done](https://ai.stackexchange.com/questions/10644/can-we-define-the-ai-singularity-mathematically), thanks for the suggestion, but I feel this question is different enough that I won't remove it.
Comments.UserDisplayName: Phylliida
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-17T23:36:07.627Z
Comments.Text: Regarding AIXI, you may want to have a look at https://ai.stackexchange.com/a/10377/2444.
Comments.UserDisplayName: nbro
Tags: <algorithm><optimization><singularity>
Title: Is a very powerful oracle sufficient to trigger the AI singularity?
UserDisplayName: Phylliida
ThreadText: # Is a very powerful oracle sufficient to trigger the AI singularity?
  
  (Asked by: username_0 on 2019-02-17)
  
  Lets say we have a oracle $S$ that, given any function $F$ and desired output $y$, can find an input $x$ that causes $F$ to output $y$ if it exists, or otherwise returns nil. I.e.:
  
  $$S(F, y) = x \implies F(x) = y$$
  $$S(F, y) = nil \implies !\exists x \hspace{10px}s.t.\hspace{10px} F(x) = y$$
  
  And $S$ takes $1$ millisecond to run (plus the amount of time it takes to read the input and write the output), regardless of $F$ or $y$. $F$ is allowed to include calls to $S$ in itself.
  
  Clearly with this we can solve any NP-Complete problem in constant time (plus the amount of time it takes to read the input and write the output), and in fact we can go further and efficiently solve any optimization problem:
  
  ```
  def IsMin(Cost, MeetsConstraints, x):
    def HasSmaller(y):
      return MeetsConstraints(x) and Cost(y) < Cost(x) and y != x
    return MeetsConstraints(x) and S(HasSmaller, True) == nil
  
  def FindMin(Cost, MeetsConstraints):
    def Helper(x):
      return IsMin(Cost, MeetsConstraints, x)
    return S(Helper, True)
  
  ```
  
  Which means we can do something like:
  
  ```
  def FindSmallestRecurrentNeuralNetworkThatPerfectlyFitsData(Data):
    def MeetsConstraints(x):
      return IsRecurrentNeuralNetwork(x) and Error(x, Data) == 0
    return FindMin(NumParamaters, MeetsConstraints)
  
  ```
  
  And something similar for any other kind of model (random forest, random ensemble of functions, etc.). We can even solve the halting problem with this, which probably means that there is some proof similar to the halting problem proof that shows such an oracle could not exist. Lets assume this exists anyway, as a thought experiment.
  
  But I'm not sure how to take it from here to something that achieves endless self improvement. What exactly the "singularity" even means I suppose is tricky to define formally, but I'm interested in any simple definitions, even if they don't quite capture it.
  
  A sidenote, here is one more function we can do:
  
  ```
  IsEquivalent(G, H):
      def Helper(x):
        return G(x) != H(x)
      return P(Helper, True) == nil
  
  ```
  
  **Tags:** algorithm, optimization, singularity
  
  > **Comments:**
  > **username_1**: "_Clearly with this we can solve any NP-Complete problem_". Note that, in principle, you can  already solve any NP-complete problem, but you need exponential time to do so, unless someone proves $P = NP$: in that case, there would a polynomial-time solution for each NP-complete problem.  
  > **username_1**: In general, in this question, you're talking about something you don't even know well. So, your assumptions and conclusions will likely not lead anyone anywhere. I would encourage you to read the book "Introduction to the Theory of Computation" by Sipser before trying to understand if the singularity is possible.  
  > **username_1**: AFAIK, the singularity is not even a well defined or mathematically formalised problem. You may want to attempt to do that. But I guess you will need to work hard.  
  > **username_0**: @username_1 sorry, I added an edit to clarify what I meant (with this oracle, we would do it very efficiently). I'm not sure where you are getting your assumptions that I don't know these things well: I have read through all of Sipser (it is a good recommendation) and understand complexity classes and such. I'm even a published author in multiple computer science academic conferences.  I know such an oracle (probably) isn't possible, but I don't see why such a thought experiment isn't interesting regardless? There are all kinds of questions we study in computer science about oracles.  
  > **username_0**: @username_1 "the singularity is not even a well defined or mathematically formalised problem" I agree. Another way to phrase my question could be "what kind of self-improving behavior could we get with such an oracle, and how close does this behavior match common intuitions of what the 'singularity' might be?"  
  > **username_1**: I think a better question on this website would be: "Can we define the AI singularity mathematically"? You may want to have a look at [AIXI](https://en.wikipedia.org/wiki/AIXI). Anyway, I think that the oracle (as you define it) would just provide speed of learning.  
  > **username_0**: [Done](https://ai.stackexchange.com/questions/10644/can-we-define-the-ai-singularity-mathematically), thanks for the suggestion, but I feel this question is different enough that I won't remove it.  
  > **username_1**: Regarding AIXI, you may want to have a look at https://ai.stackexchange.com/a/10377/2444.  
  
  ---
  
  ## 0 answers
  
  