Vyčíslitelnost (2024)

kontakt

anotace

Smyslem přednášky je projít klasickou teorii efektivní vyčíslitelnosti a rekurzivních funkcí, se zaměřením na souvislosti s matematickou logikou a teoretickou informatikou.

V letním semestru 2023/2024 je přednáška v češtině a angličtiny spojená, tj. předměty NI-VYC a NIE-VYC probíhají společně, v angličtině. Sledujte tedy letos NIE-VYC.

literatura

Poznámky k přednášce postupně zanáším do studijního textu k matematické logice, níže uvádím původní literaturu.

rekurze a vyčíslitelnost

Enderton: Elements of Recursion Theory (Part C.1 of J. Barwise: Handbook of Mathematical Logic)
Enderton: Computability Theory
Kleene: Introduction to Metamathematics (Part III: Recursive Functions)
Kleene: Origins of Recursive Function Theory
Mendelson: Introduction to Mathematical Logic (Chapter 5, Effective Computability)
Monk: Mathematical Logic (Part I: Recursive Function Theory)
Rogers: Theory of Recursive Functions and Effective Computability

aritmetika a logika

Church: A note on the Entscheidungsproblem
Church: An Unsolvable Problem of Elementary Number Theory
Kleene: Mathematical Logic (Chapter V: Computability and Decidability)
Štěpánek: Meze formální metody

bylo

20.02. Turingovy stroje, vyčíslitelné funkce.
27.02. elementární funkce a relace; prvočíselné kódování.
05.03. primitivní rekurze; iterovaná mocnina (tower function).
12.03. obecné rekurzivní funkce; univerzální kódovací funkce.
19.03. částečné rekurzivní funkce. Turingovy stroje.
26.03. kódování Turingových strojů funkcemi a naopak.
02.04. univerzální funkce; rekurzivní spočetnost.
09.04. věta o parametrech, Riceova věta.
16.04. aritmetizace dokazatelnosti, Gödelova věta o neúplnosti.

bude

23.04.
30.04.
07.05.
14.05. (rektorský den)

cvičení

Zde budu zadávat drobné i větší úkoly na cvičení, jejichž plnění přispívá k získání zápočtu.

Ukažte podrobně, jakého ranku (vůči iterované mocnině) jsou každodenní funkce jako polynomy, faktoriál, atd.
Ukažte podrobně, jak se zvedne rank při sumaci a multiplikaci.
Napište konkrétní Turingův stroj pro binární maximum.
Napište konkrétní Turingův stroj pro binární součet.
Napište Turingův stroj, který binárně kóduje slova v abecedě a,b,c.

Při implementaci strojů se můžou hodit následující emulátory:

tm (Turingovy stroje)
ma (Markovovy algoritmy)
rr (register machines)

hodnocení

Úspěšně absolvovat NI-VYC obnáší získat zápočet a složit zkoušku.

Na přednáškách i cvičeních budu průběžně zadávat drobné podúlohy, přeskakovat krátké důkazy technikálií apod, které pak podrobně uděláme (tj. uděláte :-) na cvičeních. Cvičení budou typicky začínat takovými úkoly z posledně / z přednášky. Zkoušce pak předchází zápočtový test obsahující dva „početní“ příklady. Zkoušku lze skládat teprve po získání zápočtu.

Po dvou „praktických“ úlohách tvořících zápočet (typicky konstrukce nějaké konkrétní funkce či stroje) následují dvě obsáhlejší „teoretické“ otázky (typicky definice-věta-důkaz). V teoretických otázkách jde o pochopení základních pojmů, hlavní věty, a hlavní myšlenky důkazů, nikoli o sáhodlouhou indukci nebo technikálie.

Pokud někoho obzvláště zaujme některé z témat, která jsme prošli, může jednu z těchto teoretických otázek navrhnout sám předem. Taková zkoušková otázka podléhá mému schválení co do rozsahu.

zkouškové termíny

Zkouškovým termínem je kterýkoli den zkouškového období, který se vám hodí, pokud o něm vím řekněme dva dny předem (sedím třeba ve státnicové komisi). Při našem počtu nemá cenu vypisovat termíny hromadně, resp. můžeme termín formálně vypsat přímo pro to jednotlivé zkoušení.