Hura! Svet se nehrouti :) Aneb rekurze vs. while.

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Kreativní množiny.
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Hura! Svet se nehrouti :) Aneb rekurze vs. while.

Příspěvek od peci1 »

Ahoj, ted pri uceni me napadla kacirska myslenka (pote jsem si ji vyvratil, ale treba nekoho taky poskadli, tak to sem pisu :) ).

Co takhle nahradit

Kód: Vybrat vše

while(P(x)) {
     x = f(x);
}
timto:

Kód: Vybrat vše

function R(x) {
    if (P(x))
        R(f(x));
}
Zda se, ze druha funkce by mohla byt PRF! A presto dela to same, co while! Jak to? Nehrouti se vse, co jsme se ucili? No, nehrouti :) Ona totiz ta druha funkce (ac neobsahuje while) neni PRF. Zkuste si ji zapsat v tom odpornem formalismu. Neco jako g = S_m^n (g, f) (tomuhle formalismu se moje hlava brani, takze to urcite neni presne, ale myslenka je snad zrejma). Jenze ten formalismus je potreba rozepsat do posledni zakladni funkce. A to je ten kamen urazu. Takhle rozepsany by byl samozrejme nekonecny, coz jsme si (snad?) zakazali.

Takze si vesele uzivejte zivota, konec sveta neprichazi dnes, jeste mame skoro 11 mesicu :-D
Odpovědět

Zpět na „TIN064 Vyčíslitelnost I“