Bezestrojová charakterizace polynomiálně počitatelných funkcí
Thesis title in Czech: | Bezestrojová charakterizace polynomiálně počitatelných funkcí |
---|---|
Thesis title in English: | Machine-Free Characterization of Polynomially Computable Functions |
Key words: | Polynomiální čas, rekurze, Cobham |
English key words: | Polynomial time, recursion, Cobham |
Academic year of topic announcement: | 2013/2014 |
Thesis type: | Bachelor's thesis |
Thesis language: | čeština |
Department: | Department of Logic (21-KLOG) |
Supervisor: | doc. RNDr. Vítězslav Švejdar, CSc. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 09.06.2014 |
Date of assignment: | 09.06.2014 |
Administrator's approval: | not processed yet |
Confirmed by Study dept. on: | 16.06.2014 |
Date and time of defence: | 14.09.2016 09:00 |
Date of electronic submission: | 15.08.2016 |
Date of proceeded defence: | 14.09.2016 |
Submitted/finalized: | committed by student and finalized |
Opponents: | Mgr. Jonathan Verner, Ph.D. |
Guidelines |
Pojem polynomiálně počitatelné funkce je intuitivně poměrně jasný: funkce je polynomiálně počitatelná, jestliže ji počítá algoritmus, který pro zpracování libovolného vstupu vystačí s počtem kroků, který je omezen polynomem v délce onoho vstupu. Exaktní definice je ale ne tak jasná, neboť pro explikaci toho, jak se počítají ony kroky a čeho kroky to jsou, je nutný nějaký výpočtový model, například Turingovy stroje. Je ale zajímavé, že existuje i "bezestrojová" charakterizace tohoto pojmu, která je podobná definici primitivně rekurzívních funkcí. Tomuto tématu jsou věnovány články [1] a [2].
Vypracujte vlastní verzi výkladu této problematiky. Rozmyslete si obsah článku [1], doplňte všechny vynechané detaily a udělejte si vlastní názor na to, zda a jaký účel onen článek splnil. Podle vlastní úvahy případně porovnejte články [1] a [2]. Použijte, ovšem s korektní citací, cokoliv z [3]. Vypracujte teorii polynomiálně počitatelných funkcí ve stylu teorie primitivně rekurzívních funkcí. K [3] případně přidejte důkaz nebo náznak důkazu, že bezestrojová definice je ekvivalentní definici založené například na Turingových strojích. |
References |
[1] S. Bellantoni, S. Cook. A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2:297-110, 1992.
[2] A. Cobham. The Intrinsic Computational Difficulty of Functions, in: Proc. Logic, Methodology, and Philosophy of Science II, Y. Bar-Hillel ed., pp. 24-30. North Holland, 1965. [3] P. Mach. Bezestrojová charakterizace funkcí počitatelných v polynomiálním čase. Předběžná verze nefinalizované ročníkové práce. Katedra logiky FF UK, 1998. |