Human beings don't need to know all the possible sentences to create a single sentence. The insistence that this creativity can't be quantified and analyzed seems to me sheer mysticism.
The particular example of a problem given, someone who's never had either choosing between rocky road and butterscotch, strikes me as the kind of problem where it is likely that human beings themselves act more or less randomly. Even if it were somehow a non-linear process, non-linear equations are soluble, they're just more difficult. The distinction between P and NP problems seems more relevant from what I understand. But then, quantum computing has all that attention lavished on it because it promises a way to tackle NP problems.
As for adaptability being an essential attribute of human-type awareness, that too strikes me as mysticism. In any event, nature shows us that adaptability and creativity can be approximated by evolution, without any awareness involved at all. If programs were allowed to evolve, so to speak, I'm sure the results would be amazingly creative. I'm not at all sure we'd get human consciousness, but that seems to have been a rare result in nature. What I'm really sure is that we would very likely find most of the results useless, and some positively harmful, and likely deem the whole exercise as an expensive waste.