Ricorsione e funzione di Ackermann

di
alfiere17
il
11 risposte
A
alfiere17
Pochi posts
Iscritto da
dic, 2015
Messaggi:
36

Ricorsione e funzione di Ackermann

Ciao a tutti...
il mio libro afferma che la funzione di Ackermann non è ricorsiva primitiva perchè cresce più rapidamente di tutte le altre. Ma da dove deriva la proprietà che il crescere più rapidamente implichi la non appartenenza alla classe delle funzioni ricorsive primitive?

11 Risposte

  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

    Re: Ricorsione e funzione di Ackermann

    Il punto che ti sfugge è che la funzione di Ackermann cresce più rapidamente di qualsiasi altra funzione primitiva ricorsiva, e dunque non può essere una di esse.
    Differenza sottile, ma fondamentale, rispetto a quanto hai scritto: non è il mero fatto di crescere "molto rapidamente" che la qualifichi come esempio di funzione computabile ma non primitiva ricorsiva, bensì la relazione di maggiorazione rispetto a qualsiasi altra funzione primitiva ricorsiva arbitrariamente scelta.

    Si tratta, dal punto di vista logico, di una relazione estesa tra una singola funzione e un intero insieme di funzioni, usata come argomento per giungere alla conclusione che la funzione non appartiene a detto insieme.
  • A
    alfiere17
    Pochi posts
    Iscritto da
    dic, 2015
    Messaggi:
    36

    Re: Ricorsione e funzione di Ackermann

    Non mi è però chiaro come tale relazione di maggiorazione possa portare ad affermare il non essere primitiva ricorsiva....
  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

    Re: Ricorsione e funzione di Ackermann

    Non è particolarmente difficile. L'argomentazione logica mostra che tutte le funzioni dell'insieme delle primitive ricorsive PR possiedono una proprietà (un tempo di calcolo "ragionevole", per una qualsiasi definizione teorica del termine) che invece la funzione di Ackermann non possiede, come mostra la relazione di maggiorazione. Pertanto, essa non può appartenere a tale insieme, QED.

    In alternativa, un'altra dimostrazione di non appartenenza della funzione di Ackermann all'insieme PR (la cui definizione, lo ricordo, poggia sulla tesi di Church-Turing) consiste in soldoni nel mostrare che non esiste il modo di rappresentare tale funzione usando una qualsiasi combinazione arbitraria di funzioni primitive ricorsive. Ciò, in ultima analisi, si riconduce sempre e comunque alla complessità asintotica di tale funzione.
  • A
    alfiere17
    Pochi posts
    Iscritto da
    dic, 2015
    Messaggi:
    36

    Re: Ricorsione e funzione di Ackermann

    Potresti, per caso, consigliare qualche link in cui ciò sia spiegato per bene? Il mio libro afferma solo della maggiorazione, senza spiegare, nello specifico, il perché della non appartenenza alle PR.
  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

    Re: Ricorsione e funzione di Ackermann

    Di che testo si tratta? Ce ne sono molti più approfonditi, ma temo che alcuni potrebbero essere troppo complessi per uno studente agli inizi.

    Come materiale online, si trovano facilmente dispense universitarie (non tutte di pari livello qualitativo, purtroppo) e anche qualche ragionevomente corretto, seppure non troppo approfondito.
    Fammi sapere se ti occorrono altri riferimenti.
  • +m+
    +m+
    Molto attivo
    Iscritto da
    gen, 2016
    Messaggi:
    712

    Re: Ricorsione e funzione di Ackermann

    Tra le varie applicazioni della funzioncella c'è quella
    di stabilire se una funzione calcolabile (totale) è sempre
    esprimibile con funzioni primitive ricorsive.

    Ovvero (per andare nella versione diciamo così implementativa) se
    ogni programma (che termina) si possa scrivere con cicli iterativi
    (cioè for per andare in concreto) e diramazioni condizionali
    (if then else) e basta.

    Cioè non è vero, e un esempio è proprio la fdA che termina
    (... bhè... un po' lentamente, ma termina!), ed è facilmente
    e concretamente implementabile.
  • A
    Aleph Zero
    Pochi posts
    Iscritto da
    lug, 2014
    Messaggi:
    30

    Re: Ricorsione e funzione di Ackermann

    So che è passato un po' di tempo ma è una domanda che mi incuriosisce.
    Il fatto che la funzione di Ackermann cresca più velocemente di qualsiasi altra funzione ricorsiva primitiva, non è solo una conseguenza del fatto che implementa la ricorsione su entrambi i parametri del passo ricorsivo?
    Dunque non basta affermare che la funzione di Ackerman non appartiene alle primitive ricorsive semplicemente perchè non rispetta la definizione data da Kleene (in quanto la ricorsione dovrebbe avvenire sempre su un solo parametro)?
  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

    Re: Ricorsione e funzione di Ackermann

    Aleph Zero ha scritto:

    Il fatto che la funzione di Ackermann cresca più velocemente di qualsiasi altra funzione ricorsiva primitiva, non è solo una conseguenza del fatto che implementa la ricorsione su entrambi i parametri del passo ricorsivo?
    Dunque non basta affermare che la funzione di Ackerman non appartiene alle primitive ricorsive semplicemente perchè non rispetta la definizione data da Kleene (in quanto la ricorsione dovrebbe avvenire sempre su un solo parametro)?
    No, non è sufficiente. A rigore, esistono numerosi altri casi di funzioni ricorsive doppie (e multiple) che apparentemente violano la definizione di Kleene, ma che invece appartengono appieno alla classe delle funzioni primitive ricorsive, pur variando ambedue i parametri. Esempi del genere (esempio principe: la stima archimedea del volume dell'Universo tramite granelli di sabbia) sono riportati sovente in letteratura, anche nel classico lavoro di sistematizzazione della teoria della calcolabilità svolto da Odifreddi nell'ultimo ventennio del secolo scorso.

    Non ci si deve poi lasciar trarre in inganno dal fatto che dette funzioni risultano sempre esprimibili equivalentemente in termini di funzioni primitive ricorsive: ciò non toglie che siano anche (meglio) formulabili tramite ricorsione doppia, il che invalida il tentativo di definizione dato.

    Ciò che invece caratterizza la funzione di Ackermann e gli altri controesempi noti, oltre alla velocità di crescita, è proprio la inerente irriducibilità secondo i termini della ricorsione primitiva, non il mero fatto di usare ricorsione multipla: il che porta all'introduzione di un nuovo operatore di minimizzazione µ (operatore di ricerca non limitato) e quindi all'estensione della classe delle funzioni ricorsive primitive in quella delle funzioni parziali ricorsive, la cui Turing equivalenza è stata provata appunto da Kleene.


    Vale inoltre la pena di sottolineare come la definizione di Kleene alla quale si accenna (omessa da buona parte dei testi introduttivi prodotti negli scorsi quattro o cinque lustri) sia in realtà da inquadrare soprattutto come parte dell'articolato e talora intricato percorso storico che ha condotto alle moderne definizioni: un interessantissimo percorso, oggetto di studio nei PhD di logica e qualche seminario specalistico o in selettive summer school come la ESSL, che lo stesso Kleene, in età avanzata, ha riassunto nello storico articolo "The theory of recursive functions, approaching its centennial" (Bulletin of the AMS, 5(1):43-61, 1981).
  • A
    Aleph Zero
    Pochi posts
    Iscritto da
    lug, 2014
    Messaggi:
    30

    Re: Ricorsione e funzione di Ackermann

    Ti ringrazio molto per la spiegazione data. Evidentemente ho interpretato male il concetto di primitiva ricorsiva. Dovrò quindi rivedere meglio questa parte del libro (Toffalori ), sul quale sto preparando il mio esame di calcolabilità e complessita.
    Ovviamente, tempo permettendo, darò anche un occhiata ai testi/riferimenti che mi hai detto.
    Grazie ancora
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5863

    Re: Ricorsione e funzione di Ackermann

    MAW, andiamo sul serio : dove trovo la dimostrazione che la funzione di Ackermann non e' primitiva ricorsiva?

    (nota: e' passato decisamente un bel po' di tempo da quando mi facevo queste domande )
  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

    Re: Ricorsione e funzione di Ackermann

    migliorabile ha scritto:

    MAW, andiamo sul serio : dove trovo la dimostrazione che la funzione di Ackermann non e' primitiva ricorsiva?
    Se ti interessa la dimostrazione originale dal punto di vista storico, questi sono gli articoli che hanno dato l'avvio all'intera questione:

    Wilhelm Ackermann, "Zum Hilbertschen Aufbau der reellen Zahlen", Matematische Annalen, 99:118-133, 1928
    Gabriel Sudan, "Sur le nombre transfini ?^?", Bulletin Màthematique de la Société Roumaine des Sciences, 30:11-30, 1927

    Pochi sanno che la cosiddetta "Funzione di Ackermann" dovrebbe in realtà chiamarsi Ackermann-Sudan. Al di là della data di pubblicazione, i relativi articoli (che di fatto descrivono esattamente la medesima funzione) sono stati inviati ai rispettivi peer editors distanza di poche settimane l'uno dall'altro, e sviluppati in modo totalmente indipendente. Ovviamente il fatto che Ackermann fosse allievo addirittura di un gigante come David Hilbert ha contribuito in modo sostanziale ad oscurare per decenni la presenza di un altro cointestatario della medesima scoperta presso la maggioranza degli studenti (per tacere degli insegnanti). Un ottimo survey sulla questione, utile anche per chi non legga tedesco e/o francese, è dovuto al grande Calude:

    Cristian Calude & Solomon Marcus, "The first example of a recursive function which is not primitive recursive", Historia Mathematica, 6:380-384, 1979

    Dimostrazioni semplificate si trovano poi in qualsiasi testo introduttivo e in numerosi articoli. Alcune di notevole valore storico sono dovute ad autori di grandissimo spessore, addirittura anche a Robinson (sì, proprio "quello" dell'aritmetica Q che porta il suo nome e semplifica assiomaticamente l'aritmetica di Peano PA).

    Rósza Péter, "Konstruktion nichtrekursiver Funktionen", Matematische Annalen, 111:42-60, 1935
    Raphael M. Robinson, "Recursion and double recursion", Bulletin of the AMS, 54:987-993, 1948

    Tra le migliaia di testi disponibili mi costringo a sceglierne solamente due, scelti tra i più recenti, noti e ben scritti:
    Moore & Mertens, "The nature of computation", Oxford University Press, 2011
    Qui la dimostrazione, parzialmente guidata e modellata su quella di Robinson (basata sulla classica idea di esclusione per maggiorazione già esposta ad inizio thread), è lasciata come esercizio per il lettore.

    Boolos et al., "Computability and logic", Cambridge, 2002
    Qui la dimostrazione, ancora ridotta a semplice esercizio, è invece basata sulla inesprimibilità della funzione di A. tramite funzioni primitive ricorsive, usando una metodologia sostanzialmente dovuta a Knuth.

    Lapalissianamente si possono citare altri testi a bizzeffe: anche in italiano, introduttivi, con dimostrazioni più o meno eleganti (di solito in modo inversamente proporzionale alla leggibilità), etc. ma non è certo questa la sede per una bibliografia esaustiva in merito...
Devi accedere o registrarti per scrivere nel forum
11 risposte