The Implicit Computational Complexity Flavor of Automata
Mark Holcomb · Arsenal Augusta University’s Undergraduate Research Journal · 2021
Automata are foundational models of computation, whose powers and capacities can be described formally using complexity theory. These automata range broadly in feature-set, from having multiple heads to read input from to the presence of a stack for memory. Adding more features can increase the set of problems an automata can solve; however, how far can said features be reduced while maintaining the ability to solve the same category of problems? The goal is to limit an automata's features and show that it can solve problems that aren't solvable with another class of automata. Then it would be possible to either define a more efficient solution now or present a feature-rich automata to programmers and restrict features afterwards, increasing efficiency. There has not been a uniform approach to formally defining the lesser studied multi-headed automata and their complexity classes by other researchers in the past. To tackle this project, I will be using classical proving methodologies, along with the use of a proof verification system called coq to prove the capabilities of these rarely discussed automata. This will give the community access to a single resource for the certified results relative to the power and limitations of these automata.