Metraipolis › archive › dc_7defe73c98b5
Funzione ricorsiva primitiva — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Funzione_ricorsiva_primitiva
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-05T02:53:52.557Z
- SHA-256 of the archived text
667e20373f5ffbca7af6682604bd8d4f8423de1132a0743669d24a0c446680d8- Stable URL of this page
https://metraipolis.com/documento/dc_7defe73c98b5
How to cite
Funzione ricorsiva primitiva — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Funzione_ricorsiva_primitiva (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7defe73c98b5 (Metraipolis archive dc_7defe73c98b5, sha256 667e20373f5ffbca7af6682604bd8d4f8423de1132a0743669d24a0c446680d8)
BibTeX
@misc{dc7defe73c98b5,
title = {Funzione ricorsiva primitiva — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Funzione_ricorsiva_primitiva},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7defe73c98b5; sha256 667e20373f5ffbca7af6682604bd8d4f8423de1132a0743669d24a0c446680d8},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Funzione_ricorsiva_primitiva. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità. Le funzioni ricorsive primitive sono un sottoinsieme stretto delle funzioni ricorsive (queste ultime corrispondono esattamente alle funzioni calcolabili). La classe più ampia delle funzioni ricorsive è definita aggiungendo la possibilità di avere funzioni parziali e introducendo un operatore di ricerca non limitato. Molte delle funzioni solitamente studiate nella teoria dei numeri, e le approssimazioni di funzioni a valori reali, sono primitive ricorsive, come l'addizione, la divisione, il fattoriale, l'esponenziale, la ricerca dell'ennesimo numero primo, e molte altre (Brainerd and Landweber, 1974). Infatti è difficile progettare una funzione che sia ricorsiva totale ma non primitiva ricorsiva, anche se se ne conoscono alcune, come la funzione di Ackermann. Perciò studiando questo particolare tipo di funzioni è possibile scoprire proprietà che hanno conseguenza di ampia portata. Le funzioni ricorsive primitive possono essere calcolate dalle macchine che terminano sempre, mentre le funzioni ricorsive richiedono sistemi con la stessa potenza di calcolo delle macchine di Turing. 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 ricorsiva primitiva» — https://it.wikipedia.org/wiki/Funzione_ricorsiva_primitiva Wikidata Q1570472: «funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1570472 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Funzione_ricorsiva_primitiva?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 151138648, consultata il 2026-11-05T02:50:16.387Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1a1702e03a68c4a10c8da395e2519c91e2f91da0dbe5baf9f5dea8f54d044eb6