Matematické Fórum

Lishaak · 21. 12. 2008 22:34

Nasel by se na tomto foru nekdo, kdo ma vhled do teorie castecne rekurzivnich funkci?

Kondr · 21. 12. 2008 23:10

Vygooglil jsem, že to jsou funkce vyčíslitelné while-programem nebo Turingovým strojem. Takovým funkcím se u nás (na FI MU) říká vyčíslitelné a formalizmus kolem nich jsme si zaváděli asi trochu jinak, než vy na matfyze (právě pomocí while-programů a Turingových strojů). Zkus upřesnit dotaz.

Lishaak · 21. 12. 2008 23:55

Aha. No ja se touto teorii zabyvam zatim docela kretkou dobu, ale je to opravdu fascinujici oblast matematiky. Mam ale takovyto problem. Jedno tvrzeni rika, ze castecne rekurzivni funkce se da ekvivalrentne definovat takto:

$f(\vec{x}) \simeq \mu yR(\vec{x}, y)$

Kde R je obecne rekurzivni relace. Tedy f je castecne rekurzivni prave tehdy, kdyz existuje rekurzivni relace splnujici vyse uvedeny vztah. Kniha rika, ze to je dusledek vety o normalni forme, ale ja to v tom nevidim. Neni mi jasna implikace zprava do leva, tedy jak k castecne rekurzivni funkci f najit tu relaci R.

Kondr · 24. 12. 2008 03:26

↑ Lishaak:Tak tohle s naším pojetím vyčíslitelných fcí dokázat neumím (po pravdě ani moc nevím, co je to mí).

Matematické Fórum

#1 21. 12. 2008 22:34

Castecne rekurzivni funkce

#2 21. 12. 2008 23:10

Re: Castecne rekurzivni funkce

#3 21. 12. 2008 23:55

Re: Castecne rekurzivni funkce

#4 24. 12. 2008 03:26

Re: Castecne rekurzivni funkce

Zápatí