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

Funzione calcolabile

Indice Funzione calcolabile

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

11 relazioni: Algoritmo, Algoritmo di Markov, Classe (matematica), Funzione parziale, Funzione ricorsiva, Lambda calcolo, Macchina di Turing, Macchina URM, Teoria della calcolabilità, Tesi di Church-Turing, Turing equivalenza.

Algoritmo

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

Nuovo!!: Funzione calcolabile 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!!: Funzione calcolabile e Algoritmo di Markov · 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!!: Funzione calcolabile e Classe (matematica) · Mostra di più »

Funzione parziale

Una funzione parziale In matematica, si dice funzione parziale f:A \rightarrow B un sottoinsieme di A \times B, cioè una relazione binaria tra A e B, tale che.

Nuovo!!: Funzione calcolabile e Funzione parziale · 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!!: Funzione calcolabile 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!!: Funzione calcolabile e Lambda calcolo · 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!!: Funzione calcolabile e Macchina di Turing · 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!!: Funzione calcolabile e Macchina URM · 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!!: Funzione calcolabile e Teoria della calcolabilità · 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!!: Funzione calcolabile e Tesi di Church-Turing · 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!!: Funzione calcolabile e Turing equivalenza · Mostra di più »

UscenteArrivo
Ehi! Siamo su Facebook ora! »