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
