We don’t need to compare two arbitrary Turing machines to verify an optimization, but we don’t even need to compare two arbitrary Turing machines with an enormous-but-finite arbitrary input space; we just need to compare unoptimized-version-of-code to optimized-version-of-code. That’s a much narrower task. Compilers arguably have a harder task, of comparing human-readable-code with machine-executable-code, and there have been provably correct compilers created even for inelegant languages like C.
I’m not sure about the entire direction of “prove that optimization won’t change our output”, however. A practical AI is likely to be limited by computational resources, right? So if we want to get answers out of it at all, there’s a good chance that we’re going to have to use approximate algorithms such as iterative methods that never reach exact convergence. But then what should a better-optimized AI do with it’s effectively increased computational resources? Terminate the functions at the same, equally inaccurate point, then while(no_new_input()) twiddle_thumbs()? Or use more accurate approximations and/or more iterations to get to a better, but different output?
we just need to compare unoptimized-version-of-code to optimized-version-of-code. That’s a much narrower task.
I don’t think that’s true. The optimised and unoptimised code can be considered as the start of the tape of a fixed Turing machine, or as the operating instructions of different Turing machines. It is important not to conceptualise Turing machines too much in terms of our experience with desktop computers, which are only one particular implementation of the general concept. A computer has hardware, code, and input; a Turing machine just has input and rules. There is an exact equivalence between “What is the output of Turing machine X with input A+B”, and “What is the output of Turing machine X’ with input B”, where A has been absorbed into the machine.
Terminate the functions at the same, equally inaccurate point, then while(nonewinput()) twiddle_thumbs()? Or use more accurate approximations and/or more iterations to get to a better, but different output?
I was speaking of optimisations for speed; presumably you always optimise a bottleneck, so you terminate at the same point and then go on to deal with some other input that was waiting for the response from this particular calculation.
I never claimed that “optimized code” and “unoptimized code” can’t be considered as two different generalized Turing machines; I claimed that two arbitrary different generalized Turing machines might not always be possible outputs of an optimization process. You’re correctly pointing out that “all before-and-after-optimization code pairs are equivalent to pairs of Turing machines”, but that is not the opposite of “not all pairs of Turing machines are before-and-after-optimization codes”. And once you start looking at strict subsets all sorts of impossibilities become possibilities; I can solve the halting problem if you let me pick a sufficiently restricted subset of Turing machines as admissible inputs!
I was also speaking of optimizations for speed, to ask the question: why are you bothering to optimize for speed? The answer isn’t “I want the code to be able to produce the same output in 1/Nth of the time so my computer can idle for (N-1)/Nths of the time”; what we’re really looking to do is let the code produce different, better output. So “will my optimized version produce the exact same output for the exact same input” is only half of the problem; it still isn’t a proof of recursive stability in a realistic use case where after each improvement we’re also changing the input.
You’re correctly pointing out that “all before-and-after-optimization code pairs are equivalent to pairs of Turing machines”, but that is not the opposite of “not all pairs of Turing machines are before-and-after-optimization codes”.
A useful distinction. Thank you.
So “will my optimized version produce the exact same output for the exact same input” is only half of the problem; it still isn’t a proof of recursive stability in a realistic use case where after each improvement we’re also changing the input.
Suppose we have an AI that does two things: Calculate ballistics trajectories for its army of killer robots, and coherently extrapolate human volition to guide its overall goals. If it optimises the ballistics calculation, it can spend more time thinking about the CEV; this will produce a different result (unless it was already at the point of reflective stability), but in this case that’s a good thing. However, the optimised ballistics calculation had better be yielding the same results or it will start losing the war. So I distinguish between two outputs: The output of the specific function being optimised must be the same. The output of the AI as a whole can differ.
We don’t need to compare two arbitrary Turing machines to verify an optimization, but we don’t even need to compare two arbitrary Turing machines with an enormous-but-finite arbitrary input space; we just need to compare unoptimized-version-of-code to optimized-version-of-code. That’s a much narrower task. Compilers arguably have a harder task, of comparing human-readable-code with machine-executable-code, and there have been provably correct compilers created even for inelegant languages like C.
I’m not sure about the entire direction of “prove that optimization won’t change our output”, however. A practical AI is likely to be limited by computational resources, right? So if we want to get answers out of it at all, there’s a good chance that we’re going to have to use approximate algorithms such as iterative methods that never reach exact convergence. But then what should a better-optimized AI do with it’s effectively increased computational resources? Terminate the functions at the same, equally inaccurate point, then while(no_new_input()) twiddle_thumbs()? Or use more accurate approximations and/or more iterations to get to a better, but different output?
(edited to fix markup; thanks army1987)
Underscores are for italics in Markdown. To get “no_new_input”, write
no\_new\_input.I don’t think that’s true. The optimised and unoptimised code can be considered as the start of the tape of a fixed Turing machine, or as the operating instructions of different Turing machines. It is important not to conceptualise Turing machines too much in terms of our experience with desktop computers, which are only one particular implementation of the general concept. A computer has hardware, code, and input; a Turing machine just has input and rules. There is an exact equivalence between “What is the output of Turing machine X with input A+B”, and “What is the output of Turing machine X’ with input B”, where A has been absorbed into the machine.
I was speaking of optimisations for speed; presumably you always optimise a bottleneck, so you terminate at the same point and then go on to deal with some other input that was waiting for the response from this particular calculation.
I never claimed that “optimized code” and “unoptimized code” can’t be considered as two different generalized Turing machines; I claimed that two arbitrary different generalized Turing machines might not always be possible outputs of an optimization process. You’re correctly pointing out that “all before-and-after-optimization code pairs are equivalent to pairs of Turing machines”, but that is not the opposite of “not all pairs of Turing machines are before-and-after-optimization codes”. And once you start looking at strict subsets all sorts of impossibilities become possibilities; I can solve the halting problem if you let me pick a sufficiently restricted subset of Turing machines as admissible inputs!
I was also speaking of optimizations for speed, to ask the question: why are you bothering to optimize for speed? The answer isn’t “I want the code to be able to produce the same output in 1/Nth of the time so my computer can idle for (N-1)/Nths of the time”; what we’re really looking to do is let the code produce different, better output. So “will my optimized version produce the exact same output for the exact same input” is only half of the problem; it still isn’t a proof of recursive stability in a realistic use case where after each improvement we’re also changing the input.
A useful distinction. Thank you.
Suppose we have an AI that does two things: Calculate ballistics trajectories for its army of killer robots, and coherently extrapolate human volition to guide its overall goals. If it optimises the ballistics calculation, it can spend more time thinking about the CEV; this will produce a different result (unless it was already at the point of reflective stability), but in this case that’s a good thing. However, the optimised ballistics calculation had better be yielding the same results or it will start losing the war. So I distinguish between two outputs: The output of the specific function being optimised must be the same. The output of the AI as a whole can differ.