Indice
9 relazioni: Algoritmo, Funzione ricorsiva primitiva, Lisp, Numero di Gödel, Punto fisso, Stephen Kleene, Teorema di ricorsione di Kleene, Teoria della calcolabilità, Valutazione parziale.
- Teoremi nella teoria della computazione
- Teoria della calcolabilità
Algoritmo
In matematica e informatica un algoritmo è la specificazione di una sequenza finita di operazioni (dette anche istruzioni) che consente di risolvere tutti i quesiti di una stessa classe o di calcolare il risultato di un'espressione matematica.
Vedere Teorema S m n e Algoritmo
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à.
Vedere Teorema S m n e Funzione ricorsiva primitiva
Lisp
Lisp (List Processor) è una famiglia di linguaggi di programmazione con implementazioni sia compilate sia interpretate, associata nel passato ai progetti di intelligenza artificiale.
Vedere Teorema S m n e Lisp
Numero di Gödel
In logica matematica, una numerazione di Gödel è una funzione che assegna a ciascuna produzione di un linguaggio formale un unico numero naturale chiamato numero di Gödel.
Vedere Teorema S m n e Numero di Gödel
Punto fisso
In matematica, un punto fisso per una funzione definita da un insieme in sé è un elemento coincidente con la sua immagine.
Vedere Teorema S m n e Punto fisso
Stephen Kleene
Fu ancor meglio conosciuto per la fondazione del ramo della logica matematica conosciuta come teoria della ricorsione insieme con Alonzo Church, Kurt Gödel, Alan Turing ed altri, e per l'aver inventato le espressioni regolari.
Vedere Teorema S m n e Stephen Kleene
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.
Vedere Teorema S m n e Teorema di ricorsione di Kleene
Teoria della calcolabilità
La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico.
Vedere Teorema S m n e Teoria della calcolabilità
Valutazione parziale
In Informatica, la valutazione parziale è una tecnica che permette di ottimizzare un programma specializzandolo, in pratica consiste nel fatto di valutare un programma per cui sia nota una parte degli input, in modo tale da ottenere un programma specializzato rispetto a tale input, ma che risulti essere più efficiente dell'originale.
Vedere Teorema S m n e Valutazione parziale
Vedi anche
Teoremi nella teoria della computazione
- Teorema S m n
- Teorema di Rice
Teoria della calcolabilità
- Alacre castoro
- Algoritmo ricorsivo
- Complessità di Kolmogorov
- Computabilità
- Computazione
- Entscheidungsproblem
- Funzione calcolabile
- Funzione di Ackermann
- Funzione ricorsiva
- Funzione ricorsiva primitiva
- Insieme ricorsivamente enumerabile
- Insieme ricorsivo
- LOOP (linguaggio di programmazione)
- Lambda calcolo
- Lemma di König
- Linguaggio ricorsivo
- Logica della computabilità
- Macchina di Turing
- Matematica inversa
- Minimalizzazione
- Predicato T di Kleene
- Problema decisionale
- Problema della terminazione
- Teorema S m n
- Teorema di ricorsione di Kleene
- Teoria della calcolabilità
- Tesi di Church-Turing
Conosciuto come Teorema SMN.