Original title:
Bezestrojová charakterizace polynomiálně počitatelných funkcí
Translated title:
Machine-Free Characterization of Polynomially Computable Functions
Authors:
Profeld, Michal ; Švejdar, Vítězslav (advisor) ; Verner, Jonathan (referee) Document type: Bachelor's theses
Year:
2016
Language:
cze Abstract:
[cze][eng] Tato bakalářská práce se zabývá sestavením Matematického systému. Tento systém je pečlivě vypracovaný, tak aby byl uzavřený na funkce, které v něm figurují. Je vytvořen tak, aby pokryl funkce určitého růstu. Konkrétně funkce, o kterých můžeme říct, že operují v polynomiálním čase na Turingové stroji. Platí tedy, že náš systém obsahuje všechny funkce, které na Turingových strojích běží v polynomálním čase, nebo v čase rychlejším a žádné jiné funkce neobsahuje. Tvorba tohoto mate- matického systému byla ovlivněna především prací Samuela R. Busse [1] 1This work is focused into constructing mathematical structure. This structure is closed under it's operations. Structure was developed to contain all functions of certain growth rate. To be More specific functi- ons with polynomial growth rate. We can say that our structure con- tains all functions that have growth rate slower or equal to polynomial growth rate and no other function. Development of our structure was influenced mostly by work of Samuel R. Buss [1] 1
Keywords:
Cobham; Polynomial time; recursion; Cobham; Polynomiální čas; rekurze
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/76784