Antonio Sisbarra
Nella prima parte della dimostrazione del teorema di Enumerazione si dice che la funzione U, definita nel teorema di forma Normale, è anch'essa una funzione calcolabile in due argomenti: i e x.
Come mai la y non fa parte degli argomenti della funzione che poi servirà nella dimostrazione del teorema di Enumerazione?
MindFlyer
y non è una variabile libera perché è legata all'operatore di minimizzazione. Quindi ovviamente non è un parametro della funzione. Ripassa il teorema di forma normale...
Tra l'altro, per dimostrare questa versione del teorema di enumerazione non serve nemmeno passare per il teorema di forma normale, ma basta semplicemente la macchina di Turing universale.
EDIT. Ah, mi sono accorto che Degano costruisce la MdT universale dopo aver dimostrato i teoremi di forma normale e di enumerazione. Quindi in quel punto non la può usare. Scelta forse poco ortodossa, ma tant'è. Anche perché nel "dimostrare" il teorema di forma normale si appoggia alla tesi di Church-Turing (insomma, non lo dimostra davvero), il che inficia anche il teorema di enumerazione. Mentre potrebbe risparmiarsi questo giro contorto semplicemente anticipando la costruzione della MdT universale... In definitiva, trattasi dell'ennesima deganata.
Passaggio nella dimostrazione del Teorema di Enumerazione
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