Intractable problems in reversible cellular automata
type: Item
instance of: scholarly article
title: Intractable problems in reversible cellular automata
zbMATH Open document ID: 0647.68055
DOI: 10.1007/BF00669293
author: Farrokh Vatan
published in: International Journal of Theoretical Physics
publication date: 1988-01-01T00:00:00Z
review text: The billiard ball model, a classical mechanical system in which all parameters are real variables, can perform all digital computations. An eight-state, 11-neighbor reversible cellular automaton (an entirely discrete system in which all parameters are integer variables) can simulate this model. One of the natural problems for this system is to determine the shape of a container so that the initial specific distribution of gas molecules eventually leads to a predetermined distribution. This problem is PSPACE-complete. Related intractable and decidable problems are discussed as well.
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 76N99
zbMATH DE Number: 4057014
zbMATH Keywords: billiard ball
zbMATH Keywords: reversible cellular automaton
zbMATH Keywords: distribution of gas molecules
zbMATH Keywords: PSPACE-complete
MaRDI profile type: Publication
cites work: Logical Reversibility of Computation
cites work: Q3944542
cites work: On reversibility in cellular automata
cites work: Conservative logic
cites work: Q3862379
cites work: Irreversibility and Heat Generation in the Computing Process
cites work: Q3677179
cites work: A Universal Four-State Cellular Computer
cites work: Tesselations with local transformations
cites work: Computation and construction universality of reversible cellular automata
cites work: Q3886867
description: scientific article; zbMATH DE number 4057014