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. A trace is the sequence of steps caused by the execution of an algorithm (see below for examples; ex. 1 and ex. 2).

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 happens
• AddDye: 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 empty
• DyeEmpty: 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?

3-Counter Machine

A 3-counter machine has 3 registers of which each contains a non-negative 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
• R1-1
• R2-1
• R3-1
• Indicator lamps
• R1=0
• R2=0
• R3=0

Suppose your are in front of such a 3-counter 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.

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° left
• Right: you turn 90° right
• Senses
• Wall: active if there is a wall in front of you
• Exit: 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:

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 3-counter machine a machine state must describe the 3 non-negative integers in the 3 registers. For the gummy bear factory the machine state can be represented using 4 non-negative 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 3-counter 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 non-dynamic 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 k-counter 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.

Next, let us consider a slightly more sophisticated example. The following diagram shows a machine program for addition on the 3-counter machine.

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 k-counter 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.