There are branches of evolutionary computation that aim to evolve programs. The best known examples are Genetic Programming (GP) and Evolutionary Programming (EP). GP is by far the most popular today, and involves evolving source code, generally in Lisp-like languages where programmatically manipulating source code is a bit easier, but there are also GP approaches that use stack-based languages like Forth or Factor. I'm not aware of anyone trying to evolve code in languages like C++ or Java, but I suppose someone out there has probably experimented with it.
EP is about evolving finite state machines, and from there, you could presumably infer a program in the conventional way, although it might not be particularly nice for humans to read. Neither are the programs learned by GP though, for that matter.
I once experimented with small math calculation programs and found if I added a heuristic for selecting programs with less length, given equal correctness, the former is preferred. This helped evolve shorter more readable programs.
I Was thinking for example, how hard would it be to let an algorithm pick a random number of valid tokens from a language (say java) and the suyccess metric be something like, the amount (or score) of errors that the compiler returns.
Presumably I would expect to see the first few iterations produce nonsense, but maybe after a while, a bot is able to correctly write a variable assignment.
The first obvious problem I see comes from the fact that we know we can have a completely valid piece of code after gibberish and the compiler won't notice the difference.
But what about if there's a compiler able to "score" the "correctness" of the program? that would solve that issue and in theory be able to "learn" how to program, albeit slowly and like you say, most likely not human readable.
Number of syntax errors is extremely weakly predictive of program correctness, and figuring out correctness of arbitrary source code is extremely difficult.
This is why the bread-and-butter of GP is in symbolic regression. Rather than deal with programs that do literally anything, we focus on evolving mathematical expressions. Given a set of data points, can you find a regression equation of some variables that minimize the error on the training data? There are no syntax errors to worry about, no early termination, no control flow, just a small fixed set of arithmetic operators, numbers, and variables. And by keeping the domain in numeric functions, you get a free error metric that is generally sensible.
There is talk in the field about the future -- can you evolve a web browser, for instance -- but this is very futuristic at the moment at least.
But then, I remember doing some work on college about Gödel number (https://en.wikipedia.org/wiki/G%C3%B6del_numbering). Would it be possible for example, to use this as a form of encoding instructions?
Maybe if arbitrary programs are too broad of scope, how about specifically getting only one instruction correct? e.g. to evolve the correct print(message) syntax. Do you have any references to this? it's a fascinating subject!
I don't have any references for it, but evolving correct syntax should be doable I think, at least for smallish scale problems.
Others have mentioned that people have evolved "Hello world" in Brainfuck, so it's definitely possible to do interesting things. It's just too ambitious right now to shoot for actually useful programs.
EP is about evolving finite state machines, and from there, you could presumably infer a program in the conventional way, although it might not be particularly nice for humans to read. Neither are the programs learned by GP though, for that matter.