  This paper considers the computational power of constant size, dynamic
Bayesian networks. Although discrete dynamic Bayesian networks are no more
powerful than hidden Markov models, dynamic Bayesian networks with continuous
random variables and discrete children of continuous parents are capable of
performing Turing-complete computation. With modified versions of existing
algorithms for belief propagation, such a simulation can be carried out in real
time. This result suggests that dynamic Bayesian networks may be more powerful
than previously considered. Relationships to causal models and recurrent neural
networks are also discussed.
