5 ms·

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 t

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?).

doop 13y ago
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.
- taliesinb 13y ago
  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?
  - doop 13y ago
    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.
    - taliesinb 13y ago
      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 http://news.ycombinator.com/item?id=5931434
      - doop 13y ago
        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.
        taliesinb 13y ago
        > 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?
        13y ago
pbsd 13y ago
> 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.pdf http://www.inf.usi.ch/faculty/shrimpton/spring09/damgard89.p... [2] http://www.cosic.esat.kuleuven.be/publications/article-132.pdf http://www.cosic.esat.kuleuven.be/publications/article-132.p... [3] http://ice.mat.dtu.dk/slides/KeccakIcebreak-slides.pdf http://ice.mat.dtu.dk/slides/KeccakIcebreak-slides.pdf
- taliesinb 13y ago
  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!

doop 13y ago

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.

taliesinb 13y ago
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?
- doop 13y ago
  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.
  - taliesinb 13y ago
    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 http://news.ycombinator.com/item?id=5931434
    - doop 13y ago
      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.
      - taliesinb 13y ago
        > 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?
        13y ago

pbsd 13y ago

> 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.pdf http://www.inf.usi.ch/faculty/shrimpton/spring09/damgard89.p... [2] http://www.cosic.esat.kuleuven.be/publications/article-132.pdf http://www.cosic.esat.kuleuven.be/publications/article-132.p... [3] http://ice.mat.dtu.dk/slides/KeccakIcebreak-slides.pdf http://ice.mat.dtu.dk/slides/KeccakIcebreak-slides.pdf

taliesinb 13y ago
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!