PDA

Visualizza la versione completa : [Calcolabilita']


uncool_drewl
10-09-2008, 12:15
Salve ragazzi volevo porre una domanda di informatica teorica,io ho una coppia di stringhe (w1;w2) che codificano due macchine di Turing M1 ed M2 per le quali e' noto che M2 termina in tempo finito per qualunque suo input, e' vero che
L(M1) "Linguaggio riconosciuto dalla macchina M1" e' incluso in L(M2) "Linguaggio riconosciuto dalla macchina M2" ?
In particolare:
Il problema appartiene ad RE?
Ed il suo problema complementare?
Cosa cambierebbe se sapessimo che anche M1 termina in tempo finito per ogni suo input?

Per come intendo io il problema,se L(M1) e' un linguaggio infinito chiaramente non possiamo andare a controllare che tutte le sue stringhe siano anche presenti in L(M2) "in tempo finito",detto questo dire se un insieme di stringhe (linguaggio) appartiene ad un altro linguaggio per il teorema di rice e' indecidibile e da cio' posso concludere che non e' in R. Il problema per me sta nel capire se appartiene ad RE,bisognerebbe fare una riduzione da questo problema al linguaggio universale oppure al linguaggio Lne ma a me al momento non viene in mente,d'altra parte lavorando sul problema negato se riuscissi a dimostrare che il negato appartiene ad RE automaticamente questo problema non apparterrebbe ad RE dal momento che abbiamo detto che il problema non appartiene ad R. Qualcuno ha delle idee su come procedere? grazie mille.

Loading