Stránka 1 z 1
Zk 23.1.2013
Napsal: 26. 1. 2013 18:24
od muck
1) S neni rekurzivni podle Riceovy vety (mame tridu CRF, ktere se zastavi na alespon jednom sudem cisle a ta neni urcite prazdna ani neobsahuje vsechny CRF). Mnozina S je rekurzivne spocetna, protoze ji muzu zapsat pomoci existencnich kvantifikatoru a rekurzivni podminky - v ni se pouziva konecna aproximace. No a kdyz S neni rekurzivni a je rekurzivne spocetna, tak podle Postovy vety doplnek S neni rekurzivne spocetna mnozina.
2)
(a)
- f1(x) = 2x
- f2(x) = 2x + 1
(b) Existuje ORF f3 prevadejici A na C, stejne tak i ORF f4 prevadejici B na C. Funkce f5 se bude chovat takto:
- kdyz vstup je sudy, vydeli ho dvema (tim ziska prvek z A) a pusti funkci f3
- kdyz vstup je lichy, odecte od nej 1, vydeli dvema (tim ziska prvek z B) a pusti funkci f4
Takto zadefinovane funkce f1, f2 i f5 jsou ORF, takze m-prevadi podle zadani.
Trojku nevim a co jsem si vytahl na ustni nemusim rikat. Je to o nahode a kazdy muze dostat cokoliv ze seznamu co ma pan Kucera na strankach. Tak hodne stesti vsem, koho to jeste ceka.
Re: Zk 23.1.2013
Napsal: 31. 1. 2013 02:27
od blabla
skusil som si dat dohromady tu funkciu f5, tak ked tak to niekto skontrolujte:
f_5(x) = ((x + 1) MOD 2) * f_3(x DIV 2) + (x MOD 2) * f_4((x - 1) DIV 2)
Re: Zk 23.1.2013
Napsal: 31. 1. 2013 13:31
od muck
Vypada to spravne
.
Re: Zk 23.1.2013
Napsal: 31. 1. 2013 21:02
od strky
Ja mam otazku este k tej jednotke. Ako sa tam pouziva konecna aproximace?
Nestaci to prepisat na: S = {x | Wx obsahuje cele cislo} = {x| (ex.y)Fi_x(y) div 2 = 0} a povedat, ze operacie div a = su rekurzivne spocetne a ex. kvantifikator tu rekurzivnu spocetnost tiez nepokazi a teda cela S je rekurzivne spocetna?
Re: Zk 23.1.2013
Napsal: 31. 1. 2013 23:31
od blabla
S = {x | Wx obsahuje cele cislo} = {x| (ex.y)Fi_x(y) div 2 = 0}
predpokladam, ze co si chcel napisat je:
to je ale cele zle, lebo
nemusi byt definovane a tak sa ti ten predikat "zasekne" hned na prvom testovanom
. aj keby vsak definovany bol, tak ty nechces modulit funkcnu hodnotu, ale samotne
.
konecna aproximacia sa pouzije tak, ze:
Re: Zk 23.1.2013
Napsal: 1. 2. 2013 19:29
od muck
nemusi byt definovane a tak sa ti ten predikat "zasekne" hned na prvom testovanom y.
Jen na upresneni - predikat se muze "zaseknout" (a neskoncit) prave kvuli tomu, ze se nepouzije konecna aproximace.
Blabla to pise dobre. Tento zapis mnoziny S by taky mel byt v poradku: