IB107 Vyčíslitelnost a složitost věta o parametrizaci, programovací systémy*, rekurzivní množiny Jan Strejček Fakulta informatiky Masarykova univerzita funkce Step counter Lemma 7.9 Funkce Sc(x, y,z) = < ' 1 jestliže program Px zastaví pro vstup y během z kroků jinak je totálně vyčíslitelná. Důkaz: interpreter z důkazu věty o numeraci rozšíříme o počítán instrukcí IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny věta o parametrizaci ■ funkci lze definovat parametrizací, tj. zafixováním vybraných argumentů jiné funkce Věta 5.20 (věta o parametrizaci, věta (Kleene)) Pro každá m^n^l existuje totálně vyčíslitelná funkce sm . ^A7?+i _^ tak0Vá} že pro všechna e, ,..., ym+n e N platí IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny 3/18 důkaz věty o parametrizaci ^(e,y1r..,ym)(^+1' ' ' ^Ym+n) - Ym+n) Důkaz: funkce s™(e, yi,..., y™) vrací index programu begin ■ ■ ■ ■ ■ ■ end IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny 4/18 využití věty o parametrizaci Lemma 5.21 Existuje totálně vyčíslitelná funkce h : N2 N taková, že pro všechna /,/, x e N platí / Důkaz: ■ definujme funkci ř: N3 N jako f{ij, x) = o (/, 4>(/\ x)) ■ ř je vyčíslitelná a nechí e je její index ■ věta o parametrizaci říká, že TVF sf splňující ^s?(e,/j)(x) = ^e(/J» = ■ klademe /)(/,/) = s2(e, /,/) a tudíž Ai je totálně vyčíslitelná IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny translační lemma Důsledek 5.23 (translační lemma) Ke každé vyčíslitené funkci f: N2 -> N existuje totálně vyčíslitelná funkce r:N^N taková, že pro všechna x, y e N platí f{x,y) = S je (ne nutně totální) numerace podmnožiny unárních vyčíslitelných funkcí S c v, která splňuje větu o numeraci, tj. existuje vyčíslitelná funkce ^ : N2 —^ N taková, že pro všechna x, y e N platí ■ dle translačního lemmatu pak existuje totálně vyčíslitelná funkce r splňující ii>(x,y) = 1 jsou ^\ ípf^ totální numerace množiny V^. Pokud íp splňuje větu o numeraci a ípř větu o parametrizaci, pak ýU) < ý'U) pro každé j > 1. Důkaz: pro j = 1 ■ má vyčíslitelnou univerzální funkci ■ translační lemma pro 1 je ýU) totální numeraci množiny V® a cpU) její standardní numeraci Pak ý splňuje věty o numeraci a parametrizaci, právě když pro každé j > 1 platí ^(y) = plyne z předchozí věty <== ukážeme, že íp splňuje větu o numeraci ■ pro každé j > 1 je univerzální funkce ^ : Ny+1 N pro ý definovaná vztahem ■ z < cpW plyne existence totálně vyčíslitelné funkce r : N N splňující ^}y) = <^ ■ tedy je vyčíslitelná IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny 11/18 vztahy ke standardní numeraci <== ukážeme, že íp splňuje vetu o parametrizaci ■ nechí m, n > 1 ■ z ^m+n) < (p(m+n) plyne existence totálně vyčíslitelné funkce r : N N splňující ^m+n) = ■ z ^ : N2 -> N definovaná jako není vyčíslitelná. Důkaz: diagonalizací ■ Důsledek 6.6 Neexistuje přípustná totální numerace všech totálních vyčíslitelných funkcí. IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny 14/18 rekurzivní množiny Definice 7.1 (rekurzivní množina) Množina AcNk je rekurzivní, pokud existuje totálně vyčíslitelná funkce f : Nk -> N taková, že A = f-\V}) = {(xi,...,xk)eNk | f(x,,...,xk) = 1}. Funkce f se nazývá rozhodovací funkce pro A. ■ rekurzivní množině se také říká rozhodnutelná či řešitelná ■ příklady rekurzivních množin: IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny 15/18 rekurzivní množiny Tvrzení A c Nk je rekurzivní, právě když je její charakteristická funkce Xa ■ ^k -> N definovaná vztahem 1 pokud (x1,..., xk) g A 0 jinak totálne vyčíslitelná. Důkaz: IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny vlastnosti rekurzivních množin Věta 7.4 Jestliže A c je konečná množina nebo Nk \ A je konečná, pak A je rekurzivní. Důkaz: IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny 17/18 vlastnosti rekurzivních množin Lemma 7.5 Necht A, B c jsou rekurzivní množiny. Pak i množiny A, Au B a A n B jsou rekurzivní. Důkaz: IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy*,, rekurzivní množiny