l'accesso più veloce di browser!
16 relazioni: Argomento diagonale di Cantor, Congettura abc, Funzione (matematica), Funzione coppia, Funzione ricorsiva primitiva, Insieme ricorsivamente enumerabile, L (linguaggio), Linguaggio ricorsivamente enumerabile, Macchina di Turing, Piergiorgio Odifreddi, Principio di Markov, Teorema dello speedup di Blum, Teorema di Rice, Teorema di ricorsione di Kleene, Teoria della calcolabilità, Tesi di Church-Turing.
Argomento diagonale di Cantor
L'argomento diagonale di Cantor è una tecnica dimostrativa con cui Georg Cantor ha dimostrato la non numerabilità dei numeri reali.
Nuovo!!: Funzione calcolabile e Argomento diagonale di Cantor · Mostra di più »
Congettura abc
La congettura abc (anche nota come congettura di Oesterle-Masser) è stata proposta per la prima volta da Joseph Oesterlé e David Masser nel 1985.
Nuovo!!: Funzione calcolabile e Congettura abc · Mostra di più »
Funzione (matematica)
In matematica, una funzione è una relazione tra due insiemi, chiamati dominio e codominio della funzione, che associa a ogni elemento del dominio uno e un solo elemento del codominio.
Nuovo!!: Funzione calcolabile e Funzione (matematica) · Mostra di più »
Funzione coppia
In matematica si definisce funzione coppia una funzione che associa ad ogni coppia ordinata di numeri naturali un numero naturale con corrispondenza uno a uno; è quindi un'applicazione biiettiva \pi fra l'insieme prodotto \mathbb \times \mathbb e l'insieme dei numeri naturali \mathbb.
Nuovo!!: Funzione calcolabile e Funzione coppia · Mostra di più »
Funzione ricorsiva primitiva
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à.
Nuovo!!: Funzione calcolabile e Funzione ricorsiva primitiva · Mostra di più »
Insieme ricorsivamente enumerabile
Nella teoria della calcolabilità esistono due definizioni di insieme ricorsivamente enumerabile (spesso abbreviato in insieme r.e.) o insieme semi-decidibile.
Nuovo!!: Funzione calcolabile e Insieme ricorsivamente enumerabile · Mostra di più »
L (linguaggio)
Il linguaggio L è un linguaggio di programmazione ideato da Albert R. Meyer e da Dennis Ritchie che calcola solamente funzioni ricorsive primitive.
Nuovo!!: Funzione calcolabile e L (linguaggio) · Mostra di più »
Linguaggio ricorsivamente enumerabile
Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f di cui A è il codominio.
Nuovo!!: Funzione calcolabile e Linguaggio ricorsivamente enumerabile · Mostra di più »
Macchina di Turing
In informatica una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite.
Nuovo!!: Funzione calcolabile e Macchina di Turing · Mostra di più »
Piergiorgio Odifreddi
Oltre che di matematica, nelle sue pubblicazioni si occupa di divulgazione scientifica, storia della scienza, filosofia, politica, religione, esegesi, filologia e saggistica varia.
Nuovo!!: Funzione calcolabile e Piergiorgio Odifreddi · Mostra di più »
Principio di Markov
Il Principio di Markov, che deve il nome ad Andrej Andreevič Markov, è una tautologia della logica classica che non è intuizionisticamente valida ma può essere giustificata costruttivamente.
Nuovo!!: Funzione calcolabile e Principio di Markov · Mostra di più »
Teorema dello speedup di Blum
Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili.
Nuovo!!: Funzione calcolabile e Teorema dello speedup di Blum · Mostra di più »
Teorema di Rice
Nella logica matematica, nella teoria della calcolabilità e nell'informatica teorica, il teorema di Rice costituisce un importante risultato nella teoria delle funzioni ricorsive e delle funzioni calcolabili (le due sono la stessa cosa, secondo la tesi di Church-Turing).
Nuovo!!: Funzione calcolabile e Teorema di Rice · Mostra di più »
Teorema di ricorsione di Kleene
Nella teoria della computabilità, i teoremi di ricorsione di Kleene sono due fondamentali risultati riguardanti l'applicazione di funzioni calcolabili a loro stesse.
Nuovo!!: Funzione calcolabile e Teorema di ricorsione di Kleene · Mostra di più »
Teoria della calcolabilità
La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico.
Nuovo!!: Funzione calcolabile e Teoria della calcolabilità · Mostra di più »
Tesi di Church-Turing
Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: "se un problema è umanamente calcolabile, allora esisterà una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo (cioè di calcolarlo)." Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.
Nuovo!!: Funzione calcolabile e Tesi di Church-Turing · Mostra di più »
