Equilibrium and Termination

Vincent Danos
(University of Edinburgh)
Nicolas Oury
(University of Edinburgh)

We present a reduction of the termination problem for a Turing machine (in the simplified form of the Post correspondence problem) to the problem of determining whether a continuous-time Markov chain presented as a set of Kappa graph-rewriting rules has an equilibrium. It follows that the problem of whether a computable CTMC is dissipative (ie does not have an equilibrium) is undecidable.

In S. Barry Cooper, Prakash Panangaden and Elham Kashefi: Proceedings Sixth Workshop on Developments in Computational Models: Causality, Computation, and Physics (DCM 2010), Edinburgh, Scotland, 9-10th July 2010, Electronic Proceedings in Theoretical Computer Science 26, pp. 75–84.
Published: 9th June 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.26.7 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org