IB107 Vyčíslitelnost a složitost věta o parametrizaci, programovací systémy Jan Strejček Fakulta informatiky Masarykova univerzita věta o parametrizaci ■ funkci lze definovat parametrizací, tj. zafixováním vybraných argumentů jiné funkce Věta (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 2/13 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 ■ ■ ■ ■ ■ ■ *i :=yi; end IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy 3/13 využití věty o parametrizaci Lemma Existuje totálně vyčíslitelná funkce h : N2 N taková, že pro všechna /,/, x e N p/aří Důkaz: ■ definujme funkci f: N3 N jako f (i j, x) = (v?,- o (/, 4>(/\ x)) ■ ŕ je vyčíslitelná a nechí e je její index ■ věta o parametrizaci říká, že existuje tot. vyčíslitelná funkce sf splňující ^S2(e?/J)(x) = N existuje tot. vyčíslitelná funkce r:N^N taková, že pro všechna x, y g N p/aŕŕ ŕ(x,y) = <^M(y). ■ nazývá se také neefektivní podoba věty o parametrizaci ■ lze zobecnit na vyšší počty argumentů Důkaz: ■ nechi e je index f ■ věta o parametrizaci říká, že existuje tot. vyčíslitelná funkce s splňující y>si(e>x)(y) = ¥>e(*,y) = ■ klademe r(x) = s] (e, x) a tudíž r je tot. vyčíslitelná IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy využití translačního lemmatu nechí i[): N -> 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. vyčíslitelná funkce r splňující ii>(x,y) = 1 jsou ^\ ípf^ totální numerace množiny V^. Pokud ý splňuje větu o numeraci a 1. Důkaz: pro j = 1 ■ íp 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. 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 10/13 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. vyčíslitelné funkce r : N N splňující ^m+n) = ■ z < plyne existence tot. vyčíslitelné funkce s : N N splňující ^ = ^ ém+n){yu...iym+„) = jelikož g(/, y,..., y™) = s(s^(r(/), y,..., y™)) je totálně vyčíslitelná funkce, i/; splňuje větu o parametrizaci IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy 11/13 přípustná numerace Definice (přípustná numerace) Totální numerace vyčíslitelných funkcí je přípustná (efektivní), pokud pro ni platí věty o numeraci a parametrizaci. věty o numeraci a parametrizaci jsou nezávislé, tedy ■ existuje numerace, pro kterou platí věta o numeraci, ale neplatí věta o parametrizaci ■ existuje numerace, pro kterou neplatí věta o numeraci, ale platí věta o parametrizaci IB107 Vyčíslitelnost a složitost: věta o parametrizaci, programovací systémy 12/13 numerace totálně vyčíslitelných funkcí Věta Necht ý je totální numerace všech unárních tot. vyčíslitelných funkcí. Pak univerzální funkce ^ : N2 -> N definovaná jako není vyčíslitelná. Důkaz: diagonalizací Důsledek 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 13/13