SELECT

Il Problema dell’Arresto

6 anni fa

6 minuti

page

Negli ultimi anni i computer si sono dimostrati sempre più potenti e versatili, sempre pronti a risolvere i nostri problemi in un solo istante, ma è vero che essi sono in grado di risolvere qualsiasi problema?

Se siete fra quelli che hanno una fiducia cieca nell’avanzamento tecnologico e che credono di poter affrontare qualsiasi problema con un computer, mi spiace (ma non troppo) deludervi dicendovi che è noto che esistono problemi non risolvibili da una qualsivoglia macchina, nemmeno in un tempo infinito.

Esistono problemi non risolvibili da una qualsivoglia macchina, nemmeno in un tempo infinito.

Se non fossimo dei nerd l’articolo potrebbe finire qui e ci accontenteremmo di queste due righe, ma un nerd è curioso (ed io sono un pericoloso ibrido nerd-informatico-matematico che ama tediare la gente con queste cose) e vuole saperne di più.

Quello che vi presento di seguito è un esempio di un problema non risolvibile da una qualsivoglia macchina, prendendo per buona la tesi di Church-Turing: il problema dell’arresto, per gli amici Entscheidungsproblem.

 

 

Cenni storici

PHilberter logici e matematici di ogni tempo l’idea di possedere una macchina che decidesse se una formula fosse vera o falsa in modo automatico è sempre stato un sogno.

David Hilbert nel 1928 formalizzò quest’idea e si chiese se potesse esistere un algoritmo che, data in input una formula logica qualsiasi, decidesse se essa fosse vera o falsa, nacque quindi l’Entscheidungsproblem, o problema dell’arresto, risolto indipendentemente da Alonzo Church e Alan Turing nel 1936.

 

 

Un modello per il nostro computer

Sicuramente molti di voi avran sentito parlare di macchine di Turing, λ-calcolo e altri formalismi più o meno complicati, siccome non vogliamo addentrarci nella matematica vediamo un semplice modello di calcolo molto intuitvo, ma sufficientemente espressivo.

Il nostro formalismo è uno pseudo-linguaggio di programmazione capito da una macchina ipotetica che chiameremo RAM (random access machine, un modello di calcolo vicinissimo alla nostra intuizione ed a quella dei linguaggi di programmazione imperativi che molti di noi conoscono), composto dalle seguenti istruzioni:

  • Comando o lista di comandi, di solito istruzioni (per noi intuitive) date alla macchina, ad esempio x = y + 42 che dice alla nostra macchina che x vale quello che vale y più 42 oppure return 42 che ci dice che il nostro programma darà come risultato 42 (manca poco al towel day, concedetemelo! :D )
  • Selezione, scritta come if <condizione> then <comando1> else <comando2> che dice alla nostra macchina che se è vera <condizione> allora dovrà eseguire il <comando1> altrimenti dovrà eseguire il <comando2>.
  • Iterazione, scritta come while <condizione> do <comando> che dice alla nostra macchina di eseguire <comando> finchè la condizione è vera.

Ad esempio il seguente programma calcola il prodotto di due numeri:

moltiplica (x, y):

  • somme_restanti = y
  • risultato = 0
  • while somme_restanti > 0 do
    • risultato = risultato + x
    • somme_restanti = somme_restanti – 1
  • return risultato

 

Per i più smaliziati un piccolo esercizio, se avessi omesso l’istruzione somme_restanti = somme_restanti – 1 supponendo y > 0, cosa sarebbe accaduto? (in piccolo la risposta, anche se vi invito a ragionarci un istante da soli!).

Ovviamente il programma proseguirebbe all’infinito perché la condizione i > 0 non diventerebbe mai falsa, visto che i non cambierebbe mai.

E’ possibile dimostrare che il modello RAM permette di esprimere tutte e sole le computazioni degli altri formalismi “più famosi” che abbiamo citato prima.

 

 

Entscheidungsproblem!

Finalmente abbiamo gli strumenti per poter mostrare qualcosa di veramente irrisolvibile!

Supponiamo di possedere un programma bellissimo e fantastico al quale, dato in input un altro programma e l’input di tale programma, ci possa dire se esso termina o meno (per capirci, se raggiunge mai l’istruzione return) per quel particolare input senza eseguire P, lo chiamiamo Arresto(P, I) con P il programma da valutare e I l’input di P.

Se P fosse il nostro moltiplica tutti sapremmo dire velocemente cosa risponderebbe Arresto, ma è sempre così facile? Ancora una volta, no! (Questa teoria della calcolabilità è piena di no!), ma vediamolo meglio.

Prendiamo in considerazione questo programma:

programma ( P ):

  • while Arresto(P, P) do
    • niente

 

ed osserviamo che programma(P) termina se e solo se Arresto(P, P) ci dicesse che P non termina su input P (sembra una cosa molto complicata, ma non lo è se pensiamo che un programma può benissimo essere l’input di una altro programma). A questo punto supponiamo che si esegua programma(programma) (ovvero che eseguiamo il nostro programma con input uguale a sè stesso); Cosa accadrebbe? Avremmo che programma(programma) terminerebbe se e solo se Arresto(programma, programma) ci dicesse che programma non termina su input programma! Accidenti…un paradosso! Non può dunque esiste un programma come Arresto che decida in generale quanto detto!

Se pensate che questo problema sia del tutto isolato ed interessante solo per noi teorici e pochi altri pensate che se avessimo un programma come il nostro Arresto saremmo in grado di dimostrare al volo molte congetture di teoria dei numeri, come ad esempio la congettura 3n+1 o quella di Goldbach, ma anche problemi più pratici come questo programma, chiamato Corretto, che vuole un altro programma P come input e che ne verifica la correttezza:

Corretto (P):

  • ok=true
  • while ok do
    • esegui P su uno degli input che non hai ancora provato; setta ok a falso se P da la risposta errata su tale input

 

Notiamo che Corretto(P) termina se e solo se P è un programma non corretto.

A questo punto chiamando Arresto(Corretto, P) avremmo che Arresto da risposta affermativa se e solo se Corretto termina e quindi se P è non corretto, risposta negativa viceversa: avremmo un modo semplice di decidere se i nostri programmi sono corretti o meno! – questo sarebbe il sogno di tutti gli informatici!

 

Note e approfondimenti

L’argomento è vastissimo e quello che vi ho mostrato è una trattazione tutt’altro che precisa e formale dell’argomento, se la vedesse il mio prof. di Calcolabilità mi cancellerebbe il voto dal libretto.

 

Se vi è piaciuto l’argomento e volete saperne di più, per iniziare:

poi qualcosina di più “formale” (non molto a dire il vero!):

ed infinte per approfondimenti più rigorosi (ci vogliono basi discrete di matematica):

  • Lewis, Harry R., and Christos H. Papadimitriou.
    Elements of the Theory of Computation
    Prentice Hall PTR, 1997. (uno dei miei preferiti, contiene anche molto altro!)
  • Church, Alonzo.
    An unsolvable problem of elementary number theory
    The Undecidable, Raven Press, Hewlett, New York (1965): 88-107.
  • Turing, Alan Mathison.
    On computable numbers, with an application to the Entscheidungsproblem
    J. of Math 58.345-363 (1936): 5.
Eddie Murphy: i 10 migliori film con il popolare attore comico
Eddie Murphy: i 10 migliori film con il popolare attore comico
WandaVision, la spiegazione del finale
WandaVision, la spiegazione del finale
Il Principe cerca Figlio, la recensione: Eddie Murphy come Black Panther
Il Principe cerca Figlio, la recensione: Eddie Murphy come Black Panther
WandaVision, la recensione dell’episodio finale: Wanda (e Visione) all along
WandaVision, la recensione dell’episodio finale: Wanda (e Visione) all along
Fino All’Ultimo Indizio, la recensione: quando l'indagine diventa ossessione
Fino All’Ultimo Indizio, la recensione: quando l'indagine diventa ossessione
Raya e l'Ultimo Drago, la recensione
Raya e l'Ultimo Drago, la recensione
Raya e l'Ultimo Drago, dalle parole di registi, sceneggiatori e producer
Raya e l'Ultimo Drago, dalle parole di registi, sceneggiatori e producer