Elementi di calcolabilità
1 - Riguardo a EXT, come dimostro che non è nè R nè R.E? Ha qualcosa a che vedere con il fatto che le sue funzioni si possono estendere a TOT?
-Basta descrivere una funzione che vale 1 se x=0 ed è indefinita altrimenti, dimostro che non è R tramite il teorema di Rice e che non è R.E con una riduzione da K segnato a EXT
2 - EXT è un I.I.R.F?
- Dal teorema di Rice, ne consegue che lo è perché EXT non è vuoto nè uguale ad N
3 - I = {x | n < x < 2n e Phi_x = Phi_n} sono R, R.E? Com'è la loro unione?
- E' un insieme finito, quindi ricorsivo, se uniamo i due insiemi al variare di n sono ricorsivi
4 - Sappiamo dal Padding Lemma che esiste una funzione che restituisce indici di macchine equivalenti, ne può esistere una che li restituisce tutti?
- Una funzione che è praticamente tutto N (?)
5 - K segnato si riduce a TOT
- E' meglio ridurre K a TOT segnato, in tal caso però mettere come valore restituito dalla Psi 1/2 se x€K non vale perché 1/2 non è N
6 - L'unione finita di insiemi ricorsivi è R o R.E? L'unione infinita invece è R o R.E?
- Unione finita di insiemi ricorsivi : Basta definire la loro funzione caratteristica relativamente all'unione di questa oppure che restituisce il massimo tra {Caratt.A,Caratt.B}
- Unione infinita di insiemi ricorsivi:
Se prendo I0 = {x | Phi_x converge in zero passi}
I1 = {x | Phi_x converge in un passo}
...
In = {x | Phi_x converge in n passi}
La loro unione per i€N è proprio K, che non è ricorsivo (ma è ricorsivamente numerabile)
- Unione finita di insiemi ricorsivamente numerabili : Se faccio andare una macchina in un procedimento a coda di colomba alternativamente per dire se un elemento appartiene ad un insieme A oppure ad un insieme B con A e B € RE oppure dire "MAI" se non converge, allora genero un insieme ricorsivamente numerabile (vedere Teorema 1.10.4 in merito)
- Unione infinita di insiemi ricorsivamente numerabili : Se l'unione finita di insiemi ricorsivi non è ricorsiva e non è detto che quella di insiemi ricorsivamente numerabili sia ricorsivamente numerabile
7 - Esiste f calcolabile totale t.c per ogni x. Dom(Phi_f(x)) = N e per ogni y Phi_z(y) = z => Phi_f(x)(y) = z?
- Esiste, basta prendere come f una funzione costante f = ly.z
8 - Proprietà di I = { x | x € Imm(f) e Dom(g)} con f,g calcolabili totali
- Se g è calcolabile totale, il dominio di g = N e se inoltre x€Imm(f), allora l'insieme I è immagine di una funzione
calcolabile e quindi è ricorsivamente numerabile
9 - Proprietà di A = {i | Phi_i = Phi_2i}
-Utilizzando il teorema del punto fisso, possiamo dire che è infinito, ma non sappiamo dire se è un I.I.R.F
10 - In quali casi A si riduce ad A segnato?
- Certamente non quando è vuoto o Infinito, ma se A si riduce ad A segnato allora A segnato si riduce ad A, e questo
può avvenire se e solo se entrambi gli insiemi sono ricorsivi
11 - Proprietà dell'insieme I = {x | Esiste y t.c Phi_x(y) converge <=> Phi_x+2y converge}
-Se è RE dipende dal'enumerazione, non è vuoto e per il teorema del punto fisso possiamo dire che è infinito, non
sappiamo se è un I.I.R.F
12 - Co-NP è sinonimo di NP?
-No, ma coincidono
Ricevimento 26/10/2020
Torna a “[ECC] Elementi di calcolabili e complessità”
Vai a
- Generale
- ↳ Discussioni
- ↳ Discussions (in english)
- ↳ I rappresentanti rispondono
- ↳ Parliamone
- ↳ Mercatino
- ↳ Tirocini
- ↳ Annunci
- ↳ Announcements (in english)
- ↳ Eventi
- I anno
- ↳ Algebra Lineare
- ↳ Analisi Matematica
- ↳ Fondamenti dell'Informatica
- ↳ Laboratorio I
- ↳ Programmazione e Algoritmica
- II anno
- ↳ Architetture e Sistemi Operativi
- ↳ Calcolo Numerico
- ↳ Calcolo Numerico - Vecchio Ordinamento
- ↳ Laboratorio II
- ↳ Paradigmi di Programmazione
- ↳ Ricerca Operativa
- ↳ Ricerca Operativa - Vecchio Ordinamento
- ↳ Statistica
- ↳ Statistica - Vecchio Ordinamento
- III anno
- ↳ Basi di Dati
- ↳ Basi di Dati - Vecchio Ordinamento
- ↳ Introduzione all'Intelligenza Artificiale
- ↳ Introduzione all'Intelligenza Artificiale - Vecchio Ordinamento
- ↳ Ingegneria del Software
- ↳ Ingegneria del Software - Vecchio Ordinamento
- ↳ Reti e Laboratorio III
- Complementari
- ↳ Algebra
- ↳ Cloud Computing
- ↳ Cloud e Green Computing
- ↳ Computer Grafica
- ↳ Crittografia
- ↳ Elementi di Calcolabilità e Complessità
- ↳ Elementi di Calcolabilità e Complessità - Vecchio Ordinamento
- ↳ Esperienze di programmazione
- ↳ Fisica
- ↳ Fisica - Vecchio Ordinamento
- ↳ Gestione di Reti
- ↳ Green Computing
- ↳ Interazione Uomo-Macchina
- ↳ Laboratorio di Basi di Dati
- ↳ Laboratorio di Web Scraping
- ↳ Sicurezza di Sistemi ICT
- ↳ Sviluppo di Applicazioni Mobili
- ↳ Sviluppo di Applicazioni Web
- ↳ Teoria dell'Informazione
- Vecchio Ordinamento
- ↳ I anno
- ↳ [ALL] Algoritmica e Laboratorio
- ↳ [AM] Analisi matematica
- ↳ [FIS] Fisica
- ↳ [LPP] Logica per la programmazione
- ↳ [MDAL] Matematica discreta e algebra lineare
- ↳ [PRL] Programmazione I e laboratorio
- ↳ II anno
- ↳ [AE] Architettura degli elaboratori
- ↳ [BD] Basi di dati
- ↳ [CPS] Calcolo delle probabilità e statistica
- ↳ [CN] Calcolo numerico
- ↳ [IS] Ingegneria del software
- ↳ [PR2] Programmazione II
- ↳ [RO] Ricerca Operativa
- ↳ [SOL] Sistemi operativi e laboratorio
- ↳ III anno
- ↳ [ECC] Elementi di calcolabili e complessità
- ↳ [PI] Programmazione di interfacce
- ↳ [IIA] Introduzione all'intelligenza artificiale
- ↳ [RCL] Reti di calcolatori e laboratorio
- ↳ Advanced databases
- ↳ Advanced programming
- ↳ Advanced software engineering
- ↳ Algorithm design
- ↳ Algorithm engineering
- ↳ Artificial intelligence fundamentals
- ↳ Bioinformatics
- ↳ Competitive programming and contests
- ↳ Computational mathematics for learning and data analysis
- ↳ Data mining
- ↳ Human language technologies
- ↳ ICT infrastructures
- ↳ ICT risk assessment
- ↳ Information Retrieval
- ↳ Intelligent Systems for pattern recognition
- ↳ Laboratory for innovative software
- ↳ Languages, compilers and interpreters
- ↳ Machine learning
- ↳ Mobile and cyber-physical systems
- ↳ Parallel and distributed systems: paradigms and models
- ↳ Peer to peer systems and blockchains
- ↳ Principles for software composition
- ↳ Smart applications
- ↳ Software validation and verification
- Links
- ↳ HomePage Dipartimento
- ↳ Portale Esami