\documentstyle{article}[12pt,a4]

\title{Computer Design Supervision 3}
\author{Matthew Johnson\\Trinity Hall\\mjj29@cam.ac.uk}

\begin{document}
\maketitle

\section{y2000p3q9}

The halting problem is the question of whether it it possible to create a machine, or an algorithm, which will {\em always} decide whether any program will terminate on any given input. It has been established by computation theroy that it is not possible.


The configuration of a 2 register machine at any point consist of the values of the 2 registers, the program it is running, and the current label we are executing at.


{\em difficult......}


\section{y1999p3q9}

When using a register machine, you give it a list of commands. These commands consist of an operation, a register, and one or 2 labels. Possible operations are increment register, and jump to label, or \{register == 0, jump to label 1 | register > 0, decrement register and jump to label \}. This will continue until a special HALT instruction is reached, and the result can be read from the registers.

The current configuration is a function of the program, the current values in the registers and the contents of all the registers.

The given register machine set {\em a} to 0, then exits if {\em s} is 0, otherwise copy {\em s} into{\em z}. It then prcoceeds to repeatedly divide {\em z} by 2 into {\em s}, exiting if {\em z} is odd, otherwise incrementing a, and copying {\em z} into {\em s} again. This terminates with the number of times 2 divides into {\em z} in {\em a}.


{\em will look the rest up}
\end{document}
