Tesi di Church-Turing e Turing equivalenza

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

Differenza tra Tesi di Church-Turing e Turing equivalenza

Tesi di Church-Turing vs. Turing equivalenza

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. La Turing equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu).

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 Tesi di Church-Turing · Algoritmo di Markov e Turing equivalenza · 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 Tesi di Church-Turing · Automa a stati finiti e Turing equivalenza · 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).

Compilatore e Tesi di Church-Turing · Compilatore e Turing equivalenza · 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.

Espressione regolare e Tesi di Church-Turing · Espressione regolare e Turing equivalenza · 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 Tesi di Church-Turing · Funzione ricorsiva e Turing equivalenza · 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 Tesi di Church-Turing · Lambda calcolo e Turing equivalenza · 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 Tesi di Church-Turing · Linguaggio di programmazione e Turing equivalenza · 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.

Macchina che termina sempre e Tesi di Church-Turing · Macchina che termina sempre e Turing equivalenza · 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.

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

Programmazione funzionale e Tesi di Church-Turing · Programmazione funzionale e Turing equivalenza · 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.

Programmazione imperativa e Tesi di Church-Turing · Programmazione imperativa e Turing equivalenza · Mostra di più »