Complete randomization is possible in Software. If creativity is just about choosing a new random thing and then evaluating if that thing is better or not than the previous instance, AIs then can be creative.
They just need to do billions of those randomizations in a second and pick one. Which is not hard.
They can even use their own hallucinations as a source for creativity.