Fórum studentů MFF UK

1.) KxK' = {<x,y> : x patri do K & y patri do K' }
Je mnozina rs? Je jej doplnok rs?

2.) Obor hodnot CRF je RS mnozina

3.) zostrojte n₀ : fi_n0 (w) = n₀

Uspech bol asi dost velky

...a vraj bude mozno este jeden termin

macbeth píše: Uspech bol asi dost velky

Nemam ten pocit

hippies píše:Nemam ten pocit

preto ten smajl... neviem, ci viac ako 5 ludi dostalo nejaku znamku...

ale inak by ma celkom zaujimalo, co si o nas pan Kucera mysli, ked nam dava take trivialne veci a 2/3 z terminu odidu dobrovolne... vlastne to radsej asi ani nechcem vediet

aha, oni ti ludia teda odchadzali vacsinou bez znamok... sa mi to zdalo nejake podozrive, ze ako sa vsetci rozbehli (pohruzeny do dokazovania som nestihal sledovat, ci odchadzaju so zapisom v indexe. vsimol som si akurat toho, co vzal dvojku, lebo sa ponahlal na rande )

inak fakt vdaka za tieto otazky, ziadne zlozite vety (aj tak som 2. mal na prvykrat zle )

ja to jako vymyslel vsechno, jen jsem mezitim vymyslel spoustu nesmyslu a postupne jsem to skrtal i stim co bylo dobre, .. kdyz pak po nahledu do me prace pronesl ze nas nechce premlouvat, ale ze navzajem se trapit mu prijde zbytecne, usoudil jsem, ze jsem uplne mimo misu a vzdal, pritom kdyby sedel vedle me, tak by to na 2 verim dopadlo:/ .. mno nic, pouceni pro priste a je fakt, ze kdyz jsem to tam mel napsany a neuvedomil si to, ze si to asi potrebuju opravdu jeste projit.

tedy: uvidime se zase v patek:D

Muzete mi nekdo upresnit co to je ta treti otazka? to ma sestrojit funkci co vypisuje svuj kod?

presne to znamena: kod funkce, ktera vypise svuj kod

Mohli by ste niekto povedat ako sa ten posledny priklad riesi? Ja nejak ani netusim co je vysledok (cislo, program, mnozina, funkcia, ... )

http://wiki.matfyz.cz/wiki/TIN064_V%C4%9Bty_o_rekurzi

Důsledek: quine v ČRF je snadný

A ty zbyle dva? ( hlavne prvni, i kdyz to vysvetleni pro druhy, co je ve Strojilovo skriptech mi taky neprijde moc dostatecne )

1) majme nejake pevne a z K a b z K'

definujme
f(x) = <x, b>
g(x) = <a, x>

f(x) i g(x) su proste ORF.

K je 1-preveditelne na KxK' pomocou f, tj. K' je preveditelne na (KxK')' pomocou f => keby (KxK')' bola r.s. bola by i K' r.s., co je spor.
K' je 1-preveditelne na KxK' pomocou g => keby KxK' bola r.s., bola by i K' r.s., co je spor.

Teda ani jedna nie je r.s.

2) mame CRF f a jej obor hodnot range(f).
Chceme najst CRF h t.ž. dom(h) = range(f).

definujme h(y) = prva zlozka z min_<x,s>{f(x) konverguje za s krokov a je rovne y}
vysvetlenie:

• ak pre y neexistuje x, ze f(x)=y, tak program neskonci, co je ok, lebo y je mimo range(f) a teda mimo dom(h)

• ak pre y existuju nejake x, ze f(x)=y, tak nejake najdeme. Predpokladame, ze kody dvojic <x,s> su usporiadane tak, ze sa na kazdu dostane, teda nie napr. ze najskor preberiem <x,1> pre vs. x, potom <x,2> pre vs. x; ani nie najskor <0,s> pre vs. s, potom <1,s> pre vs. s; to by az na specialne pripady nikdy nekonvergovalo. Vhodne poradie preberania dvojic je napr. nasledovne:

  Kód: Vybrat vše

    s|
  x  | 0 1 2 3 4 ...
  ----------------------
    1| 1 2 4 7 11 ...
    2| 3 5 8 12 ...
    3| 6 9 13 ...
    4| 10 ...
    ...
  

  Tak budeme verit, ze nase zvolene kodovanie dvojic usporiada dvojice v nejakom podobnom poradi

Poznamka: nemozeme definovat h jednoducho takto:
h(y) = min_x{f(x) = y}
Povedzme, ze najmensie x, ze f(x)=y je 1 a ze f(0) nie je definovane.
Skusame postupne x od 0 do nekonecna, ci f(x)=y. ale uz na f(0) program diverguje, takze sa ani nedostaneme k tomu, aby sme otestovali f(1). Takze min_x{f(x) = y} nedokazeme efektivne vycislit a teda sa nam nepodari skonstruovat takuto h tak, aby bola CRF.

Diky moc