As a simple metric in the most general case, a program generating an output might get a 1 for providing the desired output, a zero for providing an incorrect output, and a −1 for not terminating within some finite time, or crashing. Given a program which terminates on all inputs, we could say there is some implicit “goal” output, which is described by the program behavior. In this case, all terminating programs are rational given their output as the goal, but (unfortunately for the current argument,) the fraction of programs which fulfill this property of terminating on some output is uncomputable[4].
The more interesting question is how uncomputable/how complicated is the problem actually is?
Is this the upper bound on complexity, or is it even more undecidable/complex?
I agree that’s a more interesting question, and computational complexity theorists have done work on it which I don’t fully understand, but it also doesn’t seem as relevant for AI safety questions.
You should probably also talk to computability/recursion theorists, who can put problems on scales of complexity mirroring the polynomial and exponential time hierarchies that define complexity theory.
The more interesting question is how uncomputable/how complicated is the problem actually is?
Is this the upper bound on complexity, or is it even more undecidable/complex?
I agree that’s a more interesting question, and computational complexity theorists have done work on it which I don’t fully understand, but it also doesn’t seem as relevant for AI safety questions.
True, it’s not that relevant.
You should probably also talk to computability/recursion theorists, who can put problems on scales of complexity mirroring the polynomial and exponential time hierarchies that define complexity theory.