NO PERFECT 2-STATE CELLULAR-AUTOMATA FOR DENSITY CLASSIFICATION EXISTS

被引：148

作者：

LAND, M

BELEW, RK

机构：

[1] Department of Computer Science and Engineering, University of California, San Diego

来源：

PHYSICAL REVIEW LETTERS | 1995年 / 74卷 / 25期

关键词：

D O I：

10.1103/PhysRevLett.74.5148

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

Recently there have been many attempts to evolve one-dimensional two-state cellular automata which classify binary strings according to their densities of 1's and 0's. The current best-known approaches involve particle-based systems of information transfer. A proof is given that there does not exist a two-state cellular automata which performs the task perfectly. This is true even in multiple dimensions. © 1995 The American Physical Society.

引用

页码：5148 / 5150

页数：3