The prevailing misconception is that by assuming that ‘the future will be like the past’, it can ‘derive’ (or ‘extrapolate’ or ‘generalise’) theories from repeated experiences by an alleged process called ‘induction’. But that is impossible.
He is looking for solutions outside of the distribution that has been previously observed.
Theories that have relevance or potential obey a certain distribution, and it is this distribution that you are trying to sample from. Sure, theories may not be directly derived from the extrapolation of sense data, but they are nonetheless derived from the extrapolation of theories in general. So what you're looking for is not a fundamentally new paradigm, it's more like an additional level of indirection. But there's no point to experiment with multiple induction levels if we can't even make a single one work well enough.
Also, generative or inductive mechanisms have a wider scope of application than prediction. They can be used to inspect your own belief systems and pinpoint inconsistencies: the easiest way to know if your model of the world is inconsistent is to generate ideas and examples that fit the model but trigger contradictions.
But, as the author explains, epistemology doesn't work this way, and is certainly not inductive (maybe high-order inductive -- whatever that means). We don't treat physics as simply "something that works", but as knowledge based on assumptions (codified in symmetry laws) which are not inductive by any means. The laws of symmetry (assumptions, really) are a justification for induction, but can't be a result of induction alone. In fact, all of mathematics is a set of justifications for inductions that humans have developed.
But you don't need to prove them to use them. Many people go around believing unproven theories. In the sciences the preference is for verified theories(and theorems in math) and we prove them by deduction.
But it seems that you know that. I don't understand why you don't like induction in a general algorithm. We don't have to restrict ourselves to a single type of reasoning. Induction, deduction, abduction are all valid and used by humans for generating new knowledge.
I might be misunderstanding something in which case please correct me.
The article says that current research focuses on achieving intelligence by means of induction alone, but induction cannot explain all of intelligence, because we reason in ways that contradict induction (although maybe they're a result of higher-order induction).
Essentially, the idea is that "creativity" is the act of sampling from a distribution over the kind of thing you are trying to create. Learning algorithms like Boltzmann Machines will learn a distribution over the inputs they see. One thing you can do with such a distribution is checking the probability of a given input under it, which may be good to classify them. Another thing you might want to do is generate representative samples, i.e. generate an example E with probability X iff P(E) = X under the model. The latter is what I would call "creativity".
Under this definition, creativity depends on both the learned distribution (which should only assign high probability to meaningful data) and of course on the sampling algorithm. As it turns out, it is very hard to write good sampling algorithms for non-trivial distributions (naive MCMC will often get stuck). So creativity is hard, but so are a lot of other tasks, so I don't think it's fair to single it out.