- 2
`2021-01-06 20:39` -
It's been a while since I last studied automata theory, but shouldn't a simple finite-state automata suffice for tic-tac-toe? In the description, they reference a paper[0] that claims to actually prove that it is Turing complete, but all they implement is some logic gates, which are even weaker than a finite-state automata!

[0] https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-carlini.pdf

- 9