Antonio Sisbarra
Salve a tutti,
stavo studiando la dimostrazione, abbastanza sintetizzata, del fatto che la composizione di due macchine che operano in spazio logaritmico è ancora una macchina che opera in spazio logaritmico (teorema 3.5.2).
A quanto ho capito, bisogna:
1. lanciare la seconda macchina
2. non appena ha bisogno di un carattere d'ingresso lo si fa calcolare dalla prima macchina
3. da qui in poi mi sono perso perché la dimostrazione sulle dispense parla di scrivere caratteri sulla medesima casella (quale?)
Qualcuno ha in mente qualcosa?
MindFlyer
Allora, diciamo che vuoi comporre le macchine M1 e M2 che lavorano in LOGSPACE. E le vuoi comporre rimanendo in LOGSPACE. Quindi devi far lavorare M2 dandole in input l'output di M1. Ma questo non si può fare direttamente mettendo l'output di M1 su un nastro di lavoro, perché quest'output potrebbe occupare spazio più che logaritmico. Questo è il motivo per cui bisogna fare tutto quel casino.
Ovviamente dovremo avere l'input di M1 sul nastro di input (perché questo è l'input della composizione di M1 e M2) e l'output di M2 sul nastro di output (perché questo è l'output della composizione di M1 e M2). Poi dobbiamo vedere cosa ci serve nei nastri di lavoro, ricordando che questi devono essere tutti di lunghezza logaritmica.
Nei nastri di lavoro includiamo sicuramente i nastri di lavoro di M1 e M2, che non danno problemi. Per il nastro di output di M1 (che va letto da M2) mettiamo soltanto una "testina virtuale", che è un nastro di lavoro contenente solo la posizione della testina nel nastro di output di M1. Questa testina sarebbe quella che muove M2 per andare a prendere il suo input dall'output di M1. Nota che l'output di M1 deve avere lunghezza polinomiale, e quindi la posizione della testina si può rappresentare in spazio logaritmico.
Adesso iniziamo a simulare M2. Quando ha bisogno di leggere i nastri di lavoro, nessun problema. Quando deve leggere dal nastro di input (che è l'output di M1), simuliamo M1 (usando i nastri di lavoro di M1 e il nastro di input), ma non scriviamo il suo output direttamente. Teniamo solo un nastro di lavoro extra in cui mettiamo la posizione della testina di output del simulatore di M1. Quando questa testina coincide con la testina virtuale dell'input di M2, prendiamo il prossimo simbolo di output scritto da M1, e lo facciamo leggere a M2. E avanti così. Questo era sostanzialmente il senso.
Quando diceva "scrivendo i caratteri via via calcolati sulla medesima casella" intendeva quest'ultima cosa, ovvero che non si sposta mai la testina di output di M1, ma si continua a scrivere il suo output su un'unica casella, fin quando si raggiunge la posizione richiesta da M2. In realtà non c'è bisogno di scrivere esplicitamente gli output precedenti sovrascrivendo poi quelli nuovi, ma basta scrivere una volta sola il simbolo giusto.
Spero che sia chiaro...
Agli esami fa spesso queste domandine di comprensione, chiedendo di tappare i buchi delle sue dispense.
Dimostrare che l'insieme LOGSPACE è chiuso per composizione
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