Exact Solution With Alternative Termination Conditions
As observed by Capcarrere, Sipper, and Tomassini, the majority problem may be solved perfectly if one relaxes the definition by which the automaton is said to have recognized the majority. In particular, for the Rule 184 automaton, when run on a finite universe with cyclic boundary conditions, each cell will infinitely often remain in the majority state for two consecutive steps while only finitely many times being in the minority state for two consecutive steps.
Alternatively, a hybrid automaton that runs Rule 184 for a number of steps linear in the size of the array, and then switches to the majority rule (Rule 232), that sets each cell to the majority of itself and its neighbors, solves the majority problem with the standard recognition criterion of either all zeros or all ones in the final state. However, this machine is not itself a cellular automaton.
Read more about this topic: Majority Problem (cellular Automaton)
Famous quotes containing the words exact, solution, alternative, termination and/or conditions:
“Since we are assured that the all-wise Creator has observed the most exact proportions of number, weight and measure in the make of all things, the most likely way therefore to get any insight into the nature of those parts of the Creation which come within our observation must in all reason be to number, weigh and measure.”
—Stephen Hales (1677–1761)
“Coming out, all the way out, is offered more and more as the political solution to our oppression. The argument goes that, if people could see just how many of us there are, some in very important places, the negative stereotype would vanish overnight. ...It is far more realistic to suppose that, if the tenth of the population that is gay became visible tomorrow, the panic of the majority of people would inspire repressive legislation of a sort that would shock even the pessimists among us.”
—Jane Rule (b. 1931)
“It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
—Hannah Arendt (1906–1975)
“We hoped for a happy termination of this terrible war long before this; but God knows best, and has ruled otherwise.”
—Abraham Lincoln (1809–1865)
“There is no society known where a more or less developed criminality is not found under different forms. No people exists whose morality is not daily infringed upon. We must therefore call crime necessary and declare that it cannot be non-existent, that the fundamental conditions of social organization, as they are understood, logically imply it.”
—Emile Durkheim (1858–1917)