Detailansicht
Introduction to recursion theory and computational complexity
Padraig Paul Sweeney
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Lehramt Sek (AB) Unterrichtsfach Mathematik Unterrichtsfach Psychologie und Philosophie
Betreuer*in
Vera Fischer
DOI
10.25365/thesis.76446
URN
urn:nbn:at:at-ubw:1-13119.03610.110160-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit untersucht anhand von Berechenbarkeitstheorie und Komplexitätstheorie zwei verschiedene Limitationen von Berechnungen. Einerseits geht es um theoretische Limitationen, die aus dem Halteproblem resultieren: es existieren wohldefinierte Funkti-onen, die nicht berechenbar sind. Der erste Teil der Arbeit bietet einen Überblick der Probleme der Berechenbarkeitstheorie und unter anderem einen Beweis der Äquiva-lenz von zwei der bekanntesten Arten Berechenbarkeit mathematisch in rigoroser Weise zu behandeln: Registermaschinen und allgemein partiell-rekursiven Funktionen. Andrerseits werden auch praktische Limitationen behandelt, die aus der Komplexität des Problems bzw. des Algorithmus zur Lösung des Problems resultieren. Der zweite Teil der Arbeit behandelt sowohl deterministische als auch nichtdeterministische Turing-maschinen und insbesondere deren Zusammenhang mit der Komplexitätstheorie. Im Zuge dessen wird auch das „P=NP“-Problem vorgestellt.
Abstract
(Englisch)
This thesis investigates two different limitations of computation based on computability theory and computational complexity theory. On the one hand the theoretical boundary of computability, which results from the halting problem is described: as it turns out there are well defined functions, that are not computable. The first part of the thesis pro-vides an overview of the main problems in recursion theory and a proof of the equiva-lence of two of the most famous approaches to computability namely the class of regis-termachine-computable functions and that of general recursive partial functions. On the other hand, practical limitations are investigated, that arise from the specific complexity of a problem respectively the algorithm to solve the problem. During the second part of the thesis deterministic and nondeterministic Turing machines are introduced and an overview of their connection to complexity theory is provided. In course of this, the „P=NP“-problem is presented.
Schlagwörter
Schlagwörter
(Deutsch)
Berechenbarkeit Komplexitätstheorie Rekursionstheorie
Schlagwörter
(Englisch)
Calculability Computational Complexity
Autor*innen
Padraig Paul Sweeney
Haupttitel (Englisch)
Introduction to recursion theory and computational complexity
Paralleltitel (Deutsch)
Einführung in die Rekursionstheorie und Komplexitätstheorie
Publikationsjahr
2024
Umfangsangabe
56 Seiten
Sprache
Englisch
Beurteiler*in
Vera Fischer
Klassifikation
31 Mathematik > 31.99 Mathematik. Sonstiges
AC Nummer
AC17265724
Utheses ID
71983
Studienkennzahl
UA | 199 | 520 | 525 | 02