|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-Riducibilità History
Hide minor edits - Show changes to output
Changed lines 41-43 from:
*''R'' decisore per ''E'_TM_''
*''S'' decisore per '''A'_TM_''' to:
*''R'' decisore per ''E'_TM_'''
*''S'' decisore per ''A'_TM_''' Changed lines 48-49 from:
#se x = w → esegui ''M'' su ''w'' e accetta se ''M'' accetta to:
#se x = w → esegui ''M'' su ''w'' e accetta se ''M'' accetta." Changed lines 56-57 from:
altrimenti → accetta (''L(M'_1_')'' non vuoto quindi ''M'' riconosce ''w'') to:
altrimenti → accetta (''L(M'_1_')'' non vuoto quindi ''M'' riconosce ''w'')." Changed line 76 from:
altrimenti → rifiuta (''L(M) ≠ L(M'_1_')'' quindi il linguaggio riconosciuto da ''M'' non è vuoto) to:
altrimenti → rifiuta (''L(M) ≠ L(M'_1_')'' quindi il linguaggio riconosciuto da ''M'' non è vuoto)."
Changed line 124 from:
!!!Decidibilità di ''E'_LBA_''' to:
!!!Non decidibilità di ''E'_LBA_'''
Added lines 108-109:
!!!Decidibilità di ''A'_LBA_''' Changed line 117 from:
#se ''M'' termina e accetta → accetta// to:
#se ''M'' termina e accetta → accetta\\ Added lines 122-146:
>><<
!!!Decidibilità di ''E'_LBA_'''
Mentre è decidibile ''A'_LBA_''', non è invece decidibile ''E'_LBA_''', ovvero il problema che consiste nel dire se un LBA non accetta alcuna stringa. È possibile dimostrarlo tramite riduzione:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
%center%''E'_LBA_' = {<M> | M è un LBA e L(M)=0}''
Supponiamo che il decisore per ''E'_LBA_''' esista e proviamo a ridurre un problema noto a ''E'_LBA_''':\\
riduciamo ''A'_TM_''' a ''E'_LBA_''':
*''R'' decisore per ''E'_LBA_'''
*''S'' decisore per ''A'_TM_'''
Per effettuare la riduzione definiamo l'LBA ''B'' tale che ''L(B)={CH accettanti per una data MdT ''M'' e un dato ingresso ''w''}''. L'ingresso per ''B'' è una sequenza di configurazioni e per verificare che la sequenza sia una CH accettante devono essere verificate le condizioni già descritte in precedenza.
Se ''L(B) = 0'' vuol dire che non esistono CH che consentono a ''M'' di accettare ''w'' e quindi ''A'_TM_''' dovrà rifiutare. Viceversa se il linguaggio di B non è vuoto allora ''M'' accetta ''w''.
Costruiamo il decisore ''S'' che decide ''A'_TM_''':
''S'' = su ingresso ''<M, w>''
#costruisci LBA ''B'' da ''M'' e ''w''
#esegui ''R'' su ingresso ''<B>''
#se ''R'' accetta → rifiuta (''L(B)'' vuoto → ''M'' non accetta ''w'')\\
altrimenti → accetta
Quindi se esistesse un decisore per ''E'_LBA_''' potremmo ottenere un decisore per ''A'_TM_'''. Sappiamo però che non è possibile decidere ''A'_TM_''' e quindi non esiste un decisore per ''E'_LBA_'''.
Added lines 98-121:
È possibile dimostrare che un LBA possiede un numero limitato di configurazioni:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Sia ''M'' un LBA con:
*''q'' stati
*''g'' simboli di ingresso
*un nastro lungo ''n''
Il numero di configurazioni distinte possibili è ''qng'^n^'''.
>><<
Grazie a questa proprietà degli LBA è possibile dimostrare che il problema dell'accettazione di una stringa per un LBA è decidibile:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
%center%''A'_LBA_' = {<M, w> | M è un LBA che accetta w}''
Costruiamo il decisore ''L'' che decide ''A'_LBA_''':
''L'' = su ingresso ''<M, w>''
#simula ''M'' su ''w'' fino a che ''M'' termina o fino a che ha effettuato ''qng'^n^''' passi
#se ''M'' termina e accetta → accetta//
altrimenti → rifiuta (''M'' non ha accettato o è finito in loop)
La simulazione di ''M'' su ''w'' si ferma anche quando si ricade in una configurazione già vista in precedenza: questa situazione indica la presenza di un loop infinito.
La simulazione inoltre può fare al massimo ''qng'^n^''' passi: se si arriva ad aver visitato ''qng'^n^''' configurazioni distinte, il prossimo passo ci porterà in una configurazione sicuramente già vista (perché le configurazioni sono in numero limitato) e quindi in un loop.
>><<
Added lines 80-97:
!!Computation Histories (CH)
Una CH di una MdT non è altro che la sequenza di configurazioni che la macchina attraversa per elaborare un ingresso. Ogni CH è una sequenza finita di configurazioni, in quanto se la macchina di Turing non termina su un ingresso allora non esiste una CH per quel dato ingresso.
Formalmente si può definire una CH in questo modo:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Sia ''M'' una MdT e ''w'' un ingresso per ''M''. Una '''CH accettante''' per ''M'' su ''w'' è una sequenza di configurazioni ''C'_1_', C'_2_', ..., C'_l_''' dove:
*''C'_1_''' è la configurazione di partenza di ''M'' su ''w''
*''C'_l_''' è una configurazione accettante
*ogni ''C'_i_''' segue ''C'_i-1_''' secondo le regole di ''M''
Una '''CH non accettante''' è simile ad una CH accettante tranne che ''C'_l_''' è una configurazione non accettante.
>><<
Le MdT deterministiche possiedono una sola CH per un dato input, mentre le MdT non deterministiche ne possiedono molte, in corrispondenza ai possibili rami della computazione.
!!Linear Bounded Automa (LBA)
Un LBA è una MdT limitata in memoria in cui la testina non può muoversi oltre il limite destro e sinistro della stringa di input. Lo spazio di memoria utilizzabile è quindi ristretto alla lunghezza della stringa di input.
Per incrementare la memoria disponibile è possibile però aumentare l'insieme dei simboli dell'alfabeto rendendolo più ampio rispetto all'insieme dei simboli dell'alfabeto di ingresso. In questo modo si incrementa la memoria di un fattore costante, quindi la quantità di memoria disponibile è lineare rispetto alla dimensione dell'input.
Changed lines 38-39 from:
%center%''E'_TM_' = {<M> | M è una MdT e L(M)=0}'' to:
%center%''E'_TM_' = {<M> | M è una MdT e L(M) = 0}'' Deleted lines 57-58:
Added lines 59-78:
>><<
!!!Non decidibilità di ''EQ'_TM_'''
Il problema ''EQ'_TM_''' consiste nello stabilire se due macchine di Turing riconoscono lo stesso linguaggio. Questo problema non è decidibile e lo si può dimostrare utilizzando la riducibilità di ''E'_TM_''' a ''EQ'_TM_''':
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
%center%''EQ'_TM_' = {<M'_1_', M'_2_'> | M'_1_' e M'_2_' MdT t.c. L(M'_1_') = L(M'_2_')}''
Per ottenere ''S'' riduciamo il problema di decidere se un linguaggio è vuoto (''E'_TM_''') al problema di dire se una MdT riconosce lo stesso linguaggio (''EQ'_TM_''') di una MdT il cui linguaggio è vuoto:
Riduciamo ''E'_TM_''' a ''EQ'_TM_''':
*''R'' decisore per ''EQ'_TM_'''
*''S'' decisore per ''E'_TM_'''
''S'' = "su ingresso ''<M>'':
#costruisci ''M'_1_''' come la MdT t.c. ''L(M'_1_') = 0''
#esegui ''R'' su ingresso ''<M, M'_1_'>''
#se ''R'' accetta → accetta (''L(M) = L(M'_1_') = 0'')\\
altrimenti → rifiuta (''L(M) ≠ L(M'_1_')'' quindi il linguaggio riconosciuto da ''M'' non è vuoto)
Dato che ''S'' non può esistere (''E'_TM_''' non decidibile) non può esistere neanche ''R'', quindi ''EQ'_TM_''' non è decidibile (dimostrazione per contraddizione).
Added lines 33-60:
>><<
!!!Non decidibilità di ''E'_TM_'''
Il problema ''E'_TM_''' consiste nello stabilire se il linguaggio di un automa è vuoto. Questo problema non è decidibile e lo si può dimostrare sempre tramite riducibilità:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
%center%''E'_TM_' = {<M> | M è una MdT e L(M)=0}''
Come nella precedente dimostrazione riduciamo ''A'_TM_''' a ''E'_TM_''':
*''R'' decisore per ''E'_TM_''
*''S'' decisore per '''A'_TM_'''
Per la dimostrazione è necessario definire ''M'_1_''' come la MdT che rifiuta tutte le stringhe diverse da ''w'' e nel caso l'ingresso sia proprio ''w'' allora esegue ''M'' sull'ingresso:
''M'_1_''' = "su ingresso ''<x>'':
#se x ≠ w → rifiuta
#se x = w → esegui ''M'' su ''w'' e accetta se ''M'' accetta
È ora possibile definire ''S'':
''S'' = "su ingresso ''<M, w>'':
#costruisci ''M'_1_'''
#esegui ''R'' su ingresso ''<M'_1_'>''
#se ''R'' accetta → rifiuta (''L(M) = 0'' → ''M'' non riconosce nessuna stringa e quindi neanche ''w'')\\
altrimenti → accetta (''L(M'_1_')'' non vuoto quindi ''M'' riconosce ''w'')
Dato che ''S'' non può esistere (''A'_TM_''' non decidibile) non può esistere neanche ''R'', quindi ''E'_TM_''' non è decidibile (dimostrazione per contraddizione).
Added lines 1-35:
(:title Informatica Teorica - Riducibilità:)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Riducibilità ::'''
%center% %sottotitolo% Appunti del 28 Aprile
!!Riducibilità
La riducibilità è un metodo per convertire l'istanza di un problema ''A'' in un'istanza di un problema ''B'' e utilizzare la soluzione di quest'ultimo per ottenere la soluzione di ''A''. La riducibilità è anche uno dei metodi principali per dimostrare che un problema non è computazionalmente decidibile.
Quando ''A'' è riducibile a ''B'' allora:
*risolvere ''A'' non può essere più difficile di risolvere ''B''
*risolvere ''B'' ci permette di ottenere la soluzione di ''A''
*se ''B'' è decidibile allora lo è anche ''A''
*se ''A'' non è decidibile allora anche ''B'' non è decidibile
!!!Non decidibilità di ''HALT'_TM_'''
Tramite riducibilità è possibile dimostrare che il problema ''HALT'_TM_''', ovvero il problema della terminazione di una macchina di turing su un dato ingresso, non è decidibile:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
%center%''HALT'_TM_' = {<M, w> | M è una MdT e M termina sull'ingresso w}''
Supponiamo che esista una MdT ''R'' che decide il nostro problema e proviamo a descrivere la MdT ''S'' che decide ''A'_TM_''' riducendo il problema di accettazione al nostro problema di terminazione ''HALT'_TM_''':
''S'' = "su ingresso ''<M, w>'':
#esegui ''R'' su ingresso ''<M, w>''
#se ''R'' rifiuta → rifiuta (''M'' non termina sull'ingresso ''w'')
#se ''R'' accetta (''M'' non va in loop) simula ''M'' su ingresso ''w''
#se ''M'' accetta → accetta\\
altrimenti → rifiuta
Abbiamo dimostrato che se esistesse ''R'' allora saremmo in grado di costruire anche ''S'', ma sappiamo che il problema ''A'_TM_''' non è decidibile e che quindi ''S'' non può esistere, quindi non esiste nemmeno ''R'' (dimostrazione per contraddizione).
>><<
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
