Beweistheorie und Rekursionstheorie

In diesem von der DFG finanzierten Drittmittelprojekt sollen wechselseitige Beziehungen zwischen rekursionstheoretischen und beweistheoretischen Sachverhalten erforscht werden. Schwerpunkte liegen speziell auf Untersuchungen über das Wachstumsverhalten subrekursiver Hierarchien und Untersuchungen über Berechungskomplexitäten von Termersetzungssystemen.

Drittmittelgeber:

Deutsche Forschungsgemeinschaft

Beteiligte Wissenschaftler:

Dr. Arnold Beckmann, Dipl.-Math I. Lepper, Dipl.-Math. M. Möllerfeld, H.Doz. Dr. A. Weiermann (Heisenberg Stipendiat)

Veröffentlichungen:

Beckmann, A., W. Pohlers: Applications of cut-free infinitary derivations to generalized recursion theory, Annals of Pure and Applied Logic, 94 (1998), S. 159-187

Pohlers, W.: Subsystems of Set Theory and Second Order Arithmetic, in S. Buss (editor), Handbook of Proof Theory, North Holland (1998), S. 209-335

Pohlers, W.: Intuitionismus vs. Klassik, Ethik und Sozialwissenschaften, Westdeutscher Verlag Opladen, Heft 3 (1998), S. 447-446

Blankertz, B.: Beweistheoretische Techniken zur Bestimmung von Pi-0-2-Skolem Funktionen, Dissertation (1997)

Blankertz, B., A. Weiermann: A uniform approach for characterizing the provably total number-theoretic functions of KPM and (some of) its subsystems, Angenommen: Studia Logica.

Lepper, I.: Forcing mit markierten Bäumen, Diplomarbeit 1997.

Harmeling, S.: Eine beweistheoretische Anwendung der <k-Relation, Diplomarbeit 1998.

Weiermann, A.: Sometimes slow growing is fast growing, Annals of Pure 90 and Applied Logic (1997), S. 91-99.

Weiermann, A.: Bounding derivation lengths with functions from the slow growing hierarchy, Archive for Mathematical Logic 37 (1998), S. 427-441.

Beckmann, A., A. Weiermann: How to characterize the elementary recursive functions by Howard-Schütte-style methods, Angenommen: Archive for Mathematical Logic.

Weiermann, A.: Term rewriting theory for the hydra battle and the extended Grzegorczyk hierarchy, Angenommen: Journal of Symbolic Logic.

Weiermann, A.: What makes a (pointwise) subrecursive hierarchy slow growing? Angenommen: Proceedings of the Logic Colloquium 1997.

Weiermann, A.: Some interesting connections between the slow growing hierarchy and the Ackermann function, Angenommen: Journal of Symbolic Logic.

Beklemishev, L. D.: Parameter-free induction and provably total computable functions, 18 pages, Angenommen: Theoretical Computer Science

Beklemishev, L. D.: Another pathological well-ordering, 4 pages, Angenommen: Logic Colloquium'98 Proceedings, Springer-Verlag, Berlin.

Beklemishev, L. D.: Open least element principle and bounded query computation, 16 pages, Eingereicht: Computer Science Logic '99 Proceedings, LNCS series, Springer-Verlag.