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)
“The work of art assumes the existence of the perfect spectator, and is indifferent to the fact that no such person exists.”
—E.M. (Edward Morgan)