l'accesso più veloce di browser!
13 relazioni: Algoritmo di Markov, Automa a stati finiti, Compilatore, Espressione regolare, Funzione ricorsiva, Lambda calcolo, Linguaggio di programmazione, Macchina che termina sempre, Macchina di Turing universale, Macchina URM, Programmazione funzionale, Programmazione imperativa, Tesi di Church-Turing.
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!!: Turing equivalenza e Algoritmo di Markov · 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!!: Turing equivalenza e Automa a stati finiti · 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!!: Turing equivalenza e Compilatore · 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!!: Turing equivalenza e Espressione regolare · 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!!: Turing equivalenza 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!!: Turing equivalenza 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!!: Turing equivalenza 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!!: Turing equivalenza e Macchina che termina sempre · Mostra di più »
Macchina di Turing universale
Una rappresentazione grafica della macchina di Turing In teoria della computazione, si dice macchina di Turing universale (talvolta abbreviato in MTU) una macchina di Turing capace di simulare le evoluzioni di ogni macchina di Turing.
Nuovo!!: Turing equivalenza e Macchina di Turing universale · 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!!: Turing equivalenza e Macchina URM · 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!!: Turing equivalenza 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!!: Turing equivalenza e Programmazione imperativa · Mostra di più »
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.
Nuovo!!: Turing equivalenza e Tesi di Church-Turing · Mostra di più »
