Bezestrojová charakterizace polynomiálně počitatelných funkcí
Machine-Free Characterization of Polynomially Computable Functions
bakalářská práce (NEOBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/76784Identifikátory
SIS: 151298
Kolekce
- Kvalifikační práce [23725]
Autor
Vedoucí práce
Oponent práce
Verner, Jonathan
Fakulta / součást
Filozofická fakulta
Obor
Logika
Katedra / ústav / klinika
Katedra logiky
Datum obhajoby
14. 9. 2016
Nakladatel
Univerzita Karlova, Filozofická fakultaJazyk
Čeština
Známka
Neprospěl
Klíčová slova (česky)
Polynomiální čas, rekurze, CobhamKlíčová slova (anglicky)
Polynomial time, recursion, CobhamTato 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] 1
This 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