I think grammars are a way to formalize this intuition of novelty (NB: grammars can be use to generate as well as to parse). Noise is like a stream of random symbols from an alphabet - anything is possible; most all of it boring. A grammar carves out a subset of the possible streams, only those with certain relationships between the symbols.

Regular expressions are a simple kind of grammar (aka "Regular Grammars") - you can see generation as choices made for explicit choice operators ("|"), and choices of whether to loop ("∗") or continue. Although limited, they can be surprisingly expressive. Context Free Grammars allow you to generate things that have the basic structure of xml, json and source code. And you can have Turing Equivalent grammars that, in describing a subset, can compute anything.

Of course, grammars aren't restricted to the Chomsky Hierarchy, but can include any way of describing the subset of streams (or generating an instance of them) - for example, the recent HN travesty/markov generators.

You can search for the right grammar (machine learning), by taking a corpus of instances of what you want to generate, and test out your grammar, by seeing how well it compresses them. This shows whether it is capturing regularities within them and between them - the rules or laws that are the essence of a grammar. In doing this, you should also take into account the size of the grammar itself: consider the extremes of one grammar that factors out deep regularities; versus one that is simply a choice between each instance, verbatim (this compresses real well: it just needs to encode which instance. i.e. log2(1/N) bits, e.g. 8 bits to encode which of 256 different instances, assuming uniform probability). Accounting for the complexity of the grammar avoids this.

This comes down to the length of the description of the instances + the length of the description of the grammar.

( "Model" is probably a better term than "grammar", since it doesn't imply a sequence. )

Re: your last point, there's no theoretical reason that an extremely accurate model must be computationally expensive to execute (e.g. flocking behaviour was simpler than expected; and Occam's Razor gives us hope) - but it might well be computationally expensive to discover in the first place. e.g. require many great leaps of intuition by humans. (Even if it's obvious in hindsight.)

The trailer looks a little repetitive to me - esp the yellow underwater plants; and the trees seem to be random blocks of foliage - like minecraft trees or github icons, just rendered nicer. I don't want to criticize, as they probably have some cool innovations hidden away in there.

What I'd like is gameplay-significant procedural generation. e.g. trees you can climb, so their shape affects where you can reach and how. Terrain - mountains, streams - naturally has this effect. Then, developers have to make it work right! So far, only the minecraft/dwarf fortress genres do this. Because generation is fundamental to their concept, their gameplay, and why people like the games, I suspect that that genre is where we'll eventually get the hi-res breakthroughs - whereas for every other genre, including "No Man's Sky", if their gameplay isn't 100% dependent on generation, whenever there's a conflict between the two, generation will lose (crunch time! what must be finished to ship?). Servant of two masters etc.

FWIW I still think FarCry2 (not 3) creates the most immersive world so far. Hopefully something even better will be done for nextgen consoles/PCs, as opposed to just higher resolution and higher gamification.