Anche se abbiamo già dimostrato il teorema, diamo qualche altro dettaglio implementativo. Anzitutto B non è altro che la quintupla che definisce un DFA, e quindi ''Q, Σ, δ, q'_0_', F''. Quindi M come prima cosa verificherà che B sia effettivamente un DFA (altrimenti RIFIUTA subito), quindi simulerà la stringa w direttamente su di lui. Come? Scrivendo ad ogni passo sul nastro lo stato e la posizione corrente di B sull'ingresso w, che sarà inizialmente q'_0_' e dovrà rispettare ad ogni step la funzione di transizione δ. Quando M arriverà a processare l'ultimo simbolo di w, dovrà verificare se è arrivato in uno degli stati finali accettati dal DFA, e accettare o rifiutare la stringa d'ingresso di conseguenza.

Verificare che un DFA non accetti nessuna stringa significa dimostrare che il suo linguaggio è vuoto, ovvero che nessuna stringa gli appartiene. Viceversa, si ricorda che un DFA accetta una stringa se e solo se è possibile raggiungere uno stato finale utilizzando le sue funzioni di transizione.

Per la dimostrazione si procederà a definire un terzo automa a stati finiti C che accetti le stringhe di A o quelle di B, ma non entrambe. Per realizzarlo si potranno usare solo le operazioni di intersezione, unione o complemento, perché sono chiuse rispetto ai linguaggi regolari. In particolare si utilizzerà la formula della ''differenza simmetrica'':

Metterci a fare tutte le derivazioni di G per vedere se una di queste è una derivazione di w sarebbe folle, perché nel caso in cui non fosse vero potremmo andare avanti all'infinito. L'alternativa è usare la grammatica G in forma normale di Chomsky, perché in questo caso le derivazioni di w sarebbero solo 2n-1 (dove n è la lunghezza della stringa), e avremmo la garanzia di trovare una soluzione in un numero finito di passi.\\

Come prima cosa dovremo scorrere la CFG e marcare tutti i terminali. Successivamente si passa a scansionare le regole, e se da una di queste risulta che una variabile può essere sostituita da terminali marcati, marchiamo anche lei. L'operazione va ripetuta marcando tutte le variabili ottenute a partire da simboli (terminali/variabili) già marcati. Se si arriva a marcare anche la variabile iniziale significa che da lei posso raggiungere una sequenza composta solo da terminali, quindi la MdT R che risolve E'_CFG_' dovrà rifiutare tale eventualità.

-->3. marca ogni variabile A in cui G abbia una regola ''A->U'_1_'...U'_k_''' in cui ogni U'_1_', ... , U'_k_'
--->sia già marcato;

L'indecidibilità la dimostriamo con il '''metodo della diagonalizzazione''' scoperto dal matematico Cantor per misurare la dimensione degli insiemi infiniti. Poiché in collezioni infinite non è possibile contare gli elementi che ne fanno parte, per capire se due insiemi sono della stessa dimensione si verifica se è possibile mettere in corrispondenza gli elementi dell'uno con quelli dell'altro. Più formalmente, due insiemi infiniti A e B sono della stessa dimensione se esiste una ''corrispondenza'' f:A->B. Per corrispondenza si intende una funzione biettiva da A a B, quindi ogni elemento di A può corrispondere a un solo elemento di B, e ogni elemento di B ha un unico di elemento di A che corrisponde ad esso.

Facciamo un esempio: l'insieme N dei numeri naturali ha la stessa dimensione dell'insieme E dei numeri naturali pari? Esiste una corrispondenza f tra i due? Sì: f(n) = 2n. Quindi hanno stessa dimensione.

Anche se sembrerà di starci allontanando dall'obiettivo (dimostrare che A'_TM_' è indecidibile), dobbiamo introdurre un po' di teoremi e dimostrazioni di tipo matematico. Torneranno utilissime poi.

Trovare una corrispondenza tra i due insiemi non è banale, ma comunque possibile. Come prima cosa creiamo una matrice bidimensionale |N|x|N| e scriviamo in ogni cella (i,j) il numero razionale i/j. A questo punto creiamo una lista di numeri spostandoci sulle diagonali ed evitando le ripetizioni (ad esempio 1/1 e 2/2 sono lo stesso valore, quindi li contiamo una sola volta), secondo lo schema mostrato in figura:

Supponiamo che f(n) sia una corrispondenza tra R ed N, e costruiamoci su misura una x che appartenga ad R ma non abbia corrispondenza in N. Per capire come, partiamo da un esempio:

Questa costruzione ci dà garanzia che x sia diverso da qualsiasi elemento di R messo in corrispondenza con N (da una fantomatica f(n) che per assurdo abbiamo supposto esistesse). Dato che x sfugge alla corrispondenza pur appartenendo all'insieme dei numeri reali, R ed N non sono della stessa dimensione, e in particolare R non è contabile.

La chiave della dimostrazione è che l'insieme dei linguaggi possibili non è contabile, mentre quello delle macchine di Turing sì; dato che una MdT riconosce un solo linguaggio, alcuni linguaggi rimarranno tagliati fuori: quelli non Turing-riconoscibili. Questa spiegazione ci basterebbe se fossimo al bar a parlare di Turing-riconoscibilità, ma siccome - e per fortuna - non lo siamo dobbiamo verificare ogni affermazione.

Dato un generico alfabeto &#931;, l'insieme di tutte le stringhe &#931;'^*^' da lui definite è contabile perché è possibile fare una lista di tutte le stringhe di una certa lunghezza (che è finita). Dal momento che ogni MdT può essere codificata come una stringa <M>, anche l'insieme delle MdT è contabile.

Anche in questo caso la dimostrazione avverrà per assurdo.\\

Supponiamo di avere un decisore H del linguaggio tale che:

Mi sembra di sentirvi dire: "E in tutto questo la diagonalizzazione dove sta?".\\

->A = { 0, 1, 01, 11, 000, 010, ...}

->&#931;'^*^'= {&#949;, 0, 1, 00, 01, 10, 11, 000, 001, 010, ...}
->[@ A = { 0, 1, 01, 11, 000, 010, ...}
->X'_A_' = 0 1 1 0 1 0 1 1 0 1 ...

Per la dimostrazione usiamo come esempio quello dei numeri razionali positivi Q, così definibili:\\
''Q = {(m/n) | m,n &#8712; N}''

[@Q = {(m/n) | m,n &#8712; N}@]

Dimostriamo il teorema per assurdo, sostenendo che R è contabile e che quindi esiste una sua corrispondenza con N. Questo ci semplifica la vita, perché basterà trovare una x&#8712;R che non sia compresa nella corrispondenza per mostrare la contraddizione della tesi.\\

Sia A un qualsiasi linguaggio libero dal contesto generato dalla CFG G. Per la dimostrazione sfruttiamo la MdT S definita nel teorema di A'_CFG_', e scriviamo la macchina di Turing M'_G_' che decide A: