Indice
15 relazioni: Emil Leon Post, Equazione diofantea, Insieme ricorsivo, Linguaggio ricorsivamente enumerabile, Logica matematica, Ordinale limite, Presentazione di un gruppo, Principio di Markov, Teorema di completezza di Gödel, Teorema di Matijasevič, Teorema di ricorsione di Kleene, Teoremi di incompletezza di Gödel, Teoria, Teoria degli insiemi, Turing riduzione.
Emil Leon Post
Nacque in una famiglia ebrea polacca che emigrò in America quando era ancora bambino. Dopo aver completato il PhD in matematica presso la Columbia University, fece un post-dottorato all'Università di Princeton.
Vedere Insieme ricorsivamente enumerabile e Emil Leon Post
Equazione diofantea
In matematica, unequazione diofantea (chiamata anche equazione diofantina) è un'equazione in una o più incognite con coefficienti interi di cui si ricercano le soluzioni intere.
Vedere Insieme ricorsivamente enumerabile e Equazione diofantea
Insieme ricorsivo
Nella teoria della calcolabilità un insieme ricorsivo (o insieme decidibile) è intuitivamente un insieme di numeri naturali, per cui è possibile costruire un algoritmo che in un tempo finito (ma a priori non predeterminato) sia in grado, dato un qualunque numero naturale, di stabilire se esso appartiene o no all'insieme.
Vedere Insieme ricorsivamente enumerabile e Insieme ricorsivo
Linguaggio ricorsivamente enumerabile
Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f di cui A è il codominio. Essendoci una corrispondenza biunivoca tra l'insieme delle funzioni calcolabili e l'insieme dei programmi in un qualsiasi linguaggio di programmazione, un insieme è quindi ricorsivamente enumerabile se è possibile generare i suoi elementi attraverso un programma per calcolatore (per la tesi di Church-Turing è indifferente il linguaggio di programmazione scelto).
Vedere Insieme ricorsivamente enumerabile e Linguaggio ricorsivamente enumerabile
Logica matematica
La logica matematica è il settore della matematica che studia i sistemi formali dal punto di vista del modo di codificare i concetti intuitivi della dimostrazione e di computazione come parte dei fondamenti della matematica.
Vedere Insieme ricorsivamente enumerabile e Logica matematica
Ordinale limite
Un ordinale limite è un numero ordinale che non è né un ordinale successore né l'insieme vuoto. Intuitivamente si tratta di ordinali che non possono essere raggiunti attraverso l'operazione di successione S. In termini precisi diciamo che λ è un ordinale limite se per ogni α 2 (per maggiori informazioni sull'aritmetica degli ordinali vedere la voce numero ordinale).
Vedere Insieme ricorsivamente enumerabile e Ordinale limite
Presentazione di un gruppo
In matematica, e in particolare in algebra astratta, una presentazione di un gruppo è una particolare definizione ottenuta mediante l'elenco dei generatori del gruppo, ovvero degli elementi il cui prodotto combinato dà origine a tutti gli elementi del gruppo, e delle relazioni tra i vari elementi.
Vedere Insieme ricorsivamente enumerabile e Presentazione di un gruppo
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.
Vedere Insieme ricorsivamente enumerabile e Principio di Markov
Teorema di completezza di Gödel
Il teorema di completezza di Gödel è un teorema fondamentale della logica matematica ottenuto dal logico Kurt Gödel nel 1929. Esso stabilisce una corrispondenza tra validità logica e dimostrabilità logica nella logica del primo ordine.
Vedere Insieme ricorsivamente enumerabile e Teorema di completezza di Gödel
Teorema di Matijasevič
Il teorema di Matijasevič, dimostrato nel 1970 da Jurij Vladimirovič Matijasevič, implica che il decimo problema di Hilbert è irrisolvibile.
Vedere Insieme ricorsivamente enumerabile e Teorema di Matijasevič
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 Insieme ricorsivamente enumerabile e Teorema di ricorsione di Kleene
Teoremi di incompletezza di Gödel
In logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1930. Gödel enunciò il suo primo teorema di incompletezza in una tavola rotonda a margine della Seconda Conferenza sull'Epistemologia delle Scienze esatte di Königsberg.
Vedere Insieme ricorsivamente enumerabile e Teoremi di incompletezza di Gödel
Teoria
Il termine teoria (dal greco θεωρέω theoréo "guardo, osservo", composto da θέα thèa Il termine è connesso con θέα théa, "spettacolo", a sua volta derivato da θαῦμα thâuma, "visione".
Vedere Insieme ricorsivamente enumerabile e Teoria
Teoria degli insiemi
La teoria degli insiemi è una teoria matematica posta ai fondamenti della matematica stessa, collocandosi nell'ambito della logica matematica.
Vedere Insieme ricorsivamente enumerabile e Teoria degli insiemi
Turing riduzione
In teoria della computabilità, una Turing-riduzione da un problema decisionale A ad un problema decisionale B è una macchina oracolo che decide il problema A dato un oracolo per B (Rogers 1967, Soare 1987).
Vedere Insieme ricorsivamente enumerabile e Turing riduzione
Conosciuto come Ricorsivamente enumerabile.