2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – nbro Feb 17 at 22:27
  • $\begingroup$ 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. $\endgroup$ – nbro Feb 17 at 22:32
  • 1
    $\begingroup$ 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. $\endgroup$ – nbro Feb 17 at 22:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Phylliida Feb 17 at 22:55
  • 1
    $\begingroup$ Done, thanks for the suggestion, but I feel this question is different enough that I won't remove it. $\endgroup$ – Phylliida Feb 17 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.