Set aside networks, image classification, gradients, and the strength of intelligence for a moment and consider the world before people lit fires.
Fires were started periodically just as they are now, when lightning struck dry deciduous matter. People probably ran for water. Perhaps some smart people learned that fire created warmth at night after a blaze and discovered how to preserve it. They couldn't let it go out. If they did, they'd have to wait through many cold nights until the next forest fire, which could take decades, and then try again.
How did someone invent how to start one without lightning?
The first plow, the first written law, the first bow, the first coin, the first water wheel, the first mechanical clock, the first circuit, the first logo, the first transistor, the first web site.
Now try to imagine it from the other end. There is something important. It has no name. It has no design. It has no method of procurement. If you create one, no one will know what it does or why it is there. But you do. You're its inventor. It began in your brain. You saw it before it existed. It was vision without the involvement of your eyes. You then must bring it into being with your speech or make it with your hands.
This is the rarest, most human, and most precious form of intelligence.
What kind of algorithm can invent? Genetic algorithms have not produced new designs of things that meant nothing to anyone when they appeared but mean something to the computer running the algorithm. Something is missing in the way we perceive intelligence. Maybe it is a kind of negative model, where the empty space represents the thing that needs inventing. How would one create such a model?
Is there something like a virtual die, where the empty space in the universe of utility is highlighted? What kind of algorithm can detect the absence of something without it ever having first existed?
Once that ability is understood, we can then approach the problem of running through a wide array of approaches to create this previously un-invented thing and check each for feasibility, but first we must learn how to artificially envision nameless things that fill previously unimagined niches.
What kind of algorithm can invent?
Addenda in Response to Excellent Comments
This question is dear to me because I've invented things, some for corporations, some for my own laboratory, and some that I failed to push hard enough and someone else invented something very close and developed it first. This last case is interesting, and I've seen it happen many times. It's also common in scientific history, where two people who don't communicate directly simultaneously come up with some scientific or industrial invention.
Reading Alonso Church's interview we find that Alan Turing didn't study under him as most historical accounts state. According to Church, he developed his lambda calculus and Turing developed his machine in parallel and without direct consultation. There is an environmental aspect to invention, as if the world around the inventors are subconsciously searching without a clear objective.
There is an accidental appearance to invention, but everyone I know or read about who invented something was poking around in the area of the invention in their mind, and not just casually. We obsessed over some imaginary search space, hunting for something novel and purposeful.
It is like a rat in a maze that smells cheese but does not know the path. We can't just try all the passageways marking each path to avoid duplicate trials to get to the cheese. We don't know it yet but there is a hole in the ceiling covered with a thin veil. Until we realize there is another level to the maze, we cannot find the cheese. The veil represents the discovery. The passage into the second level where the cheese resides is the novelty.
We could find the hole by accidentally hitting the veil when arbitrarily jumping up and down or with a stray ball when playing a game of toss with another rat, but it would sure be faster if we realized something. We smell cheese but failed to find it. When we doubt our method, we start looking for fissures in the surfaces we haven't yet stepped on. Doubt has something to do with it.
Yes, there is a requirement of some kind of understanding or model of the world that can be altered and tested in imaginary space. This is most obvious in the writings containing the thought experiments of Archemedes (buoyancy principle which led to the relative incompressability of liquids, the first conception of a screw, ...), the thought experiments of Isaac Newton (the two prisms in series, the cannon ball blasted into orbit which led to the entire field of Newtonian physics, ...), and the thought experiments of Turing (the imitation game, computability and the punch tape machine).