Linearity (MATH 526) Final Project

Alan Turing's paper "On Computable Numbers" \cite{Church_1937} provides a framework for Computing Machines, which are physical symbol manipulation machines, which can, in theory, compute a specific computable sequence if programmed to do so. Each of these machines, subsequently named "Turing Machines" is provided with a read-write head, a programmable structure, and input tape of symbols, which the machine can move left or right. From this concept, Turing asserts "It is possible to create a single computing machine which can be used to compute any computable sequence." referring to what he calls a Universal Computing Machine. The purpose of my project is to explore this theory from first principles and create a testing framework to accurately display the computational ability of Turing Machines. I broke up the learning into two sections: computational theory and programming language/compiler design.