andreRondo
Ciao a tutti, che differenza c'è tra l'insieme infinito di indici Ax di mdT che calcolano tutte la stessa funzione (Paddling lemma) e l'insieme A (nella definizione di i.i.r.f.) che è anch'esso un insieme di indici che calcolano tutte la stessa funzione?
Ho pensato alla cardinalità dei due insiemi.. Il primo è infinito. Il secondo non saprei, anche perchè grazie al teorema 1.10.19 e al teorema di Rice si può sapere se è r.e. oppure ricorsivo, e quindi la cardinalità in quei casi varia..
MindFlyer
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 insieme di indici che rispettano le funzioni. Nel padding lemma si generano alcuni indici che corrispondono alla stessa funzione (semplicemente perché si aggiungono operazioni inutili al "programma" della funzione). Ma ci sono invece molti altri indici che corrispondono alla stessa funzione ma non sono generati dal padding lemma. Perché dico questo? Perché l'insieme generato dal padding lemma è ricorsivo: tutti gli indici sono della forma "programma fissato (sempre lo stesso!) seguito da un numero qualunque di operazioni inutili". Altre varianti del padding lemma costruiscono altri insiemi, ma sono tutti ricorsivi. Però il teorema di Rice dice che l'insieme di indici di una funzione non è ricorsivo, e quindi dev'essercene qualcuno non generato dal padding lemma.
Differenza tra Ax e A i.i.r.f
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