Real-valued affine automata compute beyond Turing machines

2022/12/22 by Abuzer Yakaryılmaz, Yakaryılmaz, Abuzer
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #Computability, Logic, AI Algorithms #DNA and Biological Computing

paper · pdf · doi:10.48550/arxiv.2212.11834

Abstract

We show that bounded-error affine finite automata recognize uncountably many (and so some non-Turing recognizable) languages when using real-valued transitions.

Related

• Improved constructions for succinct affine automata
• Computational Limitations of Affine Automata
• Two-way affine automata can verify every language
• Affine automata verifiers
• Languages recognized with unbounded error by quantum finite automata