Machine Programs
This note explains what machine programs and models of computations are. A machine program describes a program for a machine as the name suggests. In this context a machine can be seen as a device that can be controlled using buttons and indicator lamps. A model of computation is an abstract description of such a machine. It specifies the machine's behavior, i.e. what happens when a certain button is pushed or under what circumstances is an indicator lamp active. Thus, a machine program must always be interpreted with respect to a model of computation.
The purpose of machine programs is to provide a simple and flexible formal language that can be quickly understood and enable those who are unfamiliar with programming languages to formalize algorithms. Since their control flow is not confined by a predefined set of control structures they can be constructed from traces in an intuitive manner, which facilitates the implementation of algorithms with complex control flows.
Models of Computation
As stated previously, a machine program can only be interpreted with respect to a model of computation. Therefore we have to familiarize ourselves with such models first. We will look at three examples of such models and then consider the general definition.
Gummy Bear Factory
Imagine you are in a factory that produces gummy bears. There are two big funnels labeled sugar and dye which contain pieces of sugar and food dye, respectively. Beneath these two funnels is a large container called mixer. To produce gummy bears sugar and dye have to be put into the mixer in the right ratio. In order to do this there is a small control panel with two buttons and two indicator lamps:
 Buttons
AddSugar
: releases one piece of sugar into the mixer provided the sugar funnel is not empty; if it is empty nothing happensAddDye
: releases one piece of dye into the mixer provided the dye funnel is not empty; if it is empty nothing happens Indicator lamps
SugarEmpty
: lamp is active if the sugar funnel is emptyDyeEmpty
: lamp is active if the dye funnel is empty
One gummy bear consists of 3 pieces of sugar and 2 pieces of dye. Every morning the funnels are refilled with sugar and dye. After the funnels have been filled it is guaranteed that
 the number of dye pieces is even and
 the number of sugar pieces is divisible by 3
How can the machine be operated such that the maximal amount of gummy bears can be produced every day?
Examples
 if there are 66 sugar pieces and 40 dye pieces in the funnels then 60 sugar pieces and 40 dye pieces should be released into the mixer (20 gummy bears)
 if there are 9 sugar pieces and 10 dye pieces in the funnels then 9 sugar pieces and 6 dye pieces should be released into the mixer (3 gummy bears)
Play as a game (open separately)
Solution
If theSugarEmpty
and the DyeEmpty
lamp are both inactive add 3 pieces of sugar and 2 pieces of dye. Repeat this until at least one of the lamps becomes active. Since the number of dye pieces is even and the number of sugar pieces divisible by 3 there is always enough material in the funnels for one additional gummy bear if both indicator lamps are inactive.
3Counter Machine
A 3counter machine has 3 registers of which each contains a nonnegative integer (≥ 0). For each register there is a button to increment the number in the register by 1 and one to decrement it by 1. If a register contains 0 and the decrement button for that register is pressed nothing happens. Also, there is an indicator lamp for each register which is active if the register contains 0.
 Buttons
R1+1
R2+1
R3+1
R11
R21
R31
 Indicator lamps
R1=0
R2=0
R3=0
Suppose your are in front of such a 3counter machine and its registers have been initialized with some values that are unknown to you. How to operate the machine such that the sum of the numbers in register 1 and 2 is contained in register 3 in the end? The numbers in register 1 and 2 can be modified in the process. Try to find a solution which does not require you to count.
Play as a game (open separately)
Solution
Decrement register 3 as long asR3=0
is inactive; this sets register 3 to 0. Then decrement register 1 by one and increment register 3 by one as long as R1=0
is inactive. This moves the number in register 1 to register 3.
Then decrement register 2 by one and increment register 3 by one as long as R2=0
is inactive. This adds the number in register 2 to the one in register 3.
Labyrinth
You are in a labyrinth which is represented as a square grid. A square is either a wall or walkable. You can turn left or right by 90° and you can move a step forward. Since the labyrinth is dark you can only see whether there is a wall directly in front of you or whether you have reached the exit.
 Actions
Move
: you move one step in the direction you face (unless there is a wall in front, then nothing happens)Left
: you turn 90° leftRight
: you turn 90° right Senses
Wall
: active if there is a wall in front of youExit
: active if you have reached the exit
How can you find the exit without knowing the layout of the labyrinth?
General Definition
A model of computation has two components called operations and predicates although we used different names in the examples:
predicates ≡ indicator lamps ≡ senses
It also has a third component called machine states, which were described implicitly in the examples. A machine state describes the complete internal state of the machine. For a 3counter machine a machine state must describe the 3 nonnegative integers in the 3 registers. For the gummy bear factory the machine state can be represented using 4 nonnegative integers: the number of pieces of sugar in the sugar funnel, the number of pieces of dye in the dye funnel and the numbers of pieces of sugar and dye in the mixer. In the case of the labyrinth example a machine state represents the layout of the maze along with the position and orientation of the player (one can think of the labyrinth as a game on a machine).
Formally, the machine states of a model of computation are a set S and an operation is a total function which maps from S to S and a predicate is a total function which maps from S to true (active) or false (inactive).
In our examples the models of computations were presented in conjunction with a particular task. In general, there can be different tasks for a model of computation. For example, instead of the sum on the 3counter machine one could ask for the maximum: operate the machine such that the maximum number over what is contained in register 1 and 2 is in register 3 at the end.
Models of computations are a very simple yet broadly applicable theoretical concept. For example, it is possible to encode Turing machines, finite state automata and pushdown automata or instruction set architectures (with certain limitations) as models of computation. The interactive presentation of such models also makes them suitable for teaching the basics of algorithmic thinking without even needing a programming language.
Remark: the term model of computation is used as an informal term in theoretical computer science and encompasses much more than what falls under the above definition. For example, neither boolean circuits nor lambda calculus can be expressed as model of computation in the above formal sense. The notion described here can only capture sequential and nondynamic models of computation.
Machine Programs
Now we are ready to define machine programs and give some examples. At the end of the page you can find a simple interpreter for kcounter machines.
Definition and Examples
When we execute an algorithm on a machine we push a sequence of buttons until the algorithm ends. To decide what button to push next (or whether to stop) we look at the indicator lamps. However, what button to push next does not solely depend on the indicator lamps but also some internal state that we keep track of in our mind. We call this a program state. For example, in the case of the gummy bear factory we had to remember how many pieces of sugar and dye still needed to be released into the mixer for every iteration.
A machine program consists of a set of program states and each program state is associated with an operation. In addition to that there is a special program state Start
which does not have an operation. As soon as a program state is reached, the corresponding operation is executed (no operation is executed in Start
). After the operation has been executed one has to decide with what program state to continue or whether the program execution should end. This decision process can be described using binary decision trees (BDT). Here is an example:
This BDT is read as follows. We start at the root node SugarEmpty
. Since it is a predicate we look whether it is true (meaning the indicator lamp is active). If the predicate is true then we follow the solid line (right child); if it is false then we follow the dashed line (left child). This BDT states that execution should end when the sugar or dye funnel are empty. Otherwise one should continue with the program state Sugar1
.
The above diagram shows a machine program that implements an algorithm for the problem in the gummy bear factory. It has the program states Sugar1
, Sugar2
, Sugar3
, Dye1
, Dye2
and the special program state Start
. The program states Start
and Dye2
have the same BDT. All other program states have a BDT which consists of a single node. For example, if one is in the program state Sugar1
then the next program state must be Sugar2
irregardless of the predicate values.
Example trace
Program state  Operation  Sugar  Dye  Predicate sequence 

Start 
12  4 
SugarEmpty ⇢
DyeEmpty ⇢
Sugar1


Sugar1 
AddSugar 
11  Sugar2


Sugar2 
AddSugar 
10  Sugar3


Sugar3 
AddSugar 
9  Dye1


Dye1 
AddDye 
3  Dye2


Dye2 
AddDye 
2 
SugarEmpty ⇢
DyeEmpty ⇢
Sugar1


Sugar1 
AddSugar 
8  Sugar2


Sugar2 
AddSugar 
7  Sugar3


Sugar3 
AddSugar 
6  Dye1


Dye1 
AddDye 
1  Dye2


Dye2 
AddDye 
0 
SugarEmpty ⇢
DyeEmpty →
End

Next, let us consider a slightly more sophisticated example. The following diagram shows a machine program for addition on the 3counter machine.
Example trace
Program state  Operation  R1  R2  R3  Predicate sequence 

Start 
1  3  2 
R3=0 ⇢
Clear


Clear 
R31 
1 
R3=0 ⇢
Clear


Clear 
R31 
0 
R3=0 → R1=0 ⇢
Move1


Move1 
R11 
0 
Move2


Move2 
R3+1 
1 
R1=0 → R2=0 ⇢
Add1


Add1 
R21 
2  Add2 

Add2 
R3+1 
2 
R2=0 ⇢ Add1


Add1 
R21 
1  Add2 

Add2 
R3+1 
3 
R2=0 ⇢ Add1


Add1 
R21 
0  Add2 

Add2 
R3+1 
4 
R2=0 → End

In the context of our labyrinth example it is possible to implement Pledge's algorithm as machine program to find a way out of the maze. The idea is to remember the number of turns made modulo 4 using program states.
Subprograms
The ability to combine simpler programs in order to build more complex ones is an essential aspect of programming. The usual means of abstraction in programming languages are functions. Due to the limited nature of machine programs complex abstraction mechanism are not possible without going beyond what simple machine programs can express. The notion of subprograms, however, naturally fits into the syntax and semantics of machine programs.
Suppose we have a machine program P for a model of computation M. Oberseve that P takes a machine state as input and returns one as ouput (the result of the computation). In that regard it qualifies as an operation of M. Therefore if we build another program P' for M we can use P as if it were an operation of M. This means a program state of P' can be associated with P as operation. However, there should not be any cycles in the subprogram call graph, e.g. if P' calls P then P cannot call P'.
This does not increase the expressiveness of machine programs since the calls to the other programs can be compiled into the new program yielding a semantically equivalent one without subprogram calls.
Interpreter
Below is an interpreter for kcounter machines which has the above machine program for addition as default example. The BDTs are encoded as indented trees using tabulator characters. The first child in the string representation corresponds to the left child, which is taken if the predicate of parent node is false.