Kurzus nemzetközi vendég- és részidős hallgatóknak
- Kar
- Bölcsészettudományi Kar
- Szervezet
- BTK Filozófia Intézet
- Kód
- BMI-LOTD-328E.10
- Cím
- Bizonyításelmélet I.: Kiszámíthatósági elmélet
- Tervezett félév
- Tavaszi
- Meghirdetve
- 2025/26/2
- ECTS
- 4
- Nyelv
- en
- Oktatás célja
- Aim of the course: The course is an intensive introduction to recursion theory and theory of computation. Content of the course: We investigate different computational models such as primitive recursive functions, (partial) recursive functions, register-machines, Turing-machines and their properties. We prove most of the classical theorems regarding recursion theory such as s-n-m Theorem, Rice’s theorem, Halting problem, investigate the properties of recursive and recursively enumerable sets and prove Recursion Theorem. We will study selected applications to logic. Grading criteria: Oral exam Literature: • N. Cutland Computabilit Theory: An introduction to recursive functions, Cambridge. 1984. • D. S. Bridges Computability: A mathematical sketchbook. Springer. 1994 • P.G. Odifredi Classical Recursion Theory. Elsevier. 1992 1 Kód: BMI-LOTD-328E.10 Cím: Kiszámíthatóság elmélet Tárgyfelelős: Zvolenszky Zsófia, PhD Előadó: Molnár Zalán, PhD A tantárgy célja: A kurzus intenzív bevezetést nyújt a rekurzióelméletbe és a számításelméletbe. A tantárgy tartalma: Különböző számítási modelleket vizsgálunk, mint például a primitív rekurzív függvények, a (parciális) rekurzív függvények, a regisztergépek, a Turing-gépek és ezek tulajdonságai. Bizonyítjuk a rekurzióelmélet legtöbb klasszikus tételét, többek között az s-n-m tételt, Rice tételét és a Halting problémát; továbbá vizsgáljuk a rekurzív és a rekurzívan felsorolható halmazok tulajdonságait, és bizonyítjuk a rekurziótételt. Válogatott alkalmazásokat is tanulmányozunk a logika területeiből. Értékelés, speciális követelmények: Szóbeli vizsga Literature: • N. Cutland Computabilit Theory: An introduction to recursive functions, Cambridge. 1984. • D. S. Bridges Computability: A mathematical sketchbook. Springer. 1994 • P.G. Odifredi Classical Recursion Theory. Elsevier. 1992