### Abstract:

This thesis documents a method of proving that Turing machines
work for every case, if the construction of the Turing machine is
known. Mathematical Induction is used to construct the proof that the
Turing machine for binary addition will work in every well-formed case
of the input that it receives. This proof can serve as a general model
for proving that Turing machines work if their constructions are known
and provided they do work.
The modification of a Turing machine for binary addition (TBA)
in alphabet A: {S, 1, 0, +, a, b, c,} was investigated. The alphabet
was transformed and the machine modified so that it could perform the
same operations in a new alphabet Z: {I,S}. Each element of alphabet
A is represented by a three member string of occurrences of elements
of alphabet Z. A cycle to recognize, write and move is needed for this modification of TBA. An increased number of subsidiary states is
required. For each cycle within a quintuple for alphabet A, the number
of subsidiary states for TBA to function in alphabet Z equals to
the square of the number of occurrences of elements in Z that represent
an element of alphabet A. It was shown that the modified TBA
could perform the same operation as the original TBA.
Complete configurations for each state of a Turing machine can
be reconstructed from a number, a labelled number related to a complete
configuration of a Turing machine operating in the alphabet Z on a
tape with a marked left end. This construction illustrates the claim
of Marvin Minsky that the Post-tag algorithm can simulate a Turing
machine.