Stuart Kauffman writes about the protein space idea of Smith's. It's an interesting concept but more primary is that a string of codons inhabits configuration (genotype) space as well as protein (phenotype) space. Both spaces together constitute the hyperspace or phase space of the string.
The "walk" through phase space is not a traversal where each site is a dimension of 20 interconnected nodes. Each base pair choice is directly connected to three others, making each codon directly connect to three single point mutations. In typographical space, these nine other values are one "jump" away; three being slightly closer than the others (transitional mutations). In protein space, the alternate codons may be near or far, depending on the effect that the change to the functional utility of protein itself has on the probability that mutation will be propagated. This could be approximated, for a simple model, in terms of average substitutibility, in three dimensions.
What is the combined measure of distance between nodes in phase space if typographical space has Hamming distance and protein space has some king of functional dissimilarity measure? Probability is the common denominator. Hamming distance may be reconceived as log probability and so may functional dissimilarity.
In the big picture, it is not simply the ability for the search through phase space to discover a "winning" amino acid sequence but the utility of it to be sensed by the sensing apparatus of natural selection.
Note: Long jumps through phase space is part of a bigger picture, but one that does a lot less to describe the actual behavior as a Markov process. Intragenic recombination and frame shift mutations are little wormholes through phase space, but they do little to describe evolutionary behavior. It would be interesting to be able to model these dei ex machini but my guess is that their probabilities are very poorly understood.
Treat: Schutzenberger's "Algorithms and the neo-Darwinian Theory of Evolution":
Bonus: Negoro's explanation of why he doesn't think that nylonase resulted from a frame-shift mutation.