In this practical assignment, we were to develop our understanding of the Turing Machine abstraction by building a TM simulator, and also designing a number of Turing Machines for various tasks. Furthermore, we were tasked with analysing the complexity of our TM algorithms, either theoretically or experimentally (or both) . I designed and developed my TM simulator in Python, developed Turing Machines to solve the two problems detailed in the specification, and specified and solved two additional problems. All of my Turing Machine solutions to the specified problems pass the provided StacsCheck tests (REDACTED), and I performed additional tests on my solutions to the auxiliary problems. Each TM implementation has been analysed in terms of complexity, with the experimental results confirming the theoretical expectations.
Read my report here: Turing_Machines.pdf