Real-Valued Affine Automata Compute Beyond Turing Machines
Yakaryılmaz, Abuzer · Journal of automata, languages and combinatorics · 2025
We show that bounded-error affine finite automata (AfAs) recognize uncountably many (and so some non-Turing recognizable) languages when using real-valued transitions. We obtain similar results for unary languages when accessing to counter-type memories.