REVERSIBILITY OF 2D CELLULAR AUTOMATA IS UNDECIDABLE

被引：122

作者：

KARI, J

机构：

[1] Mathematics Department, University of Turku

来源：

PHYSICA D | 1990年 / 45卷 / 1-3期

关键词：

D O I：

10.1016/0167-2789(90)90195-U

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The problem whether a given two- or higher-dimensional cellular automaton is reversible is shown to be algorithmically undecidable. A cellular automaton is called reversible if it has an inverse automaton, that is a cellular automaton that makes the system retrace its steps backwards in time. The same problem is known to be decidable for one-dimensional automata. © 1990.

引用

页码：379 / 385

页数：7

共 11 条

[1]

Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8

[2]

Berger R., 1966, MEM AM MATH SOC, V66

[3]

Culik K. II, 1987, Complex Systems, V1, P1035

[4]

KARI J, 1989, THESIS U TURKU FINLA

[5]

KARI J, UNPUB COMPUTER SYSTE

[6]

Moore E. F., 1962, P S APPL MATH, V14, P17, DOI DOI 10.1090/PSAPM/014/9961

[7]

Myhill J., 1963, P AM MATH SOC, V14, P685, DOI DOI 10.2307/2034301.

[8]

Richardson D., 1972, Journal of Computer and System Sciences, V6, P373, DOI 10.1016/S0022-0000(72)80009-6

[9] UNDECIDABILITY AND NONPERIODICITY FOR TILINGS OF PLANE [J].

ROBINSON, RM .

INVENTIONES MATHEMATICAE, 1971, 12 (03) :177-&

[10]

Toffoli T., 1987, CELLULAR AUTOMATA MA, DOI DOI 10.7551/MITPRESS/1763.001.0001

← 1 2 →