Metraipolis › archive › dc_2be68af62907

Funzione di Ackermann — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Funzione_di_Ackermann
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-05T02:51:35.980Z
SHA-256 of the archived text
7ed7412771d2631f212dc7f9abc505ddaab88b4768bad80a7f8163b84dcb76ea
Stable URL of this page
https://metraipolis.com/documento/dc_2be68af62907

How to cite

Funzione di Ackermann — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Funzione_di_Ackermann (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2be68af62907 (Metraipolis archive dc_2be68af62907, sha256 7ed7412771d2631f212dc7f9abc505ddaab88b4768bad80a7f8163b84dcb76ea)
BibTeX
@misc{dc2be68af62907,
  title = {Funzione di Ackermann — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Funzione_di_Ackermann},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2be68af62907; sha256 7ed7412771d2631f212dc7f9abc505ddaab88b4768bad80a7f8163b84dcb76ea},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Funzione_di_Ackermann. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In matematica, la funzione di Ackermann è una funzione f(x,y,z) che ha come dominio l'insieme delle terne di numeri naturali e come codominio i numeri naturali. Essa è definita per ricorrenza nel seguente modo: f(0,0,z)=z; f(0,y+1,z)=f(0,y,z)+1; f(1,0,z)=0; f(x+2,0,z)=1; f(x+1,y+1,z)=f(x,[f(x+1,y,z)],z). Un caso particolare è la funzione di Ackermann a due argomenti A(m,n), così definita: A(m,n)={n+1se m=0,A(m−1,1)se m>0 e n=0,A(m−1,A(m,n−1))se m>0 e n>0. La funzione di Ackermann è definita per ogni coppia (m,n) di numeri naturali ed è sempre computabile. Il valore cresce molto rapidamente anche per valori molto piccoli di m e n. Per esempio, A(4,2) è un numero intero di 19 729 cifre. Per confronto, la costante di Avogadro ha solo 24 cifre. Il meccanismo di calcolo della funzione è estremamente semplice, quanto pesante dal punto di vista computazionale. La definizione data può essere vista come quella di una famiglia di funzioni al variare di un parametro individuato dalla prima variabile. Per ogni valore del parametro si ha una funzione che è ottenuta iterando la funzione precedente per un numero di volte individuato dalla seconda variabile. In quest'ottica le prime funzioni della famiglia sono funzioni familiari come l'addizione, la moltiplicazione e la potenza, seguite dalla tetrazione, e successivamente si hanno funzioni sempre più complesse: f(0,y,z)=y+z f(1,y,z)=y×z (mediante iterazione di z+z+z+… per y volte) f(2,y,z)=zy (mediante iterazione di z×z×z×… per y volte) f(3,y,z)=zzz... (y volte)(mediante iterazione di zzz... per y volte e quindi mediante iterazione di y×z e quindi mediante iterazione di y+z) Risulta quindi una funzione con una complessità estremamente elevata anche per valori di input semplici. L'inversa della funzione di Ackermann, indicata con α, compare in alcune dimostrazioni di scienze informatiche, come nell'algoritmo union-find.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Funzione di Ackermann» — https://it.wikipedia.org/wiki/Funzione_di_Ackermann
Wikidata Q341835: «total non-primitive-recursive computable function» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q341835
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Funzione_di_Ackermann?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 150655087, consultata il 2026-11-05T02:41:46.920Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 705008b72d51114ff39dbae5abdfcebf3e6d071e6802d9ca94f6a4581acba0dd