Execution

An algorithm is a recipe or a template that tells us how to compute the answer on an arbitrary input. When an algorithm is executed on specific inputs, we obtain an execution trace that completely describes the events that occurred in the machine. An execution trace is a list of pairs \((I, M)\), where \(I\) is some instruction in the algorithm and \(M\) is the contents of the storage just before \(I\) is performed. We use U to denote the contents of a word when the contents of the word is undefined. For the absolute value program, given the inputs \(2\) and \(3\), here is the execution trace:

jmpif [0] < [1], 3  <2, 3, U>
sub   [2], [1], [0] <2, 3, U>
end                 <2, 3, 1>

and here is the execution trace when the inputs are \(3\) and \(2\):

jmpif [0] < [1], 3  <3, 2, U>
sub   [2], [0], [1] <3, 2, U>
end                 <3, 2, 1>

Notice that in both cases, the actual instructions that were performed are different. An algorithm is correct when the execution trace yielded by the algorithm on any input leads to the correct output for that input.

Exercise #

1. Write a RAM program that takes three numbers as input on words 0, 1, and 2 and produces the maximum of three numbers as output in word 3. How many execution traces with distinct instruction sequences exist for your program?
2. Write a RAM program where the execution trace is an infinite sequence.