Research Summary: Derived from discrete math, Theory of Computation is the back bone and forefront of Computer Science. According to Wikipedia, “the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.” This field of study tries to answer many critical questions to a wide variety of computer science implications including solving problems efficiently, determine if a problem is solvable by a Turing machine, and also how much memory would be required for a certain computation task. Amongst many great minds, Alan Turing, an early British computer scientist was one of the important man in the history of Theory of Computation. He established the standards for a machine that computation theory would study on – Turing Machine. A computer is called Turing-complete if it can solve any problem that a Turing Machine can. So it all comes down to what is a Turing Machine and what problems can it solve. Luckily, I studied the Turing Machine in a Spring Camp at MIT and wrote a few programs for this theoretical computer. From a technical view, a Turing Machine is a 7-tuple abstract machine. From my understanding, it has a head that can read and write, the ability to store states and turn left or right based on states, and an infinite tape. Modern day CPUs have all that a Turing Machine can perform: a memory to store, ability of conditional jump, and the ability to read and write to disk. The Turing Machine basically drafts out the essential components of a Turing-complete computer. There are three branches to the computation theory: automata theory, computability theory, and computational complexity theory. Each one of them is linked to the ultimate question, “What are the fundamental capabilities and limitations of computers?” I am particularly interested in complexity theory since it is the most practical branch of computation theory. The big O notation is essential to how we understand the efficiency of a program of how to write programs that run in reasonable time.

Link to Websites: https://en.wikipedia.org/wiki/Theory_of_computation http://videolectures.net/turing100_rabin_turing_church_goedel/ https://www.geeksforgeeks.org/toc-finite-automata-introduction/

Questions: 1. What as some challenges in computation theory? 2. How is P vs NP important to our daily lives? 3. Which courses about computation theory at CMUQ are offered?