Pages: 1 [2]   Go Down
Print
Author Topic: Applicazione di Rice e Rice-Shapiro per studio decidibilità predicato  (Read 4733 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #15 on: 02-12-2013, 13:56:45 »

Per applicare il primo corollario in questo caso, tenendo conto che il carattere della classe A è l'inclusione dell'immagine nel dominio e non la cardinalità di quest'ultimo, si deve trovare una funzione in A tale che nessuna sua restrizione finita stia in A. Ovviamente avrà dominio infinito (altrimenti essa stessa sarebbe una restrizione finita di sé). Me ne viene in mente una molto ovvia, forse fin troppo ovvia...
Mi scusi, ho fatto questa semplice osservazione:

Sia \fs{4}f\in C_1. Certamente vale \fs{4}A\ni f_\emptyset\subseteq f, quindi non è vero che esistono funzioni calcolabili unarie (dentro o fuori di \fs{4}A) tutte le restrizioni delle quali non stiano in \fs{4}A, giacché ce n'è sempre una che ci sta, ed è proprio \fs{4}f_\emptyset.

Direi che si può usare solo l'altro corollario per questa dimostrazione ...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.383


« Reply #16 on: 02-12-2013, 19:30:38 »

Sia \fs{4}f\in C_1. Certamente vale \fs{4}A\ni f_\emptyset\subseteq f, quindi non è vero che esistono funzioni calcolabili unarie (dentro o fuori di \fs{4}A) tutte le restrizioni delle quali non stiano in \fs{4}A, giacché ce n'è sempre una che ci sta, ed è proprio \fs{4}f_\emptyset.

Direi che si può usare solo l'altro corollario per questa dimostrazione ...
Ha perfettamente ragione, stavolta sono io il colpevole: avevo trascurato l'ineffabile funzione vuota. La sua conclusione è ineccepibile.
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #17 on: 03-12-2013, 04:04:56 »

Senza renderemene conto, ho involontariamente semplificato il lavoro di ricerca su quale corollario applicare quando si senta puzza di non-parziale decidibilità:

Corollario (ai corollari)
Se f vuota è nell'insieme considerato
allora c'è un solo corollario (al più) usabile univ!

Anzi, di più.

Corollario (al corollario (ai corollari))
Se f vuota è nell'insieme considerato, e l'insieme caratterizza non tutte le funzioni calcolabili unarie calcolabili (non è banale)
allora certamente il predicato di appartenenza non è p.d. pray!

(EDIT: avevo erroneamente scritto due volte calcolabili)
« Last Edit: 05-12-2013, 16:49:55 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.383


« Reply #18 on: 03-12-2013, 20:26:41 »

Corollario (al corollario (ai corollari))
Se f vuota è nell'insieme considerato, e l'insieme caratterizza non tutte le funzioni calcolabili unarie calcolabili (non è banale)
allora certamente il predicato di appartenenza non è p.d. pray!
Eccellente! Un corollario al secondo corollario del teorema di Rice-Shapiro che somiglia molto al teorema di Rice, ma per la semidecidibilità. Notevole, grazie.
Logged
Pages: 1 [2]   Go Up
Print
Jump to: