Logo
Unionpedia
Comunicazione
Disponibile su Google Play
Nuovo! Scarica Unionpedia sul tuo dispositivo Android™!
Scaricare
l'accesso più veloce di browser!
 

Tesi di Church-Turing

Indice 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.

30 relazioni: Alan Turing, Algoritmo, Algoritmo di Markov, Alonzo Church, Anni 1930, Anni 1940, Automa a stati finiti, C (linguaggio), Calcolo (matematica), Classe (matematica), Compilatore, Computer, David Hilbert, Emil Leon Post, Entscheidungsproblem, Espressione regolare, Funzione calcolabile, Funzione ricorsiva, Lambda calcolo, Linguaggio di programmazione, Macchina che termina sempre, Macchina di Turing, Macchina RAM, Macchina RASP, Macchina URM, Pascal (linguaggio di programmazione), Programmazione funzionale, Programmazione imperativa, Teoria della calcolabilità, Turing equivalenza.

Alan Turing

Il suo lavoro ebbe vasta influenza sullo sviluppo dell'informatica, grazie alla sua formalizzazione dei concetti di algoritmo e calcolo mediante la macchina di Turing, che a sua volta ha svolto un ruolo significativo nella creazione del moderno computer.

Nuovo!!: Tesi di Church-Turing e Alan Turing · Mostra di più »

Algoritmo

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.

Nuovo!!: Tesi di Church-Turing e Algoritmo · Mostra di più »

Algoritmo di Markov

In logica matematica, un algoritmo di Markov è un sistema di riscrittura di stringhe (sistema semi-Thue) che si basa su regole analoghe a quelle grammaticali.

Nuovo!!: Tesi di Church-Turing e Algoritmo di Markov · Mostra di più »

Alonzo Church

Ha dato importanti contributi allo sviluppo della logica matematica e ai fondamenti dell'informatica teorica.

Nuovo!!: Tesi di Church-Turing e Alonzo Church · Mostra di più »

Anni 1930

Nessuna descrizione.

Nuovo!!: Tesi di Church-Turing e Anni 1930 · Mostra di più »

Anni 1940

Nessuna descrizione.

Nuovo!!: Tesi di Church-Turing e Anni 1940 · Mostra di più »

Automa a stati finiti

Un automa a stati finiti (ASF o FSA, dall'inglese Finite State Automata) o macchina a stati finiti (FSM dall'inglese Finite State Machine) è un tipo di automa che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi.

Nuovo!!: Tesi di Church-Turing e Automa a stati finiti · Mostra di più »

C (linguaggio)

C è un linguaggio di programmazione imperativo di natura procedurale.

Nuovo!!: Tesi di Church-Turing e C (linguaggio) · Mostra di più »

Calcolo (matematica)

Il calcolo è una facoltà o processo mentale cognitivo su base volontaria che trasforma uno o più dati in ingresso in uno o più risultati.

Nuovo!!: Tesi di Church-Turing e Calcolo (matematica) · Mostra di più »

Classe (matematica)

Nella moderna teoria degli insiemi, per classe si intende una generica collezione di oggetti che possono essere univocamente identificati (per esempio, tramite una proprietà che li accomuni).

Nuovo!!: Tesi di Church-Turing e Classe (matematica) · Mostra di più »

Compilatore

Un compilatore è un programma informatico che traduce una serie di istruzioni scritte in un determinato linguaggio di programmazione (codice sorgente) in istruzioni di un altro linguaggio (codice oggetto).

Nuovo!!: Tesi di Church-Turing e Compilatore · Mostra di più »

Computer

Un computer (pronuncia italiana), in italiano anche elaboratore (vedi «aspetti linguistici»), è una macchina automatizzata in grado di eseguire complessi calcoli matematici ed eventualmente altri tipi di elaborazioni dati.

Nuovo!!: Tesi di Church-Turing e Computer · Mostra di più »

David Hilbert

È stato uno dei più eminenti ed influenti matematici del periodo a cavallo tra il XIX secolo e il XX secolo.

Nuovo!!: Tesi di Church-Turing e David Hilbert · Mostra di più »

Emil Leon Post

Nacque in una famiglia ebrea polacca che emigrò in America quando era ancora bambino.

Nuovo!!: Tesi di Church-Turing e Emil Leon Post · Mostra di più »

Entscheidungsproblem

L'Entscheidungsproblem (in italiano: "problema della decisione") è un problema posto da David Hilbert nel 1928, all'interno dell'allora fervente dibattito sui fondamenti della matematica.

Nuovo!!: Tesi di Church-Turing e Entscheidungsproblem · Mostra di più »

Espressione regolare

Una espressione regolare (in lingua inglese regular expression o, in forma abbreviata, regexp, regex o RE) è una sequenza di simboli (quindi una stringa) che identifica un insieme di stringhe.

Nuovo!!: Tesi di Church-Turing e Espressione regolare · Mostra di più »

Funzione calcolabile

Le funzioni calcolabili sono il principale oggetto di studio della teoria della calcolabilità.

Nuovo!!: Tesi di Church-Turing e Funzione calcolabile · Mostra di più »

Funzione ricorsiva

Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo.

Nuovo!!: Tesi di Church-Turing e Funzione ricorsiva · Mostra di più »

Lambda calcolo

Il lambda calcolo o λ-calcolo è un sistema formale definito dal matematico Alonzo Church, sviluppato per analizzare formalmente le funzioni e il loro calcolo.

Nuovo!!: Tesi di Church-Turing e Lambda calcolo · Mostra di più »

Linguaggio di programmazione

Un linguaggio di programmazione, in informatica, è un linguaggio formale che specifica un insieme di istruzioni che possono essere usate per produrre dati in output.

Nuovo!!: Tesi di Church-Turing e Linguaggio di programmazione · Mostra di più »

Macchina che termina sempre

Nella teoria della computabilità, una macchina che termina sempre — chiamata anche un decider o macchina di Turing totale — è un particolare di tipo di macchina di Turing che, al contrario del modello generale, è garantito che termini per ogni input.

Nuovo!!: Tesi di Church-Turing e Macchina che termina sempre · 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!!: Tesi di Church-Turing e Macchina di Turing · Mostra di più »

Macchina RAM

Il modello della macchina RAM è uno strumento classico per l'analisi delle procedure sequenziali.

Nuovo!!: Tesi di Church-Turing e Macchina RAM · Mostra di più »

Macchina RASP

La Macchina RASP (Random Access Stored Program) è un calcolatore primitivo ideale che, sulla base dell'architettura di von Neumann, elabora le informazioni ricevute in entrata da un nastro di input in una unità centrale (CPU), grazie al supporto di una memoria interna ad accesso casuale (RAM), e stampa i risultati su un nastro di output.

Nuovo!!: Tesi di Church-Turing e Macchina RASP · Mostra di più »

Macchina URM

La URM (acronimo di Unlimited Register Machine) è una idealizzazione matematica di un computer basata su di una macchina inventata nel 1963 da J. C. Shepherdson e H. E. Sturgis.

Nuovo!!: Tesi di Church-Turing e Macchina URM · Mostra di più »

Pascal (linguaggio di programmazione)

Il Pascal, in informatica, è un linguaggio di programmazione creato da Niklaus Wirth e basato sul linguaggio ALGOL; il nome è dedicato a Blaise Pascal che inventò nel 1645 la Pascalina, considerata la prima calcolatrice.

Nuovo!!: Tesi di Church-Turing e Pascal (linguaggio di programmazione) · Mostra di più »

Programmazione funzionale

In informatica la programmazione funzionale è un paradigma di programmazione in cui il flusso di esecuzione del programma assume la forma di una serie di valutazioni di funzioni matematiche.

Nuovo!!: Tesi di Church-Turing e Programmazione funzionale · Mostra di più »

Programmazione imperativa

In informatica, la programmazione imperativa è un paradigma di programmazione secondo cui un programma viene inteso come un insieme di istruzioni (dette anche direttive o comandi), ciascuna delle quali può essere pensata come un "ordine" che viene impartito alla macchina virtuale del linguaggio di programmazione utilizzato.

Nuovo!!: Tesi di Church-Turing e Programmazione imperativa · 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!!: Tesi di Church-Turing e Teoria della calcolabilità · Mostra di più »

Turing equivalenza

La Turing equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu).

Nuovo!!: Tesi di Church-Turing e Turing equivalenza · Mostra di più »

Riorienta qui:

Congettura di Church-Turing, Tesi di church turing.

UscenteArrivo
Ehi! Siamo su Facebook ora! »