Computation theory with atoms

Speaker(s)

Bartosz Klin

Affiliation

Uniwersytet Warszawski

Date

April 27, 2017, 3:30 p.m.

Room

room 5070

Seminar

PhD Open

---

First, a caveat: "atoms" here are mathematical rather than physical entities, so people hoping for some kind of nuclear computation devices will be disappointed.

"Computation with atoms" means computation over structures that are infinite, but exhibit a lot of symmetries that make them amenable to symbolic manipulation. Examples include automata over infinite alphabets that can only compare their letters for equality, pushdown automata, Turing machines subject to similar restrictions, etc. Traditional intuitions about computation models sometimes fail, for example automata or Turing machines do not determinize. However, many interesting problems remain decidable and tractable on infinite but highly symmetric domains.

In the course I will present:

- the basic mathematical theory of sets with atoms,

- notions of automata and Turing machines with atoms, with their (sometimes surprising) properties,

- programming languages for computing with atoms with example applications.

(see http://phdopen.mimuw.edu.pl/index.php?page=l17w1 for more details)

 

---