Hacker News Reader

Comment by taliesinb | Hacker News Reader

I'm a Wolfram science summer school instructor, so I'm in a position to see the kinds of trends there are towards NKS-style methods. It's slow, but definitely there. Some of it is directly inspired, some of it is 'convergent evolution'.

Here's a very high-level and eclectic list of themes and specific research directions I can remember off-hand: agent-based modeling in economics and operational research, game theory automata in evolutionary biology, lattice gas methods in fluid dynamics, tessellation-based approaches to solving PDAs, L-systems in architectural design, logic automata for programming array-based computers, cellular automata-based PRNGs for stream ciphers, program search for finding lock-free concurrent algorithms, rBMs as used in deep learning.

In fact, I used an exhaustive NKS-style search the other day to find novel data query primitives (i.e. what other functions live in the type-signature space that MapReduce occupies?).

View on HN

> cellular automata-based PRNGs for stream ciphers

This is something that kind of died in the late 80s. One of the most noteworthy cases was Damgard's CA-based hash function in the paper that proved collision-resistance of the Merkle-Damgard mode [1]. It was quickly broken [2]. The SHA-3 winner, Keccak, has roots in CA-based designs [3], but at this point it's little more than an historical footnote.

[1] http://www.inf.usi.ch/faculty/shrimpton/spring09/damgard89.p...

[2] http://www.cosic.esat.kuleuven.be/publications/article-132.p...

[3] http://ice.mat.dtu.dk/slides/KeccakIcebreak-slides.pdf

For 2, I think it was overly ambitious to think that within a program family so small it has only 88 members there would be one ideal hash function. And If you compare the simplicity of Damgard's design to the contortions that modern hash designs employ to stymy cryptanalysis, it's hard to think that more designs constructions wouldn't perform better, even on that particular automaton.

For 3, I think having a full 7 slides of Bertoni et al's slide deck devoted to the influence of CA-based cryptography on SHA-3 makes it fair to call the approach influential.

Thanks for the references!

I was under the impression that lattice gas methods in CFD were more or less obsolete. They're nice in that they're unconditionally stable and only use bitwise operations, but the amount of CPU time you save from this is massively outweighed by the number of simulation runs you need to do to average out the noise. They're also not Galilean invariant (at least not without messing around with rescaling factors). Lattice Boltzmann is much more practical.

Right, but fundamentally Lattice Boltzmann is just an optimization on top of lattice gas automata. It's continuum-ing up from a CA rather than discretizing down from Navier-Stokes.

And the Galilean invariance thing is kinda cool: who knew that you didn't need something as fundamental as Galilean invariance?

You can see it as continuum-ing up from a CA, or you can see it as a discretization of the continuum Boltzmann equation.

What do you mean you don't need Galilean invariance? In the real world, fluid motion is Galilean invariant (unless you're talking relativistic motion, which is a whole other class of thing that lattice gases have trouble with). You might be simulating something but it sure ain't a Navier-Stokes fluid.

Aha! Physical fluids aren't Naiver Stokes, which is just a continuum approximation that was invented before atoms were even a scientifically established idea. Which of course you know already, but it means it is begging the question a little to say "you might be simulating something but it sure ain't a Navier-Stokes fluid".

For Galilean invariance, I've previously waxed philosophic about why I think that's a feature, not a bug (at least, pedagogically): http://news.ycombinator.com/item?id=5931434

They might not be strictly Navier-Stokes but the way in which real fluids deviate from N-S is completely unlike the way in which lattice gas fluids deviate from N-S. Absolutely, you can discretize time and space and get a useful fluid model, and (as Wolfram showed in a very good paper in 1986) you don't even have to worry too much about isotropy, as long as your lattice obeys certain constraints. You do need Galilean invariance, though.

Look, I do get your point about lattice gas fluids being interesting conceptually, and I do think they make an interesting point about how little you can get away with and still yield a useful fluid model at the macro scale, but I don't think they're a good example of a trend towards NKS-style methods. If anything the trend in that field since the late 90s has been away from NKS and towards seeing the lattice Boltzmann method as a solver for continuum treatments at the Boltzmann (rather than N-S) level.

> the way in which real fluids deviate from N-S is completely unlike the way in which lattice gas fluids deviate from N-S

Can you describe more how the deviations deviate? Specifically, how do these differences affect numerical solutions?

> If anything the trend in that field since the late 90s has been away from NKS and towards seeing the lattice Boltzmann method as a solver for continuum treatments at the Boltzmann (rather than N-S) level.

Also, which continuum are you referring to here? Number of particles? Lattice spacing?

Off the top of my head (it's quite a while..), lattice gas models wind up giving you a velocity-dependent viscosity, i.e. the viscosity of the fluid is a function of how fast it is travelling relative to the lattice. This is unphysical to say the least: while I think you can apply some sort of rescaling to alleviate it, it doesn't make it any easier to get to high Reynolds number flows: that and the huge amount of averaging make lattice gas rather impractical compared to later methods.

> Also, which continuum are you referring to here? Number of particles? Lattice spacing?

By continuum I mean you write down the continuum Boltzmann equation, i.e. a partial differential equation for the evolution of the single particle distribution function. You can then discretize this onto a lattice to recover the lattice Boltzmann method.

Lattice Boltzmann have these same weaknesses (whether one cares as you say depends on the Reynolds regime). Point is, starting from the "simplest possible gas program" has yielded a useful branch of CFD, and one would have thought it extremely unlikely to work if you used intuition from traditional mathematics... It's as discrete and analytically intractable as you get.

Anyway, to me, the continued application of these methods is one data point that NKS-like methods are proving useful across a variety of domains.

Err, no it doesn't - the viscosity in LB is a function purely of the relaxation time (for LBGK anyway). Nor do you need to do any simulation repeats to average out the noise. The main weakness of LB is that it's not as numerically stable as a lattice gas method.

Ooops -- just saw this! My mistake!

Reply on news.ycombinator.com