Computable Approximations of Semicomputable Graphs

1. Problema e Contesto

Il lavoro si inserisce nel programma di ricerca avviato da Miller (2002) volto a determinare quali condizioni topologiche rendono un sottoinsieme semicomputabile di uno spazio metrico computabile anche computabile.

• Definizioni chiave:
  • Un insieme compatto $S$ è semicomputabile se l'insieme delle unioni finite di palle aperte razionali che lo coprono è enumerabile computabilmente (c.e.).
  • Un insieme è computabile se è sia semicomputabile che c.e. (computabilmente enumerabile).
  • Sebbene ogni insieme computabile contenga punti computabili densi, esistono insiemi semicomputabili (anche di tipo topologico semplice come un arco) che non contengono alcun punto computabile e quindi non sono computabili.

Il problema specifico affrontato riguarda i grafi topologici (spazi ottenuti incollando archi e raggi agli estremi). È noto che un grafo semicomputabile non è necessariamente computabile, specialmente se possiede estremi non computabili. La domanda centrale è: Se $S$ è un grafo semicomputabile, può essere approssimato con precisione arbitraria da un sottografo computabile?

2. Metodologia

Gli autori utilizzano strumenti della topologia computabile e della teoria degli spazi metrici computabili. La metodologia si basa su tre pilastri principali:

1. Analisi Locale degli Archi: Il cuore della dimostrazione risiede nella costruzione di un intorno computabile per punti che hanno un intorno omomorfo a $\mathbb{R}$.
2. Catene Formali (Formal Chains): Vengono utilizzate successioni di "catene" (sequenze di insiemi aperti sovrapposti) definite tramite indici computabili (palle razionali) per approssimare la struttura del grafo. L'uso di catene formali permette di gestire le proprietà computazionali senza dover costruire esplicitamente i punti limite.
3. Taglio degli Estremi Non Computabili: La strategia principale consiste nell'identificare gli estremi non computabili di un grafo semicomputabile e "tagliare" piccoli segmenti attorno a questi punti, sostituendoli con nuovi estremi che sono punti computabili.

3. Risultati Chiave e Contributi

A. Esistenza di un Intorno Computabile (Teorema 3.3)

Il primo risultato fondamentale è un rafforzamento di un teorema precedente (Iljazić e Vukotić, 2017).

• Enunciato: Se un punto $x$ in un insieme semicomputabile $S$ ha un intorno $N$ omomorfo a $\mathbb{R}$, allora esiste un intorno computabile $N' \subseteq N$ che è un arco con estremi computabili.
• Significato: Questo risultato è cruciale perché garantisce che, anche se l'intero insieme non è computabile, la struttura locale attorno a punti "regolari" (non estremi) può essere catturata da un oggetto computabile ben definito (un arco con estremi noti).

B. Approssimazione di Grafi Compatti (Teorema 4.1 e Corollario 4.2)

Gli autori dimostrano che ogni grafo semicomputabile compatto può essere approssimato da un sottografo computabile.

• Procedura: Dato un grafo semicomputabile $S$ e una precisione $\epsilon > 0$, per ogni arco $A_i$ che definisce il grafo:
  • Se gli estremi di $A_i$ sono computabili, l'arco rimane invariato.
  • Se un estremo è non computabile, viene rimosso un piccolo segmento di lunghezza inferiore a $\epsilon$ vicino a quell'estremo, sostituendolo con un nuovo estremo che è un punto computabile (ottenuto tramite il Teorema 3.3 e il Lemma 3.5).
• Risultato: Esiste un sottografo $T \subseteq S$ tale che:
  1. $T$ è un grafo computabile.
  2. Tutti gli estremi di $T$ sono punti computabili.
  3. La distanza di Hausdorff $d_H(S, T) < \epsilon$.
  4. $T$ differisce da $S$ solo in piccoli intorni degli estremi non computabili originali.

C. Estensione a Grafi Non Compatti (Teorema 4.3 e Corollario 4.4)

Il risultato viene generalizzato ai grafi non compatti (che possono contenere raggi).

• La procedura di "taglio" viene applicata anche agli estremi di raggi non computabili.
• Si dimostra che ogni grafo semicomputabile (compatto o meno) può essere approssimato da un sottografo computabile con estremi computabili, tale che $S \approx_\epsilon T$ (in termini di vicinanza $\epsilon$).

D. Applicazione alle 1-Varietà (Corollario 4.5)

Poiché ogni 1-varietà con bordo e un numero finito di componenti è un grafo, il risultato si applica direttamente anche a queste strutture. Ogni 1-varietà semicomputabile può essere approssimata da una 1-varietà computabile con bordo computabile.

4. Significato e Implicazioni

Questo lavoro risolve una questione aperta nella topologia computabile relativa alla struttura dei grafi semicomputabili:

1. Superamento dell'Ostacolo degli Estremi: Dimostra che l'unico ostacolo alla computabilità di un grafo semicomputabile risiede nella natura degli suoi estremi. Se si rimuovono o si modificano leggermente le regioni attorno agli estremi non computabili, l'oggetto risultante diventa completamente computabile.
2. Approssimazione Effettiva: Fornisce un metodo costruttivo per approssimare oggetti topologici complessi (grafi) con oggetti computabili, mantenendo la struttura topologica globale e garantendo una precisione arbitraria.
3. Generalizzazione: Estende risultati precedenti noti per gli archi (1-dimensionali) e le varietà 1-dimensionali a una classe più ampia di spazi (grafi con possibili cicli e raggi), confermando che la proprietà di "essere approssimabile da un oggetto computabile" è robusta per questa classe di spazi.

In sintesi, il paper stabilisce che i grafi semicomputabili sono "quasi computabili": la loro non-computabilità è un fenomeno locale e isolato agli estremi, e può essere risolta mediante una semplice operazione di troncamento che porta a un sottografo perfettamente computabile.