Il lavoro di tesi si inserisce nell’ambito del Calcolo Molecolare, area che si è sviluppata in due direzioni. La prima (dry molecular computing) nasce con Head (1987), e mira allo sviluppo di nuovi modelli teorici di computazione come astrazione di fenomeni biologici. La seconda (wet molecular computing), che trova origine in un esperimento di Adleman (1994), mira all’utilizzo in provetta delle molecole di DNA per simulare algoritmi attraverso operazioni chimiche e biologiche.

La tesi è organizzata in due parti. Nella prima parte viene presentato l’esperimento di Adleman con i suoi vantaggi e svantaggi. Adleman ha utilizzato strumenti di biologia per risolvere un’istanza del problema del percorso hamiltoniano su un grafo orientato (problema notoriamente NP-completo), concretizzando l’idea di realizzare computazioni basate su DNA. Tra essi, in particolare, l’ibridazione, meccanismo con cui due filamenti di DNA che sono (Watson-Crick, WC) complementari si legano in uno solo, assumendo la tipica forma a doppia elica. Tra i vantaggi dei “computer a DNA” analizzati nell’esperimento, è stata osservata la possibilità di memorizzare le informazioni con un’altissima densità, un’enorme capacità di calcolo parallelo ed efficienza energetica. Sono stati esaminati anche i limiti dell’esperimento di Adleman: l’eccessiva crescita del peso delle molecole utilizzate per trovare la soluzione e la presenza di errori di ibridazioni, cioè la creazione di molecole di DNA derivate da un errato legame di due strati di DNA tra loro non perfettamente complementari. Da qui la necessità di individuare codici attendibili ed efficienti, minimizzando cioè la possibilità di legami errati.

Questa investigazione è proprio l’oggetto del “DNA Code Word design problem”. Viene analizzato un approccio al problema, che introduce inizialmente una nuova nozione di distanza, quella di Hamming per poi produrre risultati sperimentali circa la costruzione di insiemi di molecole “buone” da usare come codifica di algoritmi implementati in provetta.

Nella seconda parte viene affrontato lo stesso problema con un approccio più teorico, usando tecniche di linguaggi formali. Infatti la molecola viene vista come una parola su un alfabeto finito e un insieme di molecole viene visto come un linguaggio. Quindi studiare la “bontà” dell’insieme di molecole corrisponde a definire e studiare proprietà sui linguaggi. In letteratura sono state definite proprietà che i linguaggi devono soddisfare per evitare ibridazioni non desiderate: ad esempio la possibilità che un filamento di DNA si leghi (per ibridazione) a se stesso formando un hairpin; oppure che due filamenti u, v si leghino l’uno all’altro con il complemento WC di v fattore di u; o anche che un filamento si leghi alla concatenazione di altri due. Infatti tali situazioni possono rendere inutilizzabile la molecola (caso degli hairpin) o generare falsi. A tal fine vengono presentati i linguaggi c-compliant, τ-compliant, θ-free e θ-compliant, introdotti in letteratura, osservando che questi ultimi sono la generalizzazione di codici infissi. Dopo aver dato una lista di proprietà di linguaggi le quali assicurano che le parole di tali linguaggi non formino legami non voluti, vengono illustrati risultati circa la decidibilità e indecidibilità di tali proprietà. Infatti è noto che, dato un automa finito non deterministico A, è possibile decidere in tempo quadratico con la taglia dell’automa se il linguaggio accettato dall’automa L(A) è τ-free o τ-compliant, dove τ è l’involuzione DNA. Per quanto riguarda la non decidibilità sono stati presentati due problemi: data una grammatica context-free G restituire SI o NO, a seconda che il linguaggio generato dalla grammatica L(G) sia τ-free o τ-compliant.

La tesi si conclude riportando un approccio unificato delle varie definizioni con l’introduzione dei linguaggi bond-free, per i quali sono stati mostrati risultati di decidibilità e di massimalità.