# Zk 23.1.2013

<{ForumPost(poster="muck", timestamp=2013-01-26 18:24:53)}>


Zk_23.1.2013.PNG

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.

*Attachments:*

- *[Zk_23.1.2013.PNG](/Forum%20archiv/Attachments/5224_105240c2c48a34ec8930a9e33f2a400d)*

<{/ForumPost}>

<{ForumPost(poster="blabla", timestamp=2013-01-31 02:27:08)}>
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)
<{/ForumPost}>

<{ForumPost(poster="muck", timestamp=2013-01-31 13:31:32)}>
Vypada to spravne  :) .
<{/ForumPost}>

<{ForumPost(poster="strky", timestamp=2013-01-31 21:02:04)}>
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?
<{/ForumPost}>

<{ForumPost(poster="blabla", timestamp=2013-01-31 23:31:12)}>

 > S = {x | Wx obsahuje cele cislo} = {x| (ex.y)Fi_x(y) div 2 = 0}

predpokladam, ze co si chcel napisat je:  
$$S = \{x | W_x\ obsahuje\ sude\ cislo\} = \{x | (\exists y)[\varphi_x(y) \mod 2 = 0]\}$$  
  
to je ale cele zle, lebo $\varphi_x(y)$ nemusi byt definovane a tak sa ti ten predikat "zasekne" hned na prvom testovanom $y$. aj keby vsak definovany bol, tak ty nechces modulit funkcnu hodnotu, ale samotne $y$.  
  
konecna aproximacia sa pouzije tak, ze:  
$$S = \{x | (\exists <y, s>)[y \in W_{x, s} \wedge (y \mod 2 = 0)]\}$$
<{/ForumPost}>

<{ForumPost(poster="muck", timestamp=2013-02-01 19:29:38)}>

 > $\varphi_x(y)$ 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:  
$$S = \{x | (\exists y)(\exists s)[\varphi_{x,s}(2y)\downarrow]\}$$
<{/ForumPost}>