I don't see why it's a paradox. Lots of things would offer fitness - why can't all animals talk? Why can't plants move? Surely these things would offer greater Darwinian fitness.
"Surely these things would offer greater Darwinian fitness" is as basic a mistake as "Surely we can figure out whether this program will halt without running it".
EDIT: In fact, as I think about it, there is a deep connection between the thought "Knowing the genes of this organism, we may predict its fitness" and "Knowing the instructions of this program, we may predict its halting". I'd love to see a paper on that.
And then, this "smooth path" idea relates neatly with topological notions of computability.
Evolution is much the same, but most people are worse at it because they make the mistake of prioritizing human-values as evolutionary advantages for all species.
For example, cows get slaughtered by the billion by humans. But they're an evolutionary success story from a Darwinian perspective: by being easy to domesticate by early tribes and delicious, they've proliferated far beyond anything which would've happened un-aided by humans.
Of course, there are simple and trivial programs that can be specifically analyzed, but we're definitely not to that level on any of the stuff under discussion here. The analogy really is pretty apt.
But that's the nature of the problem: you know it halts because just executed it till it halts.
while(i>0) { i * 2; }
Turing proved that for some programs there is nothing we can do but run them and see. That doesn't mean that's all we can ever do.
Lamarckian and Darwinian evolution were debated and Darwin won. Lamarck's Lemma, which is a term I made up, points out that, were a random walk to create a mechanism for Lamarckian evolution, Darwinian evolution might well keep it around, as it could offer fitness.
That's why I phrase it as a lemma on Darwin's theory: even if it proves true, as epigenetics suggests, it doesn't make Lamarckian thinking correct. If anything, the opposite: it shows that Lamarckian effects can be explained through natural selection.
Plants can of course move, the classic example being the sensitive plant. Whether or not non-human animals can "talk" depends, basically, on whether one means "signalling" or "language proper". The bee dance can give arbitrarily complex instructions in one particular domain: there is no 'one' bee dance, each performance is roughly as unique as a sentence or so of text.
there is at least one animal that we know is able to talk, at least in our definition of "talk" - this animal is humans, so the Evolution did produce a talking animal.
It is a fallacy to assume that evolution is linear, and that it progresses toward some sort of universal optimum. There is no universal optimum. There are only specific, local optima.
A good example is the megalodon. From all we know, the megalodon was basically a massive, faster, more badass, more ferocious version of the great white shark. Why did the megalodon die out, and the lines that led to the great white survive? Surely big-badassedness is a desirable quality in an apex predator like a shark, right? Well, not really, because circumstances changed. Ocean temperatures changed, prey got scarcer and smaller, and eventually, size became a detriment. Megalodon was too big not to fail. What fit one day no longer fit the next.
The same thing may happen to humans someday, and some other animal may step up to take our places. It seems unlikely, but nature is the one doing the "selecting" in natural selection -- not us. Environments and circumstances change, and as they change, so do the criteria that "fit" the new context. In the Darwinian sense, "fit" refers to suitability to a habitat; it does not refer to "fitness" in the modern sense of the word. Think "product/market fit," not "physically fit."
Not necessarily for plants. They do in fact move. They just do it differently. They have no problem spreading their DNA throughout the world via seeds and pollen. They use a lot less energy too, compared with sprouting legs and getting up to walk around. If they did this, they would likely require much greater quantities of food, including protein, which would put plants at a disadvantage.
In any case, plants have also evolved on a completely different fitness track than that of animals. Plants have evolved incredible manipulation of chemistry, far beyond what humans can produce today, let alone even understand.
I recently finished reading Botany of Desire (Michael Pollan) where he describes how plants have co-evolved with humans, appealing to our selection of flowers, fruits, and vegetables to further distribute their DNA. Who's actually farming who? Interesting stuff.
this is why we have live organisms that able to move - it is called animals, and we have animals that can talk, and we'll possibly have [some milleniums later] animals that are able to efficiently transfer memory through DNA (possibly after these animals become able to calculate and select what memories they'd like to encode into their own DNAs and what of these memories they want to transfer to the offsprings)... Evolution isn't finished as of today, it is possibly only starting :)