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