Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: nairi on 22-06-2013, 09:02:43



Title: un'altra serie di esercizi misti
Post by: nairi on 22-06-2013, 09:02:43
Non so se riuscirò a fare altre es nuovi ma intanto posto gli ultimi rimasti per completarli o assicurarmi che siano corretti  :[Emoticon] PC Asd:

ecco il primo: Si dimostri che esiste una funzione f unaria, totale e non calcolabile tale che f(x) sia divisibile per x + 1, per ogni x ∈ N.

soluzione:

          (\lfloorqt(x+1, \phix(x))\rfloor +1)(x+1)      se \phi x(x)\downarrow
f(x)=
           2(x+1)                                     se \phix(x)\uparrow

per il primo caso mi sono aiutata con un esercizio un po' simile che abbiamo discusso anche qui sul forum!
Ho capito come si fanno questi esercizi o ancora sono un caso disperato?!  .bah


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-06-2013, 10:31:59
Hai capito, hai capito :-OK.


Title: Re:un'altra serie di esercizi misti
Post by: nairi on 22-06-2013, 11:03:26
Quote
Hai capito, hai capito

happyyyyyyyyyyyyy  :yoh


Title: Re:un'altra serie di esercizi misti
Post by: Mari_C on 22-06-2013, 13:49:56
Che mi dici di questo esercizio???

Si dimostri che esiste una funzione unaria, totale e non calcolabile tale che f(x) sia dispari \forall x \inN

        \phix(x)+2          se \phix(x)\downarrow b \wedge "b dispari"
f(x)=\phix(x)+1          se \phix(x)\downarrow b \wedge "b pari"
       1                    se \phix(x)\uparrow

Cosi dovrei garantire che f(x) sia dispari che sia diversa da \phi(x) per la non calcolabilità... .camberman


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-06-2013, 14:23:50
 :-OK


Title: Re:un'altra serie di esercizi misti
Post by: nairi on 22-06-2013, 20:28:56
ecco un ultimo predicato:

P(x) = “\phix è una funzione totale e costante.”

Soluzione:
Per l'indecidibilità di P(x) uso il t di Rice:

A={\phix  \in C1 : P(x)}
A non banale poichè contiene certamente la funzione 0 (0\inA) e inoltre A\neqC1 in quanto f\empty \in C1 ma f\empty \notin A.
Quindi {x| P(x)} non è Ricorsivo \rightarrow P(x) non è decidibile

Al punto in cui sono dovrei dim che \negP(x) sia non pd per potermela cavare!
Ma non riesco a continuare!
Intanto formulo  \negP(x) = “\phix è una funzione non totale o non costante.”
ammesso che sia giusta cosa dovrei usare di Rice-Shapiro?
 :pray help!!!!


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-06-2013, 03:21:03
ammesso che sia giusta cosa dovrei usare di Rice-Shapiro?
 :pray help!!!!
Uno dei corollari al teorema .smile!

Intanto ti chiedo: perché hai detto che "al punto in cui sei devi dimostrare che ¬P è non p.d."?
Non ti piace iniziare col dimostrare che è P stesso a non essere p.d.? .penso

I corollari sono due (non ricordo mai l'ordine, ma comunque).

-uno lo usi così: prendi una funzione certamente appartenente ad A, poi fai vedere che qualsiasi/ogni restrizione finita di essa non ne fa parte

-l'altra la usi così: prendi una funzione finita certamente appartenente ad A, poi fai vedere che esiste almeno una sua estensione che non appartiene ad A

Se si verifica uno di questi casi, A non è r.e., equivalentemente P non è p.d.


Title: Re:un'altra serie di esercizi misti
Post by: nairi on 23-06-2013, 09:58:42
allora il lavoro fatto cn il teorema di Rice è superfluo xD ... sono 4 no nella tabellina giusto?


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-06-2013, 11:27:05
Praticamente sì :boh. La bravura dello/la studente/studentessa sta anche nell'intuire cosa conviene fare di volta in volta, in base alla funzione in analisi .arrossisco.


Title: Re:un'altra serie di esercizi misti
Post by: nairi on 23-06-2013, 11:32:47
per il T di Rice Shapiro per P(x):

considero le funzioni unarie,totali,costanti e calcolabili come ad es 0 che appartengono ad A (sto usando la A definita prima)
ma ogni restrizione di queste funzioni non possono essere totali quindi non appartengono ad A.
quindi {x|P(x)} non è R.E \Rightarrow P(x) non  PD

per il \negP(x) cosa posso usare invece?


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-06-2013, 12:04:49
per il T di Rice Shapiro per P(x):

considero le funzioni unarie,totali,costanti e calcolabili come ad es 0 che appartengono ad A (sto usando la A definita prima)
ma ogni restrizione di queste funzioni non possono essere totali quindi non appartengono ad A.
Per la precisione, devi considerare tutte le restrizioni finite, non generiche.
Però possiamo dedurre che se già quelle generiche non ne fanno parte, a maggior ragione non ne faranno parte quelle specifiche (finite), delle quali sono un sottoinsieme.

per il ¬P(x) cosa posso usare invece?
Devi considerare A={ϕx non totali oppure non costanti}
e applicare uno dei corollari.

Quindi, per es. se scegli un corollario, consideri una funzione sicuramente in A, e poi fai vedere che qualsiasi sua restrizione finita non appartiene ad A, oppure, scegli l'altro corollario, consideri una funzione finita sicuramente in A e poi fai vedere che una qualsiasi sua estensione non appartiene ad A.


Title: Re:un'altra serie di esercizi misti
Post by: nairi on 23-06-2013, 16:01:32
Quote
Quindi, per es. se scegli un corollario, ...  oppure, scegli l'altro corollario

 :"-( la teoria la so ma non sempre riesco ad applicarla!!!!!  .poverinoi

per \neg P(x)  considero la funzione f\empty \in A (ha dominio finito) che non è costante (ps ma è o  non è: non totale ovvero \neqN ??)
invece esiste almeno una sua estensione che non è nè non totale nè non costante ovvero la 0 per fare un es che non appartiene dunque ad A!

Questo ragionamento è più specifico? Ps per quella di P(x) che funzione avrei potuto usare dato che quel ragionamento era un po' generico?
 grazie per le risposte che ci dai  |-O !!!


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-06-2013, 17:57:21
[...]invece esiste almeno una sua estensione che non è nè non totale nè non costante ovvero la 0 per fare un es che non appartiene dunque ad A!

Questo ragionamento è più specifico?
Sì, è un ragionamento corretto. E la dimostrazione funziona .smile.


Title: Re:un'altra serie di esercizi misti
Post by: student on 27-11-2013, 13:26:28
per il T di Rice Shapiro per P(x):

considero le funzioni unarie,totali,costanti e calcolabili come ad es 0 che appartengono ad A (sto usando la A definita prima)
ma ogni restrizione di queste funzioni non possono essere totali quindi non appartengono ad A.
quindi {x|P(x)} non è R.E \Rightarrow P(x) non  PD

Rileggendo il topic e provando a risolvere questo esercizio mi sorge un dubbio. In questo caso è stata scelta come funzione f, dalla quale tirare fuori la restrizione finita \theta, la funzione costante 0. Ma perché ogni sua restrizione finita \theta non appartiene ad A? A me sembra (ma evidentemente mi sbaglio) che ogni restrizione finita possa anch'essa essere considerarta unaria, totale, costante e calcolabile, quindi appartenente ad A. O no? Dove sbaglio?

lg


Title: Re:un'altra serie di esercizi misti
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 27-11-2013, 14:13:50
[...]perché ogni sua restrizione finita \theta non appartiene ad A? A me sembra (ma evidentemente mi sbaglio) che ogni restrizione finita possa anch'essa essere considerarta unaria, totale, costante e calcolabile, quindi appartenente ad A. O no? Dove sbaglio?
Sbagli nel non aver compreso la definizione di funzione totale e di funzione finita.

Diremo funzione finita una funzione che ha dominio finito (cioè che non va in loop in un numero finito di punti).

Diremo funzione totale una funzione che ha dominio tutto , quindi infinito (non va mai in loop).

Una funzione può essere solo di tre tipi, mutualmente esclusivi ed esaustivi: finita, totale o strettamente/propriamente parziale (cioè né finita né totale).

Evidentemente, se è finita non è totale e se è totale non è finita .smile.


Title: Re:un'altra serie di esercizi misti
Post by: student on 27-11-2013, 15:45:01
Esatto, non avevo considerato la totalità di f relativa a tutto N, includendo anche gli insiemi finiti. Perfetto, adesso è tutto chiarissimo e il ragionamento fila. Grazie ancora per la tua disponibilità e pazienza.

lg