Turing Machines with Atoms and Constraint Satisfaction Problems

We study deterministic computability over sets with atoms. We characterize those alphabets for which Turing machines with atoms determinize. To this end, the determinization problem is expressed as a Constraint Satisfaction Problem, and a characterization is obtained from deep results in CSP theory. This is joint work with Bartek Klin, Sławomir Lasota and Szymon Toruńczyk.

Authors

• Joanna Ochremiak

Keywords

No keywords are indexed for this paper.