## Counter Programs

Turing machines are not the only simple mathematical model of what
can be computed. Another model, more closely resembling Pascal
programs, is based on counter programs.

Counter programs manipulate nonnegative integers stored in variables.
The language has three operations:

X := 0
X := Y + 1
X := Y - 1

We assume that if X = 0 then X-1 is also 0.
The only control structures are sequencing and a conditional goto:

if X = 0 goto L

Execution terminates if the program tries to goto a nonexistent
label or executes the last statement in the program.

### Example Counter Program

Compute Z := X * Y using a counter program.

U := 0
Z := 0
A:if X = 0 goto C /* Goto C (halt) leaving Z=0 if X=0 */
X := X - 1 /* Add Y to Z X times */
V := Y + 1 /* Simulate V := Y */
V := V - 1
B:if V = 0 goto A /* Loop to add Y to Z, in steps of 1 */
V := V - 1
Z := Z + 1
if U = 0 goto B /* Simulate unconditional goto */

Interesting fact:
Counter programs are exactly as powerful as Turing machines! Any
computation we can do with one, we can simulate using the other.

Think about how to do that. You could lay the variables in a counter
program out on the TM tape. Each instruction in the counter program
would correspond to a state in TM.

Interesting question:
So how powerful are Turing machines/counter programs? What can they
compute (ie, what problems can they solve) and what can't they compute?