Zk 23.1.2013

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zk 23.1.2013

Re: Zk 23.1.2013

od muck » 1. 2. 2013 19:29

\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]\}

Re: Zk 23.1.2013

od blabla » 31. 1. 2013 23:31

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)]\}

Re: Zk 23.1.2013

od strky » 31. 1. 2013 21:02

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

od muck » 31. 1. 2013 13:31

Vypada to spravne :) .

Re: Zk 23.1.2013

od blabla » 31. 1. 2013 02:27

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)

Zk 23.1.2013

od muck » 26. 1. 2013 18:24

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.

Nahoru