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

Research Seminar of the Logic Group: Approximate reasoning in data mining

---

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.

---