Given a program, finding another program that has the same input to output map is much easier than given two programs, determining if they have the same input to output map.
The halting problem and similar are generally not practical problems when you are deliberately constructing your programs with analyzable structure, and you are willing to require that programs not just have a desired property, but that they provably have the desired property.
Given a program, finding another program that has the same input to output map is much easier than given two programs, determining if they have the same input to output map.
This is interesting. Do you have any sources that discuss why this is so?
Given a program, finding another program that has the same input to output map is much easier than given two programs, determining if they have the same input to output map.
This is interesting. Do you have any sources that discuss why this is so?
I have a short proof: suppose we have some program, A. And some program that provably does nothing, B.
Run first B, then A. Presto, a new program with output identical to A. Depending on whether A is a black box or some structure you can reason about, you can also hoist B up into the body of A. Again, provably output identical to A.
The underlying reason this is easier than proving general equivalence of programs is that we picked specific program B with a well-known behavior. Trying to prove two programs equivalent would be trying to reason about all possible modifications, rather than some one specific patch.
You can prove that a smaller set of transformations preserve the behavior of subsections of a program, then you can combine arbitrarily many of those transformations and preserve the input to output map of a larger program.
This comes from my direct experience programming computers.
Making small changes to a program which do not affect its input output map is usually trivially easy, and IDEs such as Eclipse and Visual Studios include tools to make such changes for you, such as extracting a section of code into a method, and replacing that section of code with a call to that method. In general this is called refactoring, and its common forms tend to be useful preparations for more substantial changes.
With respect to optimization, a program that is well organized into methods which hide implementation details can be changed by replacing a method with one that performs the same function with a more efficient implementation. Sometimes a strict refactoring is not required, you just have to preserve the properties that callers of the method rely on. For example, if you have a method which sorts a list, and you only care that the sorted list reflects the ordering, you could replace it using an algorithm with different behavior with respect to elements that are equivalent by the ordering. More to the point, if you have a chess AI that searches the game tree as deep as it can in a certain time, and you optimize the search, you are happy that the AI produces different output as long as it still outputs the best move it finds according to its deeper search of the game tree. For similar reasons, an AGI should produce better output in real time if it substantially optimizes its own efficiency.
Asking if you can determine if arbitrary have the same output is really a wrong question. Ask if you can construct a better program that has the same properties you care about.
I also have some experience in programming, but I think you are focusing too narrowly on human techniques. Humans have discovered a certain toolkit for optimisations, and they proceed as you say. But note that we usually optimise for readability and maintainability of the code, not for speed. Refactorings such as putting some code in a separate method will actually slow you down slightly, since you get the overhead of an extra stack frame—unless of course the compiler inlines the method for you!
A useful AI, however, is not constrained by human limitations; if it were, we wouldn’t build it. It can construct completely bizarre code; it doesn’t necessarily make small changes to existing code. Think of the evolved circuit that discriminates between high and low frequencies: No human engineer would ever build such a thing, and certainly you would never arrive at it by deliberately making small working modifications to an existing, working circuit. But an AI might arrive at such a thing, or its equivalent in code, by trial and error, and then need to prove that the output is still the same.
An AI is not constrained to write human maintainable code because the AI can maintain more complicated code than humans. But the AI’s code will still have structure that the AI understands and uses to manage the complexity.
I do not expect an AI to write code by trial and error, so I am not worried about difficulties with that approach.
I respectfully suggest that you are not thinking Weirdly enough. Notice that the evolved circuit still has structure that the laws of physics understand! An AI needn’t operate directly at that level to make intuitive leaps beyond the capability of any human; and needn’t operate by trial and error, precisely, (although, notice, we don’t know the internal structure of generating an insight in human brains; for all we know it involves subconsciously trying a hundred different paths and discarding most of them) to generate stuff that’s very different from the code it starts with.
I respectfully suggest that you are not thinking Weirdly enough.
Thinking Weirdly has nothing to do with it. I expect an AI to not use programming techniques it doesn’t expect to be able to use effectively, and I expect the AI’s expectations to use techniques effectively to be accurate. So, given that an AI is using a technique, even if it is Weird, I expect the AI to be effective using it. If you have an argument that a certain technique, like random guessing and checking, has insurmountable problems, then you have an argument that an AI will not use that technique. Given that the AI is using a Weird technique, I expect the AI to be advanced enough to cope with, and benefit from, the Weirdness.
Notice that the evolved circuit still has structure that the laws of physics understand!
The laws of physics can only understand the structure in a poetic sense. When I say that an AI understands the structure of its code, I mean that it has a map of the code, organized into logical components with information (not required to actually run the program) about high level properties components have and how other components rely on those properties, and this information is available and useful to modifying the code in good ways.
An AI needn’t operate directly at that level to make intuitive leaps beyond the capability of any human; and needn’t operate by trial and error, precisely, (although, notice, we don’t know the internal structure of generating an insight in human brains; for all we know it involves subconsciously trying a hundred different paths and discarding most of them) to generate stuff that’s very different from the code it starts with.
It doesn’t matter if the AI makes leaps beyond the capability of any human as long as it doesn’t make leaps beyond its own capability. You seem much more eager to apply Weirdness to difficulty of the problem than to capability of solving the problem. It doesn’t matter that understanding the AI’s Weird code is too hard for humans, because it’s not too hard for the Weird AI. The AI may “generate stuff that’s very different from the code it starts with”, but it won’t generate anything so different the AI can’t verify it is a good change.
If you don’t want to face that problem, surely you can just constrain the machine to write readable code.
A complicated refeactoring that is difficult to show whether it does the same thing could be discarded. What is needed most is a path forward, not the ability to traverse any possible path that leads forwards.
It seems likely that there will be a tradeoff between progress speed and safety, with “looking for a proof” being the slowest approach. Such a technique seems relatively unlikely to be effective if applied during a race.
What’s the use of an AI that writes code I could have written myself? If that’s the case, cut out the middleman and just write the damn stuff! I specifically want an AI that’s smarter than me, otherwise I have no use for it.
It seems likely that there will be a tradeoff between progress speed and safety, with “looking for a proof” being the slowest approach. Such a technique seems relatively unlikely to be effective if applied during a race.
Yes, this is true. That’s a problem. We don’t want the first AI that FOOMs effectively to win. We want a provably Friendly AI to win. If we demonstrate that proving Friendliness has constraints that don’t apply generally, we still cannot abandon the constraints! That defeats the entire purpose!
What’s the use of an AI that writes code I could have written myself?
I’m confused. Isn’t this sort of thing what most machines are for? You might just as well ask, “What’s the use of a clothes-washing machine, when I could’ve just washed all of the clothes by hand?”
This is a good point, but there are two objections. First, the washing machine lets you substitute one kind of effort for another and thus use comparative advantage. I can earn enough money for a washing machine in much less time than the total time saved over the lifetime of the washing machine. With an AI, code is code; there’s no comparative advantage in writing code to instead of writing code.
Second, in referring to “code I could have written myself”, I was referring to qualitative advantages rather than time saved. To make the washing-machine analogy work with this, postulate a washing machine that doesn’t actually save you any time—maybe you have to sit about cranking a driving shaft for two hours—but produces much cleaner clothes, or a smaller chance of ripping, or some other qualitative measure.
I note that automatic code generators we have already, in some cases built into the language features, like templates in C++. They’re occasionally useful but not likely to FOOM on us.
First, the washing machine lets you substitute one kind of effort for another and thus use comparative advantage.
‘Comparative advantage’ needs exchanging one kind of effort for another because it’s a law regarding trade amongst humans. What you’re looking for is mechanical advantage, which often involves trading work for more work.
With an AI, code is code; there’s no [mechanical] advantage in writing code to instead of writing code.
No. If you spend 1 day writing code for an AI and then it writes all your code from now on, you’ve saved an arbitrarily large amount of time writing code.
Second, in referring to “code I could have written myself”, I was referring to qualitative advantages rather than time saved.
Well your question was “What’s the use of an AI...?”, to which I could legitimately bring up all sorts of advantages you hadn’t been referring to. If you had said, “What’s the use of a chicken when it can’t even dance?” I could respond “I could eat it” and presumably that would be an answer to your question.
To make the washing-machine analogy work with this, postulate a washing machine that doesn’t actually save you any time—maybe you have to sit about cranking a driving shaft for two hours—but produces much cleaner clothes, or a smaller chance of ripping, or some other qualitative measure.
Your washing machine does still sound preferable to hand-washing, so I’m not sure what the point was.
I’m terribly confused as to what your point was, or why you think a code-writing machine would be useless. I want one!
Ok, yes, an AI that saves me the effort of writing code would be useful, fair enough. I think, however, that in the context of writing a FOOMing Friendly AI, code that I could have written is not going to be sufficient.
We don’t want the first AI that FOOMs effectively to win. We want a provably Friendly AI to win.
This seems as though it is framing the problem incorrectly to me. Today’s self-improving systems are corporations. They are a mix of human and machine components. Nobody proves anything about their self-improvement trajectories—but that doesn’t necessarily mean that they are destined to go off the rails. The idea that growth will be so explosive that it can’t be dynamically steered neglects the possibility of throttles.
A “provably-Friendly AI” doesn’t look very likely to win—so due attention should be give to all the other possibilities with the potential to produce a positive outcome.
Given a program, finding another program that has the same input to output map is much easier than given two programs, determining if they have the same input to output map.
This is interesting. Do you have any sources that discuss why this is so?
The second problem is equivalent to the halting problem. The first problem isn’t.
Given a program, finding another program that has the same input to output map is much easier than given two programs, determining if they have the same input to output map.
The halting problem and similar are generally not practical problems when you are deliberately constructing your programs with analyzable structure, and you are willing to require that programs not just have a desired property, but that they provably have the desired property.
This is interesting. Do you have any sources that discuss why this is so?
I have a short proof: suppose we have some program, A. And some program that provably does nothing, B.
Run first B, then A. Presto, a new program with output identical to A. Depending on whether A is a black box or some structure you can reason about, you can also hoist B up into the body of A. Again, provably output identical to A.
The underlying reason this is easier than proving general equivalence of programs is that we picked specific program B with a well-known behavior. Trying to prove two programs equivalent would be trying to reason about all possible modifications, rather than some one specific patch.
You can prove that a smaller set of transformations preserve the behavior of subsections of a program, then you can combine arbitrarily many of those transformations and preserve the input to output map of a larger program.
This comes from my direct experience programming computers.
Making small changes to a program which do not affect its input output map is usually trivially easy, and IDEs such as Eclipse and Visual Studios include tools to make such changes for you, such as extracting a section of code into a method, and replacing that section of code with a call to that method. In general this is called refactoring, and its common forms tend to be useful preparations for more substantial changes.
With respect to optimization, a program that is well organized into methods which hide implementation details can be changed by replacing a method with one that performs the same function with a more efficient implementation. Sometimes a strict refactoring is not required, you just have to preserve the properties that callers of the method rely on. For example, if you have a method which sorts a list, and you only care that the sorted list reflects the ordering, you could replace it using an algorithm with different behavior with respect to elements that are equivalent by the ordering. More to the point, if you have a chess AI that searches the game tree as deep as it can in a certain time, and you optimize the search, you are happy that the AI produces different output as long as it still outputs the best move it finds according to its deeper search of the game tree. For similar reasons, an AGI should produce better output in real time if it substantially optimizes its own efficiency.
Asking if you can determine if arbitrary have the same output is really a wrong question. Ask if you can construct a better program that has the same properties you care about.
I also have some experience in programming, but I think you are focusing too narrowly on human techniques. Humans have discovered a certain toolkit for optimisations, and they proceed as you say. But note that we usually optimise for readability and maintainability of the code, not for speed. Refactorings such as putting some code in a separate method will actually slow you down slightly, since you get the overhead of an extra stack frame—unless of course the compiler inlines the method for you!
A useful AI, however, is not constrained by human limitations; if it were, we wouldn’t build it. It can construct completely bizarre code; it doesn’t necessarily make small changes to existing code. Think of the evolved circuit that discriminates between high and low frequencies: No human engineer would ever build such a thing, and certainly you would never arrive at it by deliberately making small working modifications to an existing, working circuit. But an AI might arrive at such a thing, or its equivalent in code, by trial and error, and then need to prove that the output is still the same.
An AI is not constrained to write human maintainable code because the AI can maintain more complicated code than humans. But the AI’s code will still have structure that the AI understands and uses to manage the complexity.
I do not expect an AI to write code by trial and error, so I am not worried about difficulties with that approach.
I respectfully suggest that you are not thinking Weirdly enough. Notice that the evolved circuit still has structure that the laws of physics understand! An AI needn’t operate directly at that level to make intuitive leaps beyond the capability of any human; and needn’t operate by trial and error, precisely, (although, notice, we don’t know the internal structure of generating an insight in human brains; for all we know it involves subconsciously trying a hundred different paths and discarding most of them) to generate stuff that’s very different from the code it starts with.
Thinking Weirdly has nothing to do with it. I expect an AI to not use programming techniques it doesn’t expect to be able to use effectively, and I expect the AI’s expectations to use techniques effectively to be accurate. So, given that an AI is using a technique, even if it is Weird, I expect the AI to be effective using it. If you have an argument that a certain technique, like random guessing and checking, has insurmountable problems, then you have an argument that an AI will not use that technique. Given that the AI is using a Weird technique, I expect the AI to be advanced enough to cope with, and benefit from, the Weirdness.
The laws of physics can only understand the structure in a poetic sense. When I say that an AI understands the structure of its code, I mean that it has a map of the code, organized into logical components with information (not required to actually run the program) about high level properties components have and how other components rely on those properties, and this information is available and useful to modifying the code in good ways.
It doesn’t matter if the AI makes leaps beyond the capability of any human as long as it doesn’t make leaps beyond its own capability. You seem much more eager to apply Weirdness to difficulty of the problem than to capability of solving the problem. It doesn’t matter that understanding the AI’s Weird code is too hard for humans, because it’s not too hard for the Weird AI. The AI may “generate stuff that’s very different from the code it starts with”, but it won’t generate anything so different the AI can’t verify it is a good change.
If you don’t want to face that problem, surely you can just constrain the machine to write readable code.
A complicated refeactoring that is difficult to show whether it does the same thing could be discarded. What is needed most is a path forward, not the ability to traverse any possible path that leads forwards.
It seems likely that there will be a tradeoff between progress speed and safety, with “looking for a proof” being the slowest approach. Such a technique seems relatively unlikely to be effective if applied during a race.
What’s the use of an AI that writes code I could have written myself? If that’s the case, cut out the middleman and just write the damn stuff! I specifically want an AI that’s smarter than me, otherwise I have no use for it.
Yes, this is true. That’s a problem. We don’t want the first AI that FOOMs effectively to win. We want a provably Friendly AI to win. If we demonstrate that proving Friendliness has constraints that don’t apply generally, we still cannot abandon the constraints! That defeats the entire purpose!
I’m confused. Isn’t this sort of thing what most machines are for? You might just as well ask, “What’s the use of a clothes-washing machine, when I could’ve just washed all of the clothes by hand?”
This is a good point, but there are two objections. First, the washing machine lets you substitute one kind of effort for another and thus use comparative advantage. I can earn enough money for a washing machine in much less time than the total time saved over the lifetime of the washing machine. With an AI, code is code; there’s no comparative advantage in writing code to instead of writing code.
Second, in referring to “code I could have written myself”, I was referring to qualitative advantages rather than time saved. To make the washing-machine analogy work with this, postulate a washing machine that doesn’t actually save you any time—maybe you have to sit about cranking a driving shaft for two hours—but produces much cleaner clothes, or a smaller chance of ripping, or some other qualitative measure.
I note that automatic code generators we have already, in some cases built into the language features, like templates in C++. They’re occasionally useful but not likely to FOOM on us.
‘Comparative advantage’ needs exchanging one kind of effort for another because it’s a law regarding trade amongst humans. What you’re looking for is mechanical advantage, which often involves trading work for more work.
No. If you spend 1 day writing code for an AI and then it writes all your code from now on, you’ve saved an arbitrarily large amount of time writing code.
Well your question was “What’s the use of an AI...?”, to which I could legitimately bring up all sorts of advantages you hadn’t been referring to. If you had said, “What’s the use of a chicken when it can’t even dance?” I could respond “I could eat it” and presumably that would be an answer to your question.
Your washing machine does still sound preferable to hand-washing, so I’m not sure what the point was.
I’m terribly confused as to what your point was, or why you think a code-writing machine would be useless. I want one!
Ok, yes, an AI that saves me the effort of writing code would be useful, fair enough. I think, however, that in the context of writing a FOOMing Friendly AI, code that I could have written is not going to be sufficient.
We’re in agreement.
This seems as though it is framing the problem incorrectly to me. Today’s self-improving systems are corporations. They are a mix of human and machine components. Nobody proves anything about their self-improvement trajectories—but that doesn’t necessarily mean that they are destined to go off the rails. The idea that growth will be so explosive that it can’t be dynamically steered neglects the possibility of throttles.
A “provably-Friendly AI” doesn’t look very likely to win—so due attention should be give to all the other possibilities with the potential to produce a positive outcome.
The second problem is equivalent to the halting problem. The first problem isn’t.
You might want to edit your second paragraph. The grammar seems to be a bit garbled, to the extent that I can’t figure out what you are trying to say.
Yes, there were missing words. Fixed.