IB107 Vyčíslitelnost a složitost
0. ledna 2021, 100 minut
1. (25 bodu) Rozhodněte, zda je následující funkce / : N2 —>• N vyčíslitelná.
Í<y9i(107)     pokud (fi není rozšířením funkce (fj _L jinak
Své rozhodnutí dokažte. (Pro důkaz, že funkce je vyčíslitelná, stačí napsat while-program, který ji počítá.)
Řešení: Sporem dokážeme, že / není vyčíslitelná. Předpokládejme, že / je vyčíslitelná.
Nejdříve definujeme funkce g, h : N —>• N tak, aby platilo:
í _L pokud x > 108 a ^(x-108) = _L I 1 jmak
í _L pokud x > 108 a ^(x-108) = _L a x-108 ^ i I 1 jinak
Funkce g, h jsou totálně vyčíslitelné, g (i) vrací pro dané i kód programu begin
if xi > 108 then       xi - 108); xi := 1; end
a h (i) vrací pro dané i kód programu: begin
if xi > 108 A xi-108 ^ i then $(i,x1 - 108); X! := 1; end
Pokud (fi(i) -L, pak jsou funkce fg(i) a y^j) identické. Pokud (fi(i) = _L, pak se tyto funkce liší právě na vstupu i + 108, kde (pg^(i + 108) = _L a V3h(i)(* + 108) = 1. Tedy <fg(i) není rozšířením právě když ifi(i) = _L.
Pro každé i platí (fg^(107) = 1. Celkově dostáváme:
i E K <í=> fi(i) = -L    <í=>    'ŕ'g(i) není rozšířením (fh(i)
^    /(ff(i),/l(i)) = <r»ff(i)(107) = l <í=>    í{g{i), h (i)) je definováno
Jelikož jsou funkce g, h totálně vyčíslitelné a o funkci / předpokládáme, že je vyčíslitelná, je vyčíslitelná i funkce s : N —> N definovaná vztahem s (i) = f(g(i),h(i)). Z výše uvedeného plyne, že s (i) je definovaná právě pro i G K. Proto K je definičním oborem vyčíslitelné funkce a tudíž r.e. To je spor s faktem, že K není r.e.