Macchina di Turing e Tesi di Church-Turing

Scorciatoie: Differenze, Analogie, Jaccard somiglianza Coefficiente, Riferimenti.

Differenza tra Macchina di Turing e Tesi di Church-Turing

Macchina di Turing vs. Tesi di Church-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. 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.

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.

Alan Turing e Macchina di Turing · Alan Turing e Tesi di Church-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.

Algoritmo e Macchina di Turing · Algoritmo e Tesi di Church-Turing · 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.

Algoritmo di Markov e Macchina di Turing · Algoritmo di Markov e Tesi di Church-Turing · Mostra di più »

Alonzo Church

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

Alonzo Church e Macchina di Turing · Alonzo Church e Tesi di Church-Turing · 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.

Automa a stati finiti e Macchina di Turing · Automa a stati finiti e Tesi di Church-Turing · 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.

David Hilbert e Macchina di Turing · David Hilbert e Tesi di Church-Turing · 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.

Entscheidungsproblem e Macchina di Turing · Entscheidungsproblem e Tesi di Church-Turing · Mostra di più »

Funzione calcolabile

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

Funzione calcolabile e Macchina di Turing · Funzione calcolabile e Tesi di Church-Turing · 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.

Funzione ricorsiva e Macchina di Turing · Funzione ricorsiva e Tesi di Church-Turing · 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.

Lambda calcolo e Macchina di Turing · Lambda calcolo e Tesi di Church-Turing · 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.

Linguaggio di programmazione e Macchina di Turing · Linguaggio di programmazione e Tesi di Church-Turing · Mostra di più »

Macchina RAM

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

Macchina RAM e Macchina di Turing · Macchina RAM e Tesi di Church-Turing · 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.

Macchina RASP e Macchina di Turing · Macchina RASP e Tesi di Church-Turing · 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.

Macchina di Turing e Teoria della calcolabilità · Teoria della calcolabilità e Tesi di Church-Turing · Mostra di più »