Halting Problem

Da aptiva.

THE HALTING PROBLEM (IL PROBLEMA DELLA FERMATA)

Il problema della fermata (the halting problem) fu pubblicato nel 1937 dal matematico inglese Alan Turing, che, con la sua idea di macchina universale, è stato il precursore del moderno concetto di “programma”. Il problema della fermata chiede se sia sempre possibile, descritto un algoritmo e un determinato input finito, stabilire se l'algoritmo in questione termini o continui la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input.

Il problema sopra descritto affronta una delicata questione, che si traduce in parole più semplici nell'affermazione che non è possibile stabilire la correttezza di un qualsiasi programma. In queste poche righe tenteremo di tracciare un strada percorribile volta alla comprensione di questo difficile problema teorico che nel contempo riveste un ruolo centrale nelle discipline informatiche. Lo strumento che utilizzeremo per calarci nei meandri oscuri della logica matematica è ancora una volta il linguaggio Python. Se avessimo utilizzato un linguaggio come C avremmo dovuto introdurre alcune semplificazioni, poiché in C, dato che le funzioni (procedure) sono solo parametrizzate su valori, è possibile avere altre funzioni come parametri solamente considerando dei puntatori ad esse. Al contrario Python permette di specificare funzioni come argomenti di altre funzioni, poiché possiamo vedere una funzione semplicemente come una stringa e quindi passarla come argomento ad un'altra.

Esempio:

def sum(a, b):
	return a + b

def mul(a, b):
	return a * b

def execFunc (f, a, b):
	return f(a, b)

def main():
	a=5
	b=6
	print('Sum: ', execFunc (sum,a,b))
	print(Mul: ', execFunc (mul,a,b))

if __name__ == '__main__':
	main()

La dimostrazione di Turing del problema della fermata procede per assurdo e si basa sul fatto che, nei calcolatori, un programma è codificato mediante una sequenza di simboli che viene data in ingresso a un altro programma (tipicamente un compilatore), quindi una stessa sequenza di simboli può essere interpretata sia come un programma che come un dato d’ingresso di un altro programma. Dimostriamo che non esiste nessuna funzione Python P che prende come argomento un'altra funzione Python Q ed una stringa s che in tempo finito, dia in output True se Q su input s si ferma e False altrimenti. Ma prima di procedere notiamo che affermare questo implicherebbe una soluzione della famosa congettura di Goldbach.

LA CONGETTURA DI GOLDBACH

La congettura di Goldbach afferma che ogni numero pari maggiore di 2 può essere scritto come somma di due numeri primi p e q.

Esempio:

4 = 2 + 2

6 = 3 + 3

8 = 3 + 5

10 = 3 + 7 = 5 + 5

12 = 5 + 7

14 = 3 + 11 = 7 + 7

La congettura di Goldbach è probabilmente il più famoso problema non risolto (o solo parzialmente risolto) della teoria dei numeri. E’ comunemente attribuita a Goldbach, anche se Cartesio aveva avanzato la stessa ipotesi. Christian Goldbach notò che poteva esprimere ogni numero naturale maggiore di 2 come somma di 3 numeri primi e lo comunicò a Eulero in una lettera nel 1742, che segnò la nascita di uno dei più grandi problemi della matematica. Eulero gli rispose osservando che ciò derivava dal poter esprimere ogni numero pari maggiore di 2 come somma di due numeri primi, anche se non poteva dimostrarlo. Osserviamo che Goldbach considerava 1 come numero primo, quindi alcuni esempi riportati nella lettera sono 3=1+1+1; 4=1+1+2; 5=1+1+3=1+2+2…., mentre oggi l’1 non è più considerato un numero primo e quindi il limite inferiore dei numeri rappresentabili è cambiato.

La congettura si può scindere in due parti distinte:

- la prima chiamata “debole” o “ternaria” è:

ogni numero dispari maggiore di 5 può essere espresso come somma di tre numeri primi;

- la seconda, più difficile, chiamata “forte” o “binaria”, è:

ogni numero pari maggiore o uguale a 4 può essere espresso come somma di due numeri primi.

La prima parte è ovviamente conseguenza della seconda: se partiamo dall'ipotesi che ogni numero pari maggiore o uguale a 4 sia la somma di due numeri primi, è facile vedere che un numero dispari maggiore di 5 (ossia maggiore o uguale a 7) è sempre uguale alla somma di tre numeri primi. Infatti, dato un numero dispari maggiore o uguale a 7, se gli sottraiamo 3, si ottiene un numero pari maggiore o uguale a 4, che è dunque la somma di due primi grazie alla nostra ipotesi. Sommando il numero 3 a questi due numeri primi, si ritorna al numero di partenza che è quindi la somma di tre numeri primi.

La congettura debole di Goldbach è stata dimostrata nel 2013 dal matematico peruviano Harald Andrés Helfgott. Per quanto riguarda i numeri pari, il miglior risultato valido per tutti gli interi indipendentemente da altre congetture restò a lungo quello di Ramaré, che dimostrò nel 1955 che ogni numero pari maggiore di 2 è la somma di al massimo 6 numeri primi. La dimostrazione di Helfgott ci assicura che 4 primi bastano, ma tutti ritengono che ne bastino 2.

Consideriamo il seguente programma in linguaggio Python:

def gc(n): #Goldbach Conjecture
	while(True):
            found = True
            for p in range(1,  n):
            	q = n - p
            	if isPrime(p) and isPrime(q):
                	found = False
            if found:
            	break

Se la congettura di Goldbach fosse vera, allora il programma non terminerebbe mai, se invece la congettura fosse falsa allora esisterebbe un numero intero pari maggiore o uguale a 4 che non può essere scritto come la somma di due numeri primi, ciò causerebbe una terminazione del programma. Se riuscissimo a scrivere un programma che verifica se la funzione scritta sopra termina oppure no vinceremmo un bel gruzzolo messo in palio dalla Faber & Faber.

DIMOSTRAZIONE DEL PROBLEMA DELLA FERMATA

Dopo questa digressione ritorniamo al nostro problema e supponiamo adesso che P esista e consideriamo un altra funzione HP che prende come input un'altra funzione Q.

def HP (Q):
     if P(Q, Q) == True:         #usa P per controllare se Q si ferma quando riceve Q
        while (True):            #se Q si ferma allora HP non si ferma
              pass               #altrimenti HP termina

La funzione HP con argomento Q si ferma se Q non si ferma quando riceve se stesso come argomento e viceversa. Adesso cosa succede se passiamo HP come argomento a se stessa?

def HP (Q):
     if P(HP, HP) == True:       #usa P per controllare se HP si ferma quando riceve HP
        while (True):            #se HP si ferma allora HP non si ferma
              pass               #altrimenti HP termina

Per definizione HP su input HP si ferma se e solo se il suo argomento, HP, non si ferma quando riceve se stesso come argomento in input. Quindi HP si ferma su input HP se e solo se HP non si ferma. In questo modo abbiamo ottenuto una contraddizione e raggiunto un assurdo.

CONCLUSIONI

I risultati ottenuti non devono scoraggiarci: è vero che non potremmo mai scrivere un programma che verifica la terminazione di un altro, ma esistono algoritmi che possono essere analizzati e sui quali si possono trarre conclusioni certe. Consideriamo il problema di stabilire se un dato numero intero p > 1 è un numero primo (ovvero divisibile soltanto per 1 e per se stesso) e presentiamo il seguente programma che codifica un possibile algoritmo di risoluzione per tale problema:

primo(numero):
   fattore = 2
   while(numero%fattore != 0):
       fattore = fattore + 1 
   return fattore==numero

Codifica in linguaggio Python:


def primo(n):
   for i in range(2,  int(n**0.5)+1):  #conrollo tutti gli interi i minori di radice n
       if n % i == 0:                  # test di divisibilità
            return False               # trovato un divisore
   return True                         # nessun divisore trovato

if __name__ == '__main__':
   n = int(input("inserisci un numero "))
   if primo (n):
        print(n," e' primo")
   else:
        print(n," non e' primo")  

Questo è un semplice esempio in cui è immediato stabilire se il programma termina: infatti, la variabile fattore viene incrementata di uno ad ogni iterazione e la condizione del ciclo while non è sicuramente verificata quando fattore è uguale a numero.

Oppure si potrebbero progettare algoritmi che aggirino il problema. Una soluzione pratica potrebbe essere quella di eseguire il programma di verifica, se esso si ferma avremo la nostra risposta, altrimenti se dopo un certo periodo di tempo non termina, potremo immaginare che non si fermerà. Tuttavia non si sa se il programma potrebbe fermarsi in seguito.

Sitografia

  • libeccio.di.unisa.it/LabInf2013/Halting.pdf
  • wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf
Strumenti personali
Namespace

Varianti
Azioni
Navigazione
Strumenti