Universality of automata below Turing Machines

Speaker(s)

prof. Manfred Kudlek

Affiliation

University of Hamburg

Date

Oct. 4, 2011, 2:15 p.m.

Room

room 5820

Seminar

Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

---

In the talk it is shown that there exist universal machines of the same kind for any primitive recursive space complexity function, and that there don't exist universal finite automata. The existence of universal pushdown automata is discussed too.

---