Automata Theory

I've decided to include a section on automata theory, an interest I developed in the last module connected to the theory of computability.

Finite State Machines

Examples

Arcile, J. & Andre, E. (2022) 'Timed automata as a formalism for expressing security: A survey on theory and practise'. ACM Computing Surveys 55(6): 1-36. - Arcile and Andre survey security-centred works making use of timed automata, which are finite automata with clocks. They note the biggest applications are in attack tree translation, and RBAC modelling.
Larson, E. & Kirk, A. (2016) 'Generating Evil Test Strings for Regular Expressions'. IEEE International Conference on Software Testing, Verification and Validation (ICST). Chicago, USA, 2016. New York: IEEE. 309-319. - Larson and Kirk present EGRET, a nondeterministic finite automata that they use for generating a moderate amount of test cases that checks the suitability of a regular expression pattern as a filter.

Turing Machines

Glossary

Church-Turing Thesis

"Every (human) computation can be done by a Turing Machine" ( Copeland, 2017 )

Reaction

The Church-Turing thesis is a profound one, as it's essentially saying there is a class of computations that a Turing machine can perform, and this class is equivalent to the class of all known human calculable functions, making a turing machine a model of the human limits when it comes to calculating. Copeland (2017) does well to discuss surrounding philosophy, including misconceptions and influence.

Below I've pulled out notable concepts related to Turing machines for future reference, including adaptations of turing machines that disprove some family theses of the church-turing thesis.

Maximality Thesis

"All functions that can be generated by machines (working in accordance with a finite program of instructions) are computable by effective methods" ( Copeland, 2017 )

Extended Turing Machine (ETM)

"An ETM is exactly like a standard Turing machine except that, whereas a standard Turing machine stores only a single discrete symbol on each (non-blank) square of its tape (e.g., ‘0’ or ‘1’), a single square of an ETM’s tape can store any desired real number" ( Copeland, 2017 )

Accelerated Turing Machine (ATM)

"Accelerating Turing machines (ATMs) are exactly like standard Turing machines except that their speed of operation accelerates as the computation proceeds" ( Copeland, 2017 )

Simulation Thesis

"Any process that can be given a mathematical description (or that is scientifically describable or scientifically explicable) can be simulated by a Turing machine." ( Copeland, 2017 )

Readings

Copeland, B. (2017) The Church-Turing Thesis. Available from: here. - Copeland provides an encyclopedic entry on the Church-Turing thesis, outlining versions of it and misconceptions. Critical attention is also given to the maximality and simulation theses.

Reflection

Automata are a type of model with a formal underpinning, which obviously makes them useful for modelling and formal analysis. I find them deeply interesting, as someone with a Bachelors degree centred on mathematics and psychology, simply for them being artifacts of human thought that's able to describe organisation in the universe around us. I was happy to learn of applications such as in the production of evil regex, and the development of security protocols as once again, it meant I had a domain-specific excuse to learn more about them. I plan to eventually create a catalogue of models for an encylopedic, passion project. Until then, I'll continue to look for oppurtunities to devote a bit of time to more theoretical computer science, out of curiosity. Professionally, finite automata are another tool I can incorporate into my work, if requested.