Intractable problems in reversible cellular automata
Copyright policy )Intractable problems in reversible cellular automata
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.
- Isfahan University of Technology Iran (Islamic Republic of)
Cellular automata (computational aspects), reversible cellular automaton, Analysis of algorithms and problem complexity, distribution of gas molecules, Models of computation (Turing machines, etc.), Compressible fluids and gas dynamics, PSPACE-complete, billiard ball
Cellular automata (computational aspects), reversible cellular automaton, Analysis of algorithms and problem complexity, distribution of gas molecules, Models of computation (Turing machines, etc.), Compressible fluids and gas dynamics, PSPACE-complete, billiard ball
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!