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.