Impossibility of A Perfect Classifier
In 1994, Land and Belew showed that no two-state rule with radius r and density ρ correctly solves the voting problem on all starting configurations when the number of cells is sufficiently large (larger than about 4r/ρ).
Their argument shows that because the system is deterministic, every cell surrounded entirely by zeros or ones must then become a zero. Likewise, any perfect rule can never make the ratio of ones go above if it was below (or vice-versa). They then show that any assumed perfect rule will either cause an isolated one that pushed the ratio over to be cancelled out or, if the ratio of ones is less than, will cause an isolated one to introduce spurious ones into a block of zeros causing the ratio of ones to be become greater than .
Read more about this topic: Majority Problem (cellular Automaton)
Famous quotes containing the words impossibility of a, impossibility of and/or perfect:
“It is in this impossibility of attaining to a synthesis of the inner life and the outward that the inferiority of the biographer to the novelist lies. The biographer quite clearly sees Peel, say, seated on his bench while his opponents overwhelm him with perhaps undeserved censure. He sees him motionless, miserable, his head bent on his breast. He asks himself: “What is he thinking?” and he knows nothing.”
—Andre Maurois (1885–1967)
“It is in this impossibility of attaining to a synthesis of the inner life and the outward that the inferiority of the biographer to the novelist lies. The biographer quite clearly sees Peel, say, seated on his bench while his opponents overwhelm him with perhaps undeserved censure. He sees him motionless, miserable, his head bent on his breast. He asks himself: “What is he thinking?” and he knows nothing.”
—Andre Maurois (1885–1967)
“In many ways, life becomes simpler [for young adults]. . . . We are expected to solve only a finite number of problems within a limited range of possible solutions. . . . It’s a mental vacation compared with figuring out who we are, what we believe, what we’re going to do with our talents, how we’re going to solve the social problems of the globe . . .and what the perfect way to raise our children will be.”
—Roger Gould (20th century)