Dimostrare che l'insieme LOGSPACE è chiuso per composizione

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

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.
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”