I problemi indecidibili visti finora parlano tutti di macchine di Turing: se si fermano, se accettano, che linguaggio riconoscono. Il problema di corrispondenza di Post (PCP) è diverso: è un rompicapo combinatorio sulle stringhe, che chiunque può capire in un minuto, e non menziona alcuna macchina. Eppure è indecidibile. Proprio per questa sua natura «innocente» è uno strumento prezioso per dimostrare l'indecidibilità di problemi su grammatiche, linguaggi e sistemi di riscrittura.
Il rompicapo
Un'istanza del PCP è un insieme finito di tessere. Ogni tessera ha una stringa in alto e una in basso. Si possono usare le tessere quante volte si vuole, in qualsiasi ordine. Una soluzione (o match) è una sequenza non vuota di tessere tale che, concatenando le stringhe in alto, si ottiene esattamente la stessa stringa che si ottiene concatenando quelle in basso.
Il problema chiede: data un'istanza, esiste una soluzione?
Un'istanza risolvibile
Consideriamo quattro tessere, scritte come alto/basso:
| Tessera | Alto | Basso |
|---|---|---|
| 1 | b | ca |
| 2 | a | ab |
| 3 | ca | a |
| 4 | abc | c |
La sequenza 2, 1, 3, 2, 4 è una soluzione. In alto: a · b · ca · a · abc = abcaaabc. In basso: ab · ca · a · ab · c = abcaaabc. Le due stringhe coincidono.
Un'istanza senza soluzione
Ora le tessere abc/ab, ca/a, acc/ba. In ogni tessera la stringa in alto è più lunga di quella in basso. Qualunque sequenza produce quindi una riga superiore strettamente più lunga dell'inferiore, e le due non possono mai coincidere. Nessuna soluzione.
Questo caso si riconosce subito, ma in generale non esiste alcun criterio meccanico che funzioni sempre.
L'enunciato
Il linguaggio PCP = {⟨P⟩ : P è un'istanza del problema di corrispondenza di Post che ammette una soluzione} è indecidibile.
È però riconoscibile: basta provare tutte le sequenze di tessere in ordine di lunghezza crescente e accettare se se ne trova una che funziona. Se la soluzione esiste, prima o poi la si trova; se non esiste, la ricerca non termina.
L'idea della dimostrazione
La dimostrazione riduce A_TM al PCP. L'ingrediente chiave è la storia di calcolo: la sequenza di configurazioni C₁, C₂, …, Cₖ attraversate da una macchina M sull'input w, scritte una dopo l'altra e separate da un simbolo #.
Data ⟨M, w⟩, si costruisce un'istanza di tessere progettata in modo che l'unica maniera di ottenere una soluzione sia scrivere una storia di calcolo accettante di M su w.
- Tessera iniziale: in alto solo #, in basso #C₁#, dove C₁ è la configurazione iniziale. La riga inferiore parte in vantaggio di una configurazione.
- Tessere di transizione: per ogni transizione di M, una tessera che in alto ha un pezzo di configurazione e in basso il pezzo corrispondente dopo un passo. Per esempio, se δ(q, a) = (r, b, D), la tessera ha qa in alto e br in basso.
- Tessere di copia: per ogni simbolo del nastro, una tessera con lo stesso simbolo sopra e sotto, per ricopiare le parti di configurazione che non cambiano.
- Tessere di chiusura: quando compare lo stato accettante, tessere che permettono di «consumare» i simboli rimasti fino a pareggiare le due righe.
Il meccanismo è questo: la riga superiore insegue sempre quella inferiore. Per raggiungerla, chi risolve il rompicapo è costretto a trascrivere in alto la configurazione corrente, e le tessere lo obbligano a scrivere in basso la configurazione successiva. Le righe possono pareggiarsi solo se il calcolo arriva allo stato accettante. Quindi l'istanza ha soluzione se e solo se M accetta w.
Ci sono dettagli tecnici, come forzare la prima tessera a essere quella iniziale (si passa per una variante intermedia, il PCP modificato), ma l'idea è tutta qui.
Conseguenze sulle grammatiche
Il PCP è il punto di partenza per molti risultati sulle grammatiche libere dal contesto. Data un'istanza con tessere t₁, …, tₙ, si costruiscono due grammatiche:
- G_A genera le stringhe della forma «alto di tᵢ₁ … alto di tᵢₖ» seguite da un marcatore degli indici iₖ … i₁;
- G_B fa lo stesso con le stringhe in basso.
Una stringa generata da entrambe corrisponde esattamente a una soluzione. Ne seguono, fra gli altri, questi risultati:
- è indecidibile stabilire se due grammatiche libere dal contesto generano linguaggi con intersezione non vuota;
- è indecidibile stabilire se una grammatica libera dal contesto è ambigua (si considera la grammatica unione di G_A e G_B: una stringa con due derivazioni corrisponde a una soluzione).
Per questo nessuno strumento per parser li risolve in generale.
Varianti decidibili
Non tutte le versioni sono indecidibili. Il PCP con alfabeto di un solo simbolo è decidibile, perché conta solo la lunghezza delle stringhe e il problema diventa aritmetico. Anche il caso con due sole tessere è decidibile. Limitare la lunghezza della sequenza cercata rende il problema decidibile, ma lo porta nel campo della complessità: la versione limitata è NP-completa.
In sintesi
- Il PCP chiede se una sequenza di tessere produce la stessa stringa in alto e in basso.
- È riconoscibile, perché si possono provare tutte le sequenze, ma non decidibile.
- La dimostrazione costruisce tessere che obbligano a scrivere una storia di calcolo accettante.
- Dal PCP discendono l'indecidibilità dell'ambiguità e dell'intersezione delle grammatiche libere dal contesto.
- Con un alfabeto unario o con due tessere il problema diventa decidibile.
