Step 3: Four Counters Can Be Simulated By Two Counters.
As before, one of the counters is used as scratchpad. The other, real counter holds an integer whose prime factorization is 2a3b5c7d. The exponents a, b, c, and d can be thought of as four virtual counters that are being simulated. If the real counter is set to zero then incremented once, that is equivalent to setting all the virtual counters to zero. If the real counter is doubled, that is equivalent to incrementing a, and if it's halved, that's equivalent to decrementing a. By a similar procedure, it can be multiplied or divided by 3, which is equivalent to incrementing or decrementing b. Similarly, c and d can be incremented or decremented. To check if a virtual counter such as c is equal to zero, just divide the real counter by 5, see what the remainder is, then multiply by 5 and add back the remainder. That leaves the real counter unchanged. The remainder will have been nonzero if and only if c was zero.
As a result, an FSM with two counters can simulate four counters, which are in turn simulating two stacks, which are simulating a Turing machine. Therefore, an FSM plus two counters is at least as powerful as a Turing machine. A Turing machine can easily simulate an FSM with two counters, therefore the two machines have equivalent power.
Read more about this topic: Counter Machine, Two-counter Machines Are Turing Equivalent (with A Caveat)
Famous quotes containing the words step and/or simulated:
“A major misunderstanding of child rearing has been the idea that meeting a child’s needs is an end in itself, for the purpose of the child’s mental health. Mothers have not understood that this is but one step in social development, the goal of which is to help a child begin to consider others. As a result, they often have not considered their children but have instead allowed their children’s reality to take precedence, out of a fear of damaging them emotionally.”
—Elaine Heffner (20th century)
“Not too many years ago, a child’s experience was limited by how far he or she could ride a bicycle or by the physical boundaries that parents set. Today ... the real boundaries of a child’s life are set more by the number of available cable channels and videotapes, by the simulated reality of videogames, by the number of megabytes of memory in the home computer. Now kids can go anywhere, as long as they stay inside the electronic bubble.”
—Richard Louv (20th century)