cerca
Informatica Teorica - Macchina di Turing
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.IT-MacchinaDiTuring History

Hide minor edits - Show changes to output

June 24, 2010, at 10:01 PM by ido - aggiunte informazioni storiche utilizzime
Added lines 21-22:

La MdT come modello di calcolo è stato introdotta nel 1936 da Alan Turing per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica.
Changed line 127 from:
Ciò che dobbiamo fare è riuscire a convertire una MdT multinastro M nell'equivalente a singolo nastro S. L'idea è copiare il contenuto dei ''k'' nastri di M sull'unico nastro di S, e separarli da un carattere delimitatore, ad esempio il #. Per quanto riguarda invece le testine di M, possiamo mettere un pallino sopra ogni carattere in S corrispondente. Nel nostro caso useremo il simbolo °; ad esempio nella stringa w'_1_'w°'_2_'w_'3_' la testina "virtuale" è sul carattere w'_2_'.\\
to:
Ciò che dobbiamo fare è riuscire a convertire una MdT multinastro M nell'equivalente a singolo nastro S. L'idea è copiare il contenuto dei ''k'' nastri di M sull'unico nastro di S, e separarli da un carattere delimitatore, ad esempio il #. Per quanto riguarda invece le testine di M, possiamo mettere un pallino sopra ogni carattere in S corrispondente. Nel nostro caso useremo il simbolo °; ad esempio nella stringa w'_1_'w°'_2_'w'_3_' la testina "virtuale" è sul carattere w'_2_'.\\
Changed lines 82-83 from:
Durante la computazione, M continua a modificare lo stato corrente, il contenuto del nastro e la posizione della testina. I valori assunti da questi tre elementi ad ogni passo prendono il nome di '''configurazione''' della MdT. Le configurazioni possono essere rappresentate in una forma molto semplice, che presentiamo con un esempio: 010001q'_3_'01011, significa che il contenuto del nastro è 01000101011, che lo stato corrente è q'_3_', e che la testina si trova sul carattere all'immediata destra dello stato, ovvero sul quinto 0.\\
Si dice che una configurazione C'_1_' produce una configurazione C'_2_' se la MdT può passare legalmente da C'_1_' a C'_2_' in un unico passo.\\
to:
Durante la computazione, M continua a modificare lo stato corrente, il contenuto del nastro e la posizione della testina. I valori assunti da questi tre elementi ad ogni passo prendono il nome di '''configurazione''' della MdT. Le configurazioni possono essere rappresentate in una forma molto semplice, che spieghiamo con un esempio: 010001q'_3_'01011, significa che il contenuto del nastro è 01000101011, che lo stato corrente è q'_3_', e che la testina si trova sul carattere all'immediata destra dello stato, ovvero sul quinto 0.\\
Si dice che una configurazione C'_1_' '''produce''' una configurazione C'_2_' se la MdT può passare legalmente da C'_1_' a C'_2_' in un unico passo.\\
Changed line 89 from:
Tutte queste definizioni ci servivano per dire che M accetta l'ingresso ''w'' se esiste una sequenza di configurazioni C'_1_', ... C'_k_' tali che:
to:
Tutte queste definizioni ci servivano per dire che M accetta l'ingresso ''w'' se esiste una sequenza di configurazioni C'_1_', ... , C'_k_' tali che:
Changed lines 101-102 from:
Una MdT può accettare, rifiutare o andare in loop su un certo ingresso, dove per loop si intende quel comportamento per cui non si arriva mai a uno stato di terminazione. Dato che è difficile sapere se la fase di loop è temporanea o definitiva, spesso alle MdT generiche si preferisce una variante chiamata '''decisori''', che arrivano sempre a una decisione finale: la stringa è accettata oppure no. Se un decisore riconosce un certo linguaggio, si può dire anche che lo ''decide''.
to:
Una MdT può accettare, rifiutare o andare in loop su un certo ingresso, dove per loop si intende quel comportamento per cui non si arriva mai a uno stato di terminazione. Dato che è difficile sapere se la fase di loop è temporanea o definitiva, spesso alle MdT generiche si preferisce una variante chiamata '''decisori''', che arrivano sempre a una decisione finale (la stringa è accettata oppure no). Se un decisore riconosce un certo linguaggio, si può dire anche che lo ''decide''.
Changed lines 115-117 from:
'''δ: Q × Γ'^k^' → Q × Γ'^k^ × {L,R,S}'^k^''''\\
, dove gli indici k permettono di compiere più operazioni su k nastri contemporaneamente, mentre l'aggiunta del simbolo S indica che la testina può muoversi a sinistra (L), a destra (R) o stare ferma (S, stay).
to:
'''δ: Q × Γ'^k^' → Q × Γ'^k^' × {L,R,S}'^k^''''\\
, dove gli indici k permettono di compiere più operazioni su k nastri contemporaneamente, mentre l'aggiunta del simbolo S indica che la testina può muoversi a sinistra (L), a destra (R) o stare ferma (S, ''Stay'').
Changed line 127 from:
Ciò che dobbiamo fare è riuscire a convertire una MdT multinastro M nell'equivalente a singolo nastro S. L'idea è copiare il contenuto dei ''k'' nastri di M sull'unico nastro di S, e separarli da un carattere delimitatore, ad esempio il #. Per quanto riguarda invece le testine di M, possiamo mettere un pallino sopra ogni carattere in S corrispondente. Nel nostro caso useremo il simbolo °; ad esempio nella stringa w'_1_'w°'_2_'w_'3_' la testina "virtuale" è sul carattere di mezzo.\\
to:
Ciò che dobbiamo fare è riuscire a convertire una MdT multinastro M nell'equivalente a singolo nastro S. L'idea è copiare il contenuto dei ''k'' nastri di M sull'unico nastro di S, e separarli da un carattere delimitatore, ad esempio il #. Per quanto riguarda invece le testine di M, possiamo mettere un pallino sopra ogni carattere in S corrispondente. Nel nostro caso useremo il simbolo °; ad esempio nella stringa w'_1_'w°'_2_'w_'3_' la testina "virtuale" è sul carattere w'_2_'.\\
Changed lines 151-152 from:
Sempre più facile: dato che per il Teorema 1 ogni MdT multinastro ha una equivalente MdT a singolo nastro, e che un linguaggio è Turing-riconoscibile se esiste una MdT (a singolo nastro) che lo riconosce, anche la seconda implicazione è banalmente risolta.
to:
Dato che per il Teorema 1 ogni MdT multinastro ha una equivalente MdT a singolo nastro, e che un linguaggio è Turing-riconoscibile se esiste una MdT (a singolo nastro) che lo riconosce, anche la seconda implicazione è banalmente risolta.
Changed lines 165-166 from:
Come sappiamo, la computazione di N può essere vista come un albero, in cui ogni ramo rappresenta un ramo del nondeterminismo, ed ogni nodo una configurazione di N (ad esempio, la radice è quella di partenza). D dovrà quindi esplorare quest'albero alla ricerca di una configurazione di accettazione. Ocio però, non conviene fare un'esplorazione per profondità (dalla radice alla foglia, e poi ancora su) perché potrei incappare in un ramo infinito e non uscirne mai più (è il nondeterminismo, bellezza!). La strategia giusta è quella in larghezza, in cui prima controllo tutti i nodi sullo stesso livello, poi passo a quello più in basso.
to:
Come sappiamo, la computazione di N può essere vista come un albero, in cui ogni ramo rappresenta un ramo del nondeterminismo ed ogni nodo una configurazione di N (ad esempio, la radice è quella di partenza). D dovrà quindi esplorare l'albero alla ricerca di una configurazione di accettazione. Ocio però: non conviene fare un'esplorazione per profondità (dalla radice alla foglia, e poi ancora su) perché potrei incappare in un ramo infinito e non uscirne mai più (è il nondeterminismo, bellezza!). La strategia giusta è quella in larghezza, in cui prima controllo tutti i nodi sullo stesso livello, poi passo a quello più in basso.
Changed line 168 from:
Per semplificarci la vita, costruiamo D come una MdT a 3 nastri (tanto il Teorema 1 ci dice che possiamo sempre convertirla in una a singolo nastro), ognuno dei quali ha un proprio ruolo:
to:
Costruiamo D come una MdT a 3 nastri (tanto il Teorema 1 ci dice che possiamo sempre convertirla in una a singolo nastro), ognuno dei quali ha un proprio ruolo:
Changed line 184 from:
# sostituisci la stringa sul terzo nastro con quella successiva. Simula il prossimo ramo di computazione di N tornando al passo 2.
to:
# sostituisci la stringa sul terzo nastro con quella successiva. Simula il prossimo ramo di computazione di N tornando al passo 2."
Added lines 1-204:
(:title Informatica Teorica - Macchina di Turing :)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----

%titolo%''':: Informatica Teorica - Macchina di Turing ::'''

%center% %sottotitolo% Appunti & Dimostrazioni del 21 Aprile

!!Concetti iniziali
La '''Macchina di Turing''' (da ora, [@MdT@]) è un modello per calcolatore general purpose. Si tratta di un modello molto potente, molto più di tutti quelli visti finora, ed è in grado di fare tutto ciò che un computer reale può fare, quindi risolvere problemi che si trovano entro il limite della calcolabilità.\\
Vediamo le caratteristiche:
* usa un nastro infinito come memoria illimitata;
* ha una testina che può leggere e scrivere simboli sulle celle del nastro;
* la testina può muoversi lungo il nastro sia a sinistra che a destra;
* a inizio computazione il nastro contiene solo la stringa d'ingresso, mentre tutte le altre celle sono bianche;
* la computazione continua (all'infinito) finché non produce in uscita un ''accetta'' o un ''rifiuta'', che si riferiscono rispettivamente agli stati di accettazione o rifiuto designati.

Lo schema di una possibile MdT è il seguente:

%center%Attach:IT-esMdT.gif

!!Esempio 1
Dobbiamo creare una MdT M che verifichi l'appartenenza di una stringa al linguaggio:\\
''B = {w#w | w ∈ {0,1}* }''

In pratica M dovrà accettare stringhe binarie composte da due sottostringhe identiche separate dal simbolo #, e rifiutare tutte le altre. Come fare? Memorizzare tutti i caratteri di una sottostringa e confrontarli con la seconda sarebbe folle, perché possono essere di lunghezza spropositata. La soluzione è far spostare avanti e indietro la testina lungo il nastro per confrontare i caratteri delle due sottostringhe che si trovano alla stessa posizione, e se questi corrispondono ci mettiamo un bel marcatore per ricordarci che li abbiamo già esaminati.\\
Questa descrizione non ci basta, ne vogliamo una non troppo formale ma sicuramente più precisa:

>>left bgcolor=#fbf3ff width=auto border='2px solid #cccccc' padding=5px<<
M = "su ingresso ''w'':
# vai avanti e indietro lungo il nastro tra le posizioni corrispondenti delle sottostringhe separate dal simbolo #, e verifica se queste posizioni contengono lo stesso simbolo. In caso negativo, o se non si trova nessun simbolo #, RIFIUTA; altrimenti se i simboli corrispondono sostituiscili col simbolo [@x@];
# quando tutti i simboli a sinistra del # sono stati sostituiti con la [@x@], controlla se ne rimangono altri non segnati a destra. Se sì, allora RIFIUTA; altrimenti ACCETTA."
>><<

Vediamo un esempio di esecuzione (la [@v@] sopra un carattere indica la posizione della testina):

[@
v
0 1 1 0 # 0 1 1 0 _ ...

v
x 1 1 0 # 0 1 1 0 _ ...

v
x 1 1 0 # x 1 1 0 _ ...

v
x 1 1 0 # x 1 1 0 _ ...

v
x x 1 0 # x 1 1 0 _ ...

...

v
x x x x # x x x x _ ...

accetta!@]

!!Definizione formale
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Una '''MdT''' è una 7-upla (Q,&#931;,&#915;,&#948;,q'_0_',q'_accetta_',q'_rifiuta_'), dove:
* Q è l'insieme degli stati
* &#931; è l'alfabeto dei simboli in ingresso, che non contiene il simbolo ''blank'' |_|
* &#915; è l'alfabeto del nastro, dove ''|_| &#8712; &#915;'' e ''&#931; &#8838; &#915;''
* &#948;: Q × &#915; &#8594; Q × &#915; × {L,R} è la funzione di transizione
* q'_0_' &#8712; Q è lo stato iniziale
* q'_accetta_' &#8712; Q è lo stato accettante
* q'_rifiuta_' &#8712; Q è lo stato rifiutante, dove q'_accetta_'&#8800;q'_rifiuta_'
>><<

La funzione di transizione &#948; in pratica dice che quando la macchina si trova in uno stato ''q'' e la testina è su una cella che contiene il simbolo ''b'', sostituisce quest'ultimo col simbolo ''a'' e si sposta nello stato ''r''. Lo spostamento è verso sinistra se il terzo componente della funzione di transizione è [@L@]; mentre se è [@R@] si sposta verso destra. Riassumendo il tutto, spostandoci ad esempio a sinistra: ''&#948;(q,a)=(r,b,L)''.

!!Funzionamento della MdT
Siano dati:
* una MdT M=(Q,&#931;,&#915;,&#948;,q'_0_',q'_accetta_',q'_rifiuta_')
* una stringa di ingresso ''w'' tale che ''w = w'_1_'w'_2_'..w'_n_''', dove ogni w'_i_' fa parte dell'alfabeto &#931;*

Inizialmente ''w'' occupa le prime ''n'' celle a sinistra del nastro, e la testina si trova sulla prima cella a sinistra. Poiché l'alfabeto &#931; non contiene il simbolo ''blank'', il primo |_| che appare sul nastro coincide con la fine dell'ingresso.\\
Una volta che M è partita, la computazione procede in accordo alle regole descritte dalla funzione di transizione. Si noti che se ci viene chiesto di spostarci a sinistra del limite sinistro del nastro, rimaniamo fermi sulla prima cella senza sforare. La computazione continua fino a quando non si arriva a un q'_accetta_' o un q'_rifiuta_', nel qual caso la MdT termina; altrimenti va avanti all'infinito.

Durante la computazione, M continua a modificare lo stato corrente, il contenuto del nastro e la posizione della testina. I valori assunti da questi tre elementi ad ogni passo prendono il nome di '''configurazione''' della MdT. Le configurazioni possono essere rappresentate in una forma molto semplice, che presentiamo con un esempio: 010001q'_3_'01011, significa che il contenuto del nastro è 01000101011, che lo stato corrente è q'_3_', e che la testina si trova sul carattere all'immediata destra dello stato, ovvero sul quinto 0.\\
Si dice che una configurazione C'_1_' produce una configurazione C'_2_' se la MdT può passare legalmente da C'_1_' a C'_2_' in un unico passo.\\
Alcune configurazioni importanti di M sono:
* configurazione di partenza, ovvero ''q'_0_'w'';
* configurazione di accettazione, in cui lo stato corrente è q'_accetta_';
* configurazione di rifiuto, in cui lo stato corrente è q'_rifiuta_'.

Tutte queste definizioni ci servivano per dire che M accetta l'ingresso ''w'' se esiste una sequenza di configurazioni C'_1_', ... C'_k_' tali che:
# C'_1_' è la configurazione di partenza di M sull'ingresso ''w'';
# ogni C'_i_' produce C'_i+1_';
# C'_k_' è la configurazione di accettazione.

!!Definizioni
L'insieme di stringhe che M accetta sono chiamate '''linguaggio di M''', o ''linguaggio riconosciuto da M'', scritto anche ''L(M)''.

>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Chiamiamo un linguaggio '''Turing-riconoscibile''' se esiste una MdT che lo riconosce.
>><<

Una MdT può accettare, rifiutare o andare in loop su un certo ingresso, dove per loop si intende quel comportamento per cui non si arriva mai a uno stato di terminazione. Dato che è difficile sapere se la fase di loop è temporanea o definitiva, spesso alle MdT generiche si preferisce una variante chiamata '''decisori''', che arrivano sempre a una decisione finale: la stringa è accettata oppure no. Se un decisore riconosce un certo linguaggio, si può dire anche che lo ''decide''.

>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Chiamiamo un linguaggio '''Turing-decidibile''' o semplicemente '''decidibile''' se esiste una MdT che lo decide.
>><<

!!Varianti
Della MdT vedremo due varianti molto importanti: la MdT multinastro e quella [@n.d.@]. Si noti che ognuna di esse ha le stesse potenzialità dato che riconosce gli stessi linguaggi delle altre (sono quindi equivalenti); questa proprietà è detta '''robustezza'''.

!!!MdT multinastro
Una '''MdT multinastro''' si differenzia da quelle "standard" per le seguenti caratteristiche:
* ha più nastri, ognuno con la propria testina per leggere e scrivere;
* inizialmente la stringa d'ingresso si trova solo sul primo nastro, mentre tutti gli altri sono inizializzati coi simboli ''blank'' (quindi sono considerati vuoti);
* la funzione di transizione cambia nella forma:\\
'''&#948;: Q × &#915;'^k^' &#8594; Q × &#915;'^k^ × {L,R,S}'^k^''''\\
, dove gli indici k permettono di compiere più operazioni su k nastri contemporaneamente, mentre l'aggiunta del simbolo S indica che la testina può muoversi a sinistra (L), a destra (R) o stare ferma (S, stay).

Come dicevamo, e contrariamente a quanto possa sembrare, la MdT multinastro è equivalente a quella a nastro singolo, e per convincervi scomodiamo un teorema.

!!!!Teorema 1 - sulle MdT multinastro
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Ogni MdT multinastro ha una equivalente MdT a singolo nastro.
>><<

'''Dimostrazione'''

Ciò che dobbiamo fare è riuscire a convertire una MdT multinastro M nell'equivalente a singolo nastro S. L'idea è copiare il contenuto dei ''k'' nastri di M sull'unico nastro di S, e separarli da un carattere delimitatore, ad esempio il #. Per quanto riguarda invece le testine di M, possiamo mettere un pallino sopra ogni carattere in S corrispondente. Nel nostro caso useremo il simbolo °; ad esempio nella stringa w'_1_'w°'_2_'w_'3_' la testina "virtuale" è sul carattere di mezzo.\\
Proviamo a dare una descrizione più completa dell'algoritmo di conversione, che tenga conto anche di casi critici come lo spostamento su un simbolo #.

>>left bgcolor=#fbf3ff width=auto border='2px solid #cccccc' padding=5px<<
S = "su ingresso ''w = w'_1_'...w'_n_''':
# scrivi sul nastro la configurazione iniziale di M nel formato corretto:\\
#w°'_1_'w'_2_'...w'_n_'#|_|°#|_|°#...#
# per simulare una singola mossa: ''(a)'' fai uno scan del nastro partendo dal primo # (limite sinistro) al (k+1)simo # (limite destro), così da capire dove sono posizionate le testine virtuali; ''(b)'' fai un secondo scan per aggiornare il nastro in accordo alle funzioni di transizione di M
# se, applicando le funzioni di transizione di M, la testina di S si sposta a destra di un #, significa che in M si sarebbe finiti su una cella ''blank''. Quindi, S deve scrivere un simbolo ''blank'' in quella cella e shiftare a destra di una posizione tutti i caratteri rimanenti del nastro. Fatto questo, può continuare la simulazione."
>><<

!!!!Corollario al Teorema 1
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un linguaggio è Turing-riconoscibile se e solo se esiste una MdT multinastro che lo riconosce.
>><<

'''Dimostrazione'''

Il teorema è un "se e solo se", quindi vanno dimostrati entrambi i sensi delle implicazioni.

'''(I)''' ''Se un linguaggio è Turing-riconoscibile, allora esiste una MdT multinastro che lo riconosce''\\
Dato che un linguaggio è Turing-riconoscibile se esiste una MdT a singolo nastro che lo riconosce, e che questa è un caso particolare di una MdT multinastro (dove il numero di nastri k=1), l'implicazione è banalmente risolta.

'''(II)''' ''Se un linguaggio è riconosciuto da una MdT multinastro, allora è Turing-riconoscibile''\\
Sempre più facile: dato che per il Teorema 1 ogni MdT multinastro ha una equivalente MdT a singolo nastro, e che un linguaggio è Turing-riconoscibile se esiste una MdT (a singolo nastro) che lo riconosce, anche la seconda implicazione è banalmente risolta.

!!!MdT non deterministica
Una '''MdT non deterministica''' può procedere ad ogni punto della computazione secondo diverse possibilità. La funzione di transizione assumerà dunque la nuova forma:\\
'''&#948;: Q × &#915; &#8594; P(Q × &#915; × {L,R,S})'''

!!!!Teorema 2 - sulle MdT non deterministiche
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Ogni MdT [@n.d.@] ha una equivalente MdT deterministica.
>><<

'''Dimostrazione'''

Dobbiamo dimostrare che è possibile simulare una MdT [@n.d.@] N con una MdT deterministica D. L'idea è semplice: D dovrà tentare tutti i possibili rami di computazione [@n.d.@] di N, e se arriva a uno stato di accettazione, accetta.\\
Come sappiamo, la computazione di N può essere vista come un albero, in cui ogni ramo rappresenta un ramo del nondeterminismo, ed ogni nodo una configurazione di N (ad esempio, la radice è quella di partenza). D dovrà quindi esplorare quest'albero alla ricerca di una configurazione di accettazione. Ocio però, non conviene fare un'esplorazione per profondità (dalla radice alla foglia, e poi ancora su) perché potrei incappare in un ramo infinito e non uscirne mai più (è il nondeterminismo, bellezza!). La strategia giusta è quella in larghezza, in cui prima controllo tutti i nodi sullo stesso livello, poi passo a quello più in basso.

Ora che sappiamo cosa fare, cosa facciamo? :| \\
Per semplificarci la vita, costruiamo D come una MdT a 3 nastri (tanto il Teorema 1 ci dice che possiamo sempre convertirla in una a singolo nastro), ognuno dei quali ha un proprio ruolo:
# contiene la stringa d'ingresso, ed è in sola lettura;
# mantiene una copia del nastro di N su un certo ramo [@n.d.@] di computazione, su cui fa le simulazioni;
# tiene traccia della posizione di D sull'albero di computazione [@n.d.@] di N. Ad esempio la sequenza [@123@] significa che devo partire dalla radice, spostarmi sul suo primo figlio, da qui andare al suo secondo figlio, e infine da qui al suo terzo figlio.

Ecco uno schema:

%center%Attach:IT-MdT-nd2d.gif

Descriviamo D, in modo meno formale del solito:

>>left bgcolor=#fbf3ff width=auto border='2px solid #cccccc' padding=5px<<
D = "
# inizialmente abbiamo sul primo nastro l'ingresso ''w'', mentre gli altri due sono vuoti;
# copiamo il contenuto del primo nastro sul secondo;
# simuliamo sul secondo nastro il comportamento di N con ingresso ''w'' su un certo ramo di computazione [@n.d.@]. Prima di ogni passo di N dobbiamo consultare il prossimo simbolo sul terzo nastro, così da capire quale scelta dobbiamo fare tra quelle consentite dalla funzione di transizione di N. Se non ci sono più simboli sul terzo nastro, o quella scelta non è valida, usciamo da questo ramo di computazione e andiamo al passo 4. Stessa cosa se troviamo una configurazione di rifiuto. Se invece troviamo una configurazione di accettazione, D ACCETTA l'ingresso;
# sostituisci la stringa sul terzo nastro con quella successiva. Simula il prossimo ramo di computazione di N tornando al passo 2.
>><<


!!!!Corollario al Teorema 2
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un linguaggio è Turing-riconoscibile se e solo se esiste una MdT [@n.d.@] che lo riconosce.
>><<

'''Dimostrazione'''

Il teorema è un "se e solo se", quindi vanno dimostrati entrambi i sensi delle implicazioni.

'''(I)''' ''Se un linguaggio è Turing-riconoscibile, allora esiste una MdT [@n.d.@] che lo riconosce''\\
Dato che un linguaggio è Turing-riconoscibile se esiste una MdT deterministica che lo riconosce, e che questa è un caso particolare di una MdT [@n.d.@], l'implicazione è banalmente risolta.

'''(II)''' ''Se un linguaggio è riconosciuto da una MdT [@n.d.@], allora è Turing-riconoscibile''\\
Dato che per il Teorema 2 ogni MdT [@n.d.@] ha una equivalente MdT deterministica, e che un linguaggio è Turing-riconoscibile se esiste una MdT deterministica che lo riconosce, anche la seconda implicazione è banalmente risolta.

----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]