• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

Ackermann, funzione di

Enciclopedia della Matematica (2013)
  • Condividi

Ackermann, funzione di


Ackermann, funzione di esempio di → funzione ricorsiva che non è ricorsiva primitiva (→ funzione ricorsiva primitiva). Hilbert formulò l’ipotesi che ogni funzione calcolabile fosse ricorsiva primitiva, cioè ottenibile dalle funzioni di base (funzione zero, funzione successore e funzioni di proiezione) tramite i procedimenti di composizione e ricorsione. Tale affermazione si rivelò infondata quando nel 1928 Ackermann definì una nuova funzione calcolabile, ma non ricorsiva primitiva, poiché per ottenerla è necessario un ulteriore procedimento, detto di minimalizzazione. Questa funzione, che porta il suo nome e che qui di seguito è indicata con A, ha come dominio l’insieme dei numeri naturali N ed è definita nel modo seguente:

formula

Per comprendere il suo modo di operare, si può verificare, per passi successivi, che A(2,1) = 5:

formula

La funzione è calcolabile; tuttavia si può dimostrare che non è ottenibile soltanto per composizione e ricorsione di funzioni di base. Per definirla si deve ricorrere a un procedimento basato sull’applicazione di un operatore di → minimalizzazione, che data una funzione ricorsiva in n + 1 variabili permette di costruirne un’altra in n variabili.

Vedi anche
applicazione Matematica Il concetto di a. è una generalizzazione del concetto classico di funzione (➔ corrispondenza). Si parla di a. di un insieme P in un insieme Q, quando tra i due si stabilisce una corrispondenza del tipo seguente: a ogni elemento di P corrisponde un ben determinato elemento di Q, mentre un elemento ... codominio In matematica, l’insieme descritto dal valore di una funzione f(P), quando P varia nel dominio di definizione della funzione f(P).
Tag
  • FUNZIONE RICORSIVA PRIMITIVA
  • INSIEME DEI NUMERI NATURALI
  • FUNZIONE CALCOLABILE
  • FUNZIONE RICORSIVA
Vocabolario
funzióne
funzione funzióne s. f. [dal lat. functio -onis, der. di fungi «adempiere»]. – 1. Attività svolta abitualmente o temporaneamente in vista di un determinato fine, per lo più considerata nel complesso di un sistema sociale, burocratico, ecc....
Disforia di genere
disforia di genere loc. s.le f. Condizione di intensa e persistente sofferenza causata dal sentire la propria identità di genere diversa dal proprio sesso anatomico. ♦ «Come ha appena detto la compagna transgender...». I delegati di fabbrica...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali