Concetti equivalenti: funzioni ricorsive, linguaggi ricorsivi.
Concetti equivalenti: funzioni parzialmente ricorsive, linguaggi ricorsivamente enumerabili.
Il problema di stabilire se esiste un virus su un sistema è indecidibile. Tuttavia, ciò
non vuol dire che sia impossibile scoprire un virus in un sistema. Infatti se di un certo virus
se ne possiede la firma
,
basterà ricercare all'interno dei programmi l'eventuale presenza di tale impronta
virale. Quindi l'indecidibilità significa che non esiste una soluzione generale al problema di
scoprire la presenza di un virus in un sistema.
W. Dowling [Dow89] ha dimostrato che, qualunque sia la definizione di virus, nessun programma può contemporaneamente testare il proprio input alla ricerca di un virus ed essere sicuro di non diffondere esso stesso un virus. Vediamo come.
I programmi girano in un ambiente: ciò significa che qualsiasi programma è eseguito come subroutine di un programma logicamente indipendente, che è il sistema operativo. Supponiamo che un virus sia un programma che quando è in esecuzione altera il codice del sistema operativo. Questa ipotesi dà luogo alle seguenti osservazioni:
Supponiamo di poter disporre di un programma filtro che ricevendo in input un programma stabilisca se sia un virus o no, con la garanzia di non diventare esso stesso un veicolo per la diffusione dell'infezione.
In ogni caso si è dimostrato che il programma filtro IS-SAFE non può essere contemporaneamente safe e corretto. Quindi non si può stabilire con esattezza se un arbitrario programma P è un virus oppure no [Fer93].