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:
- 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)
- Manfred Kudlek
Small Deterministic Turing Machines
(TCS 168 (2), pp. 241-255, 1996)
- 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)
- 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)
- Manfred Kudlek, Yurii Rogozhin
Small Universal Circular Post Machines
(Computer Science Journal of Moldova, Vol. 9, Nr. 1, pp. 34-52, 2001)
- Manfred Kudlek, Yurii Rogozhin
A New Small Universal Turing Machine
(Preproceedings of DLT'2001, ed. W. Kuich, pp. 323-332, TU Wien, 2001)
- Manfred Kudlek, Yurii Rogozhin
New Small Universal Circular Post Machines
(Proceedings of FCT'2001, ed. R. Freivalds, LNCS 2138, pp. 217-226, 2001)
- 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)
- Manfred Kudlek, Yurii Rogozhin
Small Universal Turing and Circular Post Machines
(PU.M.A., vol. 13, no. 1-2, pp. 197-210, 2003)
- Artiom Alhazov, Manfred Kudlek, Yurii Rogozhin
Nine Universal Circular Post Machines
(Computer Science Journal of Moldova, vol. 11, pp. 247-262, 2002)
- Manfred Kudlek
Some Considerations on Universality
(Proc. of CSP08, eds. N. Murphy, T. Neary, A. Seda, D. Woods, pp. 149-155, 2008)
- Manfred Kudlek
Some Considerations on Universality
(EPTCS 1, pp. 118-122, 2009)
Letzte Änderung: 17:40 19.05.2011
Impressum