Well, consider your sort example. I can just shuffle the array randomly until your specification is met, or i can do all the possible things to do until your specification is met. It’s the efficient implementations that are a problem. I can easily program a horrifically inefficient AI—a program just iterates through all programs starting from shortest and runs them for specific number of steps, and puts them against a set of challenges solutions to which are substantially larger than the programs being iterated. If AI is at all possible, that will work.
It is possible to make algorithms for important enough subset of the possible specifications, even though it is impossible in general (e.g. you can specify the halting probability, but you can’t compute it).
Well, consider your sort example. I can just shuffle the array randomly until your specification is met, or i can do all the possible things to do until your specification is met. It’s the efficient implementations that are a problem. I can easily program a horrifically inefficient AI—a program just iterates through all programs starting from shortest and runs them for specific number of steps, and puts them against a set of challenges solutions to which are substantially larger than the programs being iterated. If AI is at all possible, that will work.
It is possible to make algorithms for important enough subset of the possible specifications, even though it is impossible in general (e.g. you can specify the halting probability, but you can’t compute it).