Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfuß

Proiect: Maşini Turing Universale Mici

Diese Seite ist auch in Deutsch verfügbar. This page is also available in English. Cette page existe aussi en Français. Versión Español.


Prof. Dr. Kudlek,
Prof. Dr. Maurice Margenstern (Metz, Paris)
Prof. Dr. Pál Dömösi (Debrecen)
Prof. Dr. Yuri Rogozhin (Chisinau)
Ludmila Pavlockaya (Moskau)

Durată: Lansat în 1980

Cuvinte cheie: Maşini Turing Universale

Obiective:

Cercetarea graniţei dintre decidabilitate şi nedecidabilitate. Pe de o parte se găsesc maşinile Turing universale mici. Cele mai mici până acum au fost construite de către Yu. Rogozhin. Toate acestea au complexitate exponenţială în ceea ce priveşte reprezentarea şi simularea maşinilor speciale. Cercetarea acestei relaţii între mărime şi complexitate.

Cercetarea maşinilor universale cu complexitate finită în spaţiu şi timp. Pentru automatele finite nu există maşini universale de acelaşi tip. Maşini Post universale circulare sunt de asemenea luate în considerare şi construite.

Publicaţii:

  1. Volker Diekert, Manfred Kudlek
    Small Deterministic Turing Machines
    (Papers on Automata and Languages, Department of Mathematics, Karl Marx University of Economics, Budapest, 1988-4, pp. 77-87, 1989)
  2. Manfred Kudlek
    Small Deterministic Turing Machines
    (TCS 168 (2), pp. 241-255, 1996)
  3. Manfred Kudlek, Maurice Margenstern
    Universal Turing Machines with Complexity Constraints
    (Proceedings of the International Conference Automata and Formal Languages VIII, Publ. Math. Debrecen 53, pp. 895-904, 1999)
  4. Manfred Kudlek
    On Universal Finite Automata and a-Transducers
    (In: Grammars and Automata for String Processing: from Mathematics and Computer Science to Biology and back . Eds. C. Martín Vide, V. Mitrana, Topics in Computer Mathematics , pp. 163-170, Taylor and Francis, London, 2003)
  5. Manfred Kudlek, Yurii Rogozhin
    Small Universal Circular Post Machines
    (Computer Science Journal of Moldova, Vol. 9, Nr. 1, pp. 34-52, 2001)
  6. Manfred Kudlek, Yurii Rogozhin
    A New Small Universal Turing Machine
    (Preproceedings of DLT'2001, ed. W. Kuich, pp. 323-332, TU Wien, 2001)
  7. Manfred Kudlek, Yurii Rogozhin
    New Small Universal Circular Post Machines
    (Proceedings of FCT'2001, ed. R. Freivalds, LNCS 2138, pp. 217-226, 2001)
  8. Manfred Kudlek, Yurii Rogozhin
    A Universal Turing Machine with 3 States and 9 Symbols
    (Proceedings of DLT'2001, eds. W. Kuich, G. Rozenberg, A. Salomaa, LNCS 2295, pp. 311-318, 2002)
  9. Manfred Kudlek, Yurii Rogozhin
    Small Universal Turing and Circular Post Machines
    (PU.M.A., vol. 13, no. 1-2, pp. 197-210, 2003)
  10. Artiom Alhazov, Manfred Kudlek, Yurii Rogozhin
    Nine Universal Circular Post Machines
    (Computer Science Journal of Moldova, vol. 11, pp. 247-262, 2002)
  11. Manfred Kudlek
    Some Considerations on Universality
    (Proc. of CSP08, eds. N. Murphy, T. Neary, A. Seda, D. Woods, pp. 149-155, 2008)
  12. Manfred Kudlek
    Some Considerations on Universality
    (EPTCS 1, pp. 118-122, 2009)

Ultima actualizare: 17:40 19-05-2011
Impressum