MindFlyer

About

Username
MindFlyer
Joined
Visits
4,880
Last Active
Roles
Member, Administrator, Moderator
Posts
436

Comments

  • No. Rincontrolla la definizione di K.
  • Di solito su problemi di questo tipo preferisco non dare direttamente la risposta, perché sarebbe inutile. Prima scrivi una soluzione tua (o un approccio), e poi discutiamo su quello.
  • Se non si fanno ipotesi su f, la risposta a ogni domanda è ovviamente "a volte sì, a volte no". Vogliamo per esempio che f sia calcolabile?
  • andreRondo wrote: » @MindFlyer In fondo a pagina 42 delle dispense, dice che la condizione (*) nella definizione di funzione u-ricorsiva può essere rimossa, a patto che la funzione phi(x1,x2,....,xn,y) sia essa stessa una funzione ricorsiva primit…
  • Non so!
  • andreRondo wrote: » Antonio Sisbarra wrote: » Le domande che ha fatto Degano a un orale nella sessione di gennaio: - dimostrare che con le funzioni u-ricorsive si possono calcolare i cicli for Come si risponde a questa? Il Corollario 1.…
  • Ed è tornato anche il latex, grazie a @Gaspare Ferraro .
  • Ok. Allora diamo una risposta più completa. A seconda di come si scelgono B e C ricorsivamente enumerabili, la loro differenza B\C può essere ricorsiva, RE e non ricorsiva, o non RE. Un esempio in cui è non RE è semplice: se B è tutto N e C è K, …
  • Non fare una confusione assurda con le cardinalità. La cardinalità di tutti gli insiemi che hai citato è numerabile (tranne nel caso in cui sono vuoti). La risposta alla domanda è presto data: l'insieme costruito nel padding lemma non è un insiem…
  • Per dire che un insieme non è RE, non basta far vedere che un particolare algoritmo non lo semi-decide. Bisogna far vedere che nessun algoritmo lo semi-decide. Per quanto l'intuizione sia corretta, come dimostrazione non regge.
  • Nel senso che di p sai solo che è l'indice di quella funzione. Molto probabilmente p non è 42. E per dire che è in K, vuoi che sia esattamente 42.
  • Per far funzionare quel discorso vuoi anche che p sia in K (non solo che y non sia in K). Quindi vuoi che p=42, ma questo non è garantito. Il modo giusto di dire quella cosa è questo: voglio una funzione phi_p(z) = { 1 se z=p; indefinita altrimen…
  • Tu devi dire come si calcola phi_f(x) (y) in modo che sia definita per un numero infinito di y se e solo se phi_x(x) termina. Il suggerimento è di simulare phi_x(x) per y passi. Manca la conclusione... Cosa deve restituire phi_f(x) (y)? Comunq…
  • andreRondo wrote: » quindi phi_x di cui parlavi prima, termina se simulato per infiniti y passi Questa cosa non ha senso.
  • Non avevo voglia di scrivere "K segnato" perché c'è un momentaneo problema di LaTeX nel forum, quindi ho scritto la cosa equivalente, ovvero riduzione da K a INF. Tutto qua.
  • Non so cosa vuoi fare con quella psi, quella phi, e quella f, né come siano definite, né che senso abbia impostare le cose così. Tutto quello che vuoi fare è una riduzione da K a INF, che è una cosa abbastanza facile da fare (dato che FIN è molto…
  • caos ha solo detto che invece d'invocare il secondo teorema di Kleene lo si può dimostrare direttamente a partire dal primo teorema di Kleene e dal teorema s-1-1, come accennavo sopra e come spiega anche Wikipedia. Cioè ha ottenuto un k che fa es…
  • Marco Il Marco Basile wrote: » Ciao, questo e' quello che mi ha detto il professore, in quanto ogni sottoinsieme di N puo' essere ridotto ad un altro sottoinsieme di N purche' non sia r.e. Scusa, ma continui a dirla doppiamente sbagliata, perch…
  • Marco Il Marco Basile wrote: » - trovare un insieme A contenuto in N , A completo per riduzioni secondo la classe delle funzioni calcolabili totali (rec) (la risposta e' che tanti sottoinsiemi di N sono completi, ma non N intero, non K (che e' con…
  • Non riesco a vederlo, sei sicura di averlo caricato bene?
    in Appunti Comment by MindFlyer February 25
  • Allora faccio il merge.
  • Ma... C'è un problema di aliasing tra Programmazione di interfacce e Interazione uomo macchina?
  • Ferragina. Non è stato malissimo nel complesso e ho anche imparato una cosa o due sulla compressione di testi, ma lui ha mancato di professionalità in modo veramente poco bello.
  • La mia esperienza è un po' datata, comunque penso che sia ancora valida. Non c'è alcun problema a priori nel fare tirocini preparando esami. L'unica limitazione è che dovrebbe esistere un numero massimo di esami mancanti alla laurea oltre al qua…
  • Non spammate la stessa domanda in due categorie, pls. C'è bisogno che unisca le categorie di CC ed ECC? Come funziona?
  • Certo che no. Definire vuol dire definire. Non saprei come spiegarlo meglio di così, quindi cerco di spiegarlo peggio. Diciamo che tu hai davanti due spazi A e B. Vuoi scrivere un'applicazione lineare con nucleo A e immagine B. Nel senso che…
  • Ok, hai dimostrato che non esiste una funzione calcolabile totale e crescente che genera tutti e soli gli indici di [tex]\varphi_x[/tex] (devi dire tutti e soli, perché se ne genera solo qualcuno o genera anche qualcos'altro la dimostrazione non fun…
  • Fin qui è giusto. Hai dimostrato che [tex]A_x[/tex] non è ricorsivo, e quindi la sua funzione caratteristica non è calcolabile. Come si passa da qui a dire che non c'è una funzione calcolabile totale che genera tutti e soli gli elementi di [tex]A_…
  • Rice ti dice niente?