Název:
Bezestrojová charakterizace polynomiálně počitatelných funkcí
Překlad názvu:
Machine-Free Characterization of Polynomially Computable Functions
Autoři:
Profeld, Michal ; Švejdar, Vítězslav (vedoucí práce) ; Verner, Jonathan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2016
Jazyk:
cze
Abstrakt: [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
Klíčová slova:
Cobham; Polynomiální čas; rekurze; Cobham; Polynomial time; recursion