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

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.

---