TGI

• Heimatseite
• Ankündigungen
• Mitarbeiterinnen und Mitarbeiter
• Studentinnen und Studenten

Lehre

• Lehre
• Abschlussarbeiten

Forschung

• Forschung
• Publikationen

Misc

• Service
• Tools
• Petri Nets World
  

Projekt : Kleine Universelle Turing-Maschinen

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

Laufzeit: seit 1980

Schlagworte: Universelle Turing-Maschinen

Ziele:

Es wird die Grenze zwischen Entscheidbarkeit und Unentscheidbarkeit untersucht. Auf der einen Seite befinden sich kleine universelle Turing-Maschinen. Alle bisher kleinsten wurden von Yu. Rogozhin konstruiert. Jedoch haben sie alle eine große (exponentielle) Komplexität bezüglich Darstellung und Simulation spezieller Maschinen. Diese Beziehung zwischen Größe und Komplexität wird näher untersucht. Ferner werden universelle Maschinen für Turingmaschinen mit beschränkter Zeit- und Band-Komplexität untersucht und eine Anzahl solcher konstuiert. Ferner wurde eine neue kleine universelle Turing-Maschine konstruiert.

Für Turing-Maschinen mit einer Teilklasse der primitiv rekursiven Funktionen als Platzkomplexität wurde eine Darstellung der primitiv rekursiven Funktionen und eine universelle Turing-Maschine mit derselben Platzkomplexität für die Simulation entwickelt. Eine analoge Universelle Turing-Maschine für entsprechende Zeitkomplexität benötigt polynomiell mehr Zeit.

Ferner wurde gezeigt, dass keine universellen endlichen Automaten und endlichen a-Transducer existieren. Außerdem wurden kleine universelle zyklische Post-Maschinen untersucht und ein Anzahl solcher konstruiert. Ferner wurde eine neue kleine universelle Turing-Maschine konstruiert. Dazu wurde ein INTAS-Projekt für 18 Monate bewilligt, beginnend mit Dezember 1998 und verlängert bis Ende 2000. Es wurde wie für Turing-Maschinen für zyklische Post-Maschinen die Grenze zwischen Entscheidbarkeit und Universalität untersucht und weiter eingeschränkt.

Publikationen:

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)