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 - 1We 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 LExecution terminates if the program tries to goto a nonexistent label or executes the last statement in the 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?