Computational Power of Particle Methods

The computational power of a compute model determines the class of problems it can solve. Automata theory allows describing the computational power of abstract machines (automata) and the problems they can solve. At the top of the Chomsky hierarchy of formal languages and grammars are Turing machines, the most powerful automata, which resemble the concept on which most modern computers are built. Here, we investigate the computational power of particle methods, a well-established class of algorithms with applications in scientific computing and computer simulation. Although particle methods can be interpreted as automata based on their formal definition, their computational power has so far not been studied. We address this by analyzing Turing completeness of particle methods. In particular, we prove two sets of restrictions under which a particle method is still Turing complete, and we show when it loses Turing completeness. This contributes to understanding the theoretical foundations of particle methods and provides insight into the powerfulness of computer simulations.