Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: nairi on 20-06-2013, 09:04:58



Title: es calcolabilità e t. s-m-n
Post by: nairi on 20-06-2013, 09:04:58
 .ciaociao Ciao raga! Vi propongo la soluzione di 2 esercizi che spero siano corretti!

1) Usare il t s-m-n per dimostrare che esiste una funzione totale e calcolabile s(k) :
Ws(k)={x,2x,3x,...} e Es(k)={x,x^2,x^3,...}

Soluzione:
         
           x(y/x)   se "y è un multiplo di x"
f(x,y)= \uparrow  altrimenti

f(x,y)=(1\cdot(\muz(y=x\cdotz)))\cdotx(y/x)
e poi applico il t s-m-n...

2)Usare il t s-m-n per dimostrare che esiste una funzione totale e calcolabile s(x) :
Ws(x)={x+n2 : n\in N }  e Es(x)={nx : n\in N}

Soluzione:

f(x,y)=x(\muz(y=x+z2))
e poi applico il t s-m-n...

Che ve ne pare?!  :yoh


Title: Re:es calcolabilità e t. s-m-n
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 20-06-2013, 10:02:45
Sono entrambi corretti, a parte quel puntino dopo 1 nel primo esercizio :-)|, e il fatto che hai scritto una cosa che matematicamente può produrre anche numeri razionali, mentre tu devi gestire solo interi: in particolare
non puoi scrivere x(y/x) .nono ma devi scrivere xqt(x, y) .sisi.

Mi fa piacere che nel secondo tu sia riuscita a riciclare il valore z ottenuto dalla minimalizzazione, cosa che invece non sei riuscita a fare nel primo: era così difficile, in fondo riciclarlo .smile?

Alla fine tu, se ci pensi, prendi quell'unico z intero che (se esiste) è il quoziente intero della divisione con resto zero di y/x, ma quello è proprio il valore restituito dall'operatore di minimalizzazione!

Potevi scrivere, quindi, più semplicemente:

\fs{5}f\({x,\;y}\)=x^{\mu_z\({y=zx}\)} :boh


Title: Re:es calcolabilità e t. s-m-n
Post by: nairi on 20-06-2013, 10:51:18
Quote
Potevi scrivere, quindi, più semplicemente: ...

Wow! la mia mente non è così elastica da pensare di mettere \mu... come esponente! :D ...

Cmq grazie per le correzioni!


Title: Re:es calcolabilità e t. s-m-n
Post by: nairi on 21-06-2013, 20:43:17
Si dimostri che esiste una funzione k(x), totale e calcolabile, tale che per ogni x\in N si abbia
Wk(x) = {2x, 2x + 2, 2x + 4, . . .}
Ek(x) = {2x + 1, 2x + 3, 2x + 5, . . .} .

Ecco la soluzione:

f(x,y)=2x+(\muz(y=2x+z \wedge z pari)+1)

f(x,y) è calc e poi applico t s-m-n...

è giusto?  .rido


Title: Re:es calcolabilità e t. s-m-n
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-06-2013, 00:47:02
 :-OK

Io avrei scritto un'altra formulazione egualmente corretta: .smile

\fs{3}f(x,\;y)\;=\;2x+2\mu_z\({y=2x+2z}\)+1\;=\;2\({x+\mu_z\({y=2\({x+z}\)}\)}\)+1


Title: Re:es calcolabilità e t. s-m-n
Post by: nairi on 22-06-2013, 08:37:49
Quote
Io avrei scritto un'altra formulazione egualmente corretta


grazie ;) più idee si hanno e meglio è!!!