Universality of automata below Turing Machines

Prelegent(ci)

prof. Manfred Kudlek

Afiliacja

University of Hamburg

Termin

4 października 2011 14:15

Pokój

p. 5820

Seminarium

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.

---