• 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

funzione calcolabile

Enciclopedia della Matematica (2017)
  • Condividi

funzione calcolabile


funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di ciascun valore ammesso per le sue variabili indipendenti. In generale, una funzione a una variabile associa a ogni valore del suo insieme di definizione uno e un solo valore di un insieme detto codominio. Se la funzione è calcolabile, tale corrispondenza è effettuata tramite un algoritmo di calcolo; per questo motivo una funzione calcolabile può essere pensata come un → automa in grado di elaborare l’informazione in ingresso e fornire, in modo univoco, il risultato in uscita. Un esempio elementare di funzione calcolabile è la funzione successore che associa a ogni numero naturale n il numero n + 1, suo successivo nell’ordinamento naturale. La funzione successore è indicata con il simbolo s e si ha, quindi: s(n) = n + 1. Le funzioni calcolabili possono avere anche più variabili: per esempio la funzione somma e la funzione prodotto, che rispettivamente associano a due numeri x e y il numero x + y e il numero x ⋅ y, sono funzioni calcolabili di due variabili. La loro effettiva calcolabilità è garantita, in entrambi i casi, dalla possibilità di definire una procedura deterministica e finita che, dati due numeri, permette di giungere al risultato, calcolare cioè la somma e il prodotto. Utilizzando funzioni calcolabili elementari, è possibile costruire funzioni più complesse, anch’esse calcolabili. Per esempio, indicando con A la funzione somma e con P la funzione prodotto si può costruire la funzione calcolabile A(P(x, s(y)), z), che si può interpretare come ƒ(x, y, z) = x ⋅ (y + 1) + z.

Non tutte le funzioni definibili sono calcolabili; c’è infatti una differenza sostanziale fra definire in modo coerente e matematicamente corretto una funzione e poterne calcolare il valore. Per esempio, l’algoritmo per il calcolo della divisione fra numeri interi può non avere termine, come nel caso della divisione fra 5 e 3 (5 : 3 = 1,6666...): la funzione che associa a ogni coppia di numeri interi positivi x e y il loro rapporto x : y non è quindi una funzione calcolabile, bensì semicalcolabile, perché la procedura di calcolo che la definisce è finita in alcuni casi e non lo è in altri. Nel caso della divisione è comunque possibile modificare l’algoritmo in maniera tale da renderlo finito, imponendo che si fermi a una data cifra decimale. Esistono tuttavia casi in cui la funzione è intrinsecamente non calcolabile. Per esempio, tra i 23 problemi posti da Hilbert (→ Hilbert, problemi di), il decimo chiede di definire un algoritmo per stabilire se una qualunque equazione diofantea (equazione cioè a coefficienti interi), abbia o meno soluzioni intere. In modo equivalente il problema si può così formulare: definire per casi una funzione ƒ sull’insieme dei polinomi a coefficienti interi tale che per ogni polinomio p

Enciclopedia della Matematica formula lettf 03420 001.jpg

Questa funzione, pur essendo ben definita da un punto di vista matematico, nel senso della possibilità di impiegare il principio del terzo escluso per definire oggetti, non è calcolabile: nel 1970, il matematico russo J. Matijasevič ha, infatti, dimostrato che il problema è indecidibile (→ decidibilità). L’esistenza di funzioni non calcolabili, come quella appena descritta, determina l’esigenza di capire quante e quali siano le funzioni calcolabili all’interno delle funzioni ben definite. Innanzitutto, poiché il concetto di funzione calcolabile discende dal concetto di algoritmo e poiché in un automa esecutore i dati e i risultati sono rappresentati in modo discreto, il dominio di una funzione calcolabile è anch’esso discreto. Ciò comporta che una funzione calcolabile ha come dominio e come codominio l’insieme dei numeri naturali; è, quindi, una funzione aritmetica. L’insieme delle funzioni calcolabili è un sottoinsieme dell’insieme delle funzioni aritmetiche; tuttavia esistono funzioni aritmetiche che non sono calcolabili. Inoltre, mentre le funzioni calcolabili costituiscono una infinità numerabile, l’insieme delle funzioni aritmetiche non calcolabili ha cardinalità superiore al numerabile (→ funzione caratteristica). Si può quindi affermare che gli oggetti matematici che si possono effettivamente costruire sono soltanto una piccola parte di quelli che si possono coerentemente definire.

Allo scopo di fornire una traduzione rigorosa del concetto di funzione calcolabile, a partire dagli anni Trenta del Novecento sono stati introdotti e studiati alcuni modelli formali per descrivere il processo di calcolo di una funzione. Fra i modelli di calcolo introdotti ci sono le → funzioni ricorsive, la macchina di → Turing e il λ-calcolo (→ lambda-calcolo). Secondo la cosiddetta tesi di → Church, l’insieme delle funzioni ricorsive rappresenta in maniera adeguata l’insieme delle funzioni calcolabili nel senso che ogni funzione calcolabile può essere definita come funzione ricorsiva e, viceversa, ogni funzione ricorsiva è una funzione calcolabile. La tesi di Church è avvalorata dal fatto che tutti i formalismi finora introdotti per descrivere le funzioni calcolabili sono equivalenti fra loro, rappresentano cioè la stessa classe di funzioni.

Vedi anche
Alonzo Church Matematico e logico-matematico statunitense (Washington 1903 - Hudson, Ohio, 1995), prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, dal 1967 di matematica e filosofia all'univ. di California. Nel 1936 enunciò la proposizione oggi chiamata tesi (o ipotesi o legge) di ... cardinalità Nella teoria degli insiemi, c. (o potenza) di un insieme è il numero degli oggetti di un insieme finito (numero cardinale). Si può estendere il concetto di c. anche a insiemi infiniti: due insiemi hanno la stessa c. quando è possibile stabilire tra gli oggetti che li compongono una corrispondenza biunivoca ... David Hilbert {{{1}}} Matematico tedesco (Königsberg 1862 - Gottinga 1943). È la figura più notevole della matematica della prima metà del Novecento e forse dell'intero secolo. A Königsberg frequentò l'università con A. Hurwitz, già professore, e con H. Minkowski, suo condiscepolo. Dal 1895 al 1929 fu prof. all'univ. ... inclusione Botanica Sostanza o soluzione complessa racchiusa nei vacuoli delle cellule, detta anche incluso cellulare; può essere liquida, come le goccioline di oli, o solida, come la drusa . CHIMICA Composto di i. Tipo di composto chimico derivante dall’imprigionamento di molecole di una sostanza (molecole ospiti) ...
Tag
  • INSIEME DEI NUMERI NATURALI
  • PRINCIPIO DEL TERZO ESCLUSO
  • INSIEME DI DEFINIZIONE
  • MACCHINA DI → TURING
  • FUNZIONE ARITMETICA
Vocabolario
calcolàbile
calcolabile calcolàbile agg. [der. di calcolare]. – Che può essere calcolato. In matematica, funzione c., funzione che può essere calcolata, per la quale esiste cioè un procedimento effettivo per calcolare il suo valore per dati valori...
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....
  • 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