Nie jesteś zalogowany | Zaloguj się

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.