Why two counters can simulate a stack?
Dear colleagues:
It is shown that Minsky Counter Machine can simulate a Turing machine , for two counters can simulate a stack (a half tape in Turing machine). If 1 pushed in the stack, then double the counter plus 1; if 0 is pushed then double the counter. When multipliers and reminders in many steps are mixed in one counter, how to discriminate which step of a pushing? Where I can find the introduction to Minsky Counter Machine in more detail than Wikipedia ?
I am sure the ideas below are very easy to write out as counter machines; I use C-like code for explanations.
Let C2 store zero when we start simulating any stack operation.
Below are few useful routines before push and pop.
MV(C1,C2): Move the counter's value to the other counter (say, C1 to C2):
{while(C1!=0){C1--;C2++;}}
MV2(C1,C2): Move and double:
{while(C1!=0){C1--;C2++;C2++}}
PUSH(b):
{if(b)C2++;
MV2(C1,C2); MV(C1,C2)
}
POP:
{MV(C1,C2);
label1:
if(C2==0) goto nextIf0;
C2--;
if(C2==0) goto nextIf1;
C2--; C1++; goto label1;
}
- Badges
- Science topic
- Similar topics
- Computer Communications (Networks)
- Simulators