Intractable problems in reversible cellular automata (Q1104752): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:59, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Intractable problems in reversible cellular automata |
scientific article |
Statements
Intractable problems in reversible cellular automata (English)
0 references
1988
0 references
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.
0 references
billiard ball
0 references
reversible cellular automaton
0 references
distribution of gas molecules
0 references
PSPACE-complete
0 references