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

Macchina di Turing

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

60 relazioni: Alacre castoro, Alan Turing, Alfred North Whitehead, Algoritmo, Algoritmo di Markov, Alonzo Church, Automa a pila, Automa a stati finiti, Bertrand Russell, Computer cluster, David Hilbert, Douglas Hofstadter, Entscheidungsproblem, Epistemologia, Filosofia della matematica, Formica di Langton, Funzione (informatica), Funzione calcolabile, Funzione ricorsiva, Gödel, Escher, Bach: un'eterna ghirlanda brillante, Gioco della vita, Haskell Curry, Indeterminismo, Informatica, Informatica quantistica, Jacques Herbrand, Java (linguaggio di programmazione), JavaScript, Kaliningrad, Kurt Gödel, Lambda calcolo, Linguaggio di programmazione, Macchina astratta, Macchina di Turing probabilistica, Macchina di Turing universale, Macchina RAM, Macchina RASP, Marvin Minsky, Matematica, MathWorld, Modello matematico, Numero irrazionale, Numero primo, Numero primo di Mersenne, Objective-C, Pi greco, Primo teorema di Shannon, Principia Mathematica, Problema della terminazione, Python, ..., Stanford Encyclopedia of Philosophy, Stato interno, Stephen Kleene, Teoremi di incompletezza di Gödel, Teoria della calcolabilità, Teoria della complessità computazionale, Tesi di Church-Turing, Wilhelm Ackermann, 1900, 1936. Espandi índice (10 più) »

Alacre castoro

Nella teoria della computabilità un alacre castoro (in inglese "busy beaver", letteralmente "castoro indaffarato", dall'espressione colloquiale per indicare una persona industriosa) è una macchina di Turing che ottiene la massima "attività delle operazioni" (come misurato dal numero di passi eseguiti, o dal numero dei simboli non vuoti che essa stampa sul nastro) tra tutte quelle in una determinata categoria.

Nuovo!!: Macchina di Turing e Alacre castoro · Mostra di più »

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!!: Macchina di Turing e Alan Turing · Mostra di più »

Alfred North Whitehead

Si occupò di logica, matematica, epistemologia, teologia e metafisica.

Nuovo!!: Macchina di Turing e Alfred North Whitehead · 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!!: Macchina di 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!!: Macchina di 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!!: Macchina di Turing e Alonzo Church · Mostra di più »

Automa a pila

Un automa a pila o Push Down Automa (PDA) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento.

Nuovo!!: Macchina di Turing e Automa a pila · 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!!: Macchina di Turing e Automa a stati finiti · Mostra di più »

Bertrand Russell

Fu anche un autorevole esponente del movimento pacifista e un divulgatore della filosofia.

Nuovo!!: Macchina di Turing e Bertrand Russell · Mostra di più »

Computer cluster

In informatica un computer cluster, o più semplicemente un cluster (dall'inglese grappolo), è un insieme di computer connessi tra loro tramite una rete telematica.

Nuovo!!: Macchina di Turing e Computer cluster · 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!!: Macchina di Turing e David Hilbert · Mostra di più »

Douglas Hofstadter

Figlio del Premio Nobel per la fisica Robert Hofstadter, si laureò in matematica all'Università di Stanford e conseguì il Ph.D. in fisica nel 1975 presso l'Università dell'Oregon.

Nuovo!!: Macchina di Turing e Douglas Hofstadter · 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!!: Macchina di Turing e Entscheidungsproblem · Mostra di più »

Epistemologia

L'epistemologia (termine, coniato dal filosofo scozzese James Frederick Ferrier, dal greco ἐπιστήμη, epistème, "conoscenza certa" ossia "scienza", e λόγος, logos, "discorso") è quella branca della filosofia contemporanea che si occupa delle condizioni sotto le quali si può avere conoscenza certa o scientifica ovvero dei metodi per raggiungere tale conoscenza.

Nuovo!!: Macchina di Turing e Epistemologia · Mostra di più »

Filosofia della matematica

La filosofia della matematica è la branca della filosofia della scienza che cerca di dare risposta a domande quali: "perché la matematica è utile nella descrizione della natura?", "in quale senso, qualora se ne trovi uno, le entità matematiche (in particolare i numeri) esistono?" "perché e in che modo gli enunciati matematici sono veri?".

Nuovo!!: Macchina di Turing e Filosofia della matematica · Mostra di più »

Formica di Langton

Formica di Langton La formica di Langton è un automa a stati finiti bidimensionale con un insieme di regole molto semplice ma in grado di creare figure molto complicate.

Nuovo!!: Macchina di Turing e Formica di Langton · Mostra di più »

Funzione (informatica)

Una funzione (detta anche routine, subroutine, procedura, sottoprogramma o metodo), in informatica e nell'ambito della programmazione, è un particolare costrutto sintattico di un determinato linguaggio di programmazione che permette di raggruppare, all'interno di un programma, una sequenza di istruzioni in un unico blocco, espletando così una specifica (e in generale più complessa) operazione, azione (o elaborazione) sui dati del programma stesso in modo tale che, a partire da determinati input, restituisca determinati output.

Nuovo!!: Macchina di Turing e Funzione (informatica) · Mostra di più »

Funzione calcolabile

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

Nuovo!!: Macchina di 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!!: Macchina di Turing e Funzione ricorsiva · Mostra di più »

Gödel, Escher, Bach: un'eterna ghirlanda brillante

Gödel, Escher, Bach: un'eterna ghirlanda brillante, talvolta abbreviato in GEB, è un celebre saggio di Douglas Hofstadter, pubblicato la prima volta nel 1979 per Basic Books e vincitore di un Premio Pulitzer.

Nuovo!!: Macchina di Turing e Gödel, Escher, Bach: un'eterna ghirlanda brillante · Mostra di più »

Gioco della vita

Il Gioco della vita (Game of Life o Life in inglese) è un automa cellulare sviluppato dal matematico inglese John Conway sul finire degli anni sessanta.

Nuovo!!: Macchina di Turing e Gioco della vita · Mostra di più »

Haskell Curry

Figlio dell'educatore Samuel Silas Curry, studiò all'Università di Harvard e ricevette il dottorato a Gottinga nel 1930, sotto la supervisione di David Hilbert.

Nuovo!!: Macchina di Turing e Haskell Curry · Mostra di più »

Indeterminismo

L'indeterminismo è l'atteggiamento filosofico che si oppone al determinismo, negando la cogenza assoluta della necessità posta da questo e con l'ammissione della realtà ontologica della contingenza.

Nuovo!!: Macchina di Turing e Indeterminismo · Mostra di più »

Informatica

L'informatica è la scienza applicata che si occupa del trattamento dell'informazione mediante procedure automatizzate.

Nuovo!!: Macchina di Turing e Informatica · Mostra di più »

Informatica quantistica

L'informatica quantistica è l'insieme delle tecniche di calcolo e del loro studio che utilizzano i quanti per memorizzare ed elaborare le informazioni.

Nuovo!!: Macchina di Turing e Informatica quantistica · Mostra di più »

Jacques Herbrand

Laureato a Parigi alla École Normale Supérieure nel 1929 sotto la guida di Ernest Vessiot, dopo un periodo nell'esercito lavorò nel 1931 come ricercatore presso l'Università di Gottinga.

Nuovo!!: Macchina di Turing e Jacques Herbrand · Mostra di più »

Java (linguaggio di programmazione)

In informatica Java è un linguaggio di programmazione ad alto livello, orientato agli oggetti e a tipizzazione statica, specificatamente progettato per essere il più possibile indipendente dalla piattaforma di esecuzione.

Nuovo!!: Macchina di Turing e Java (linguaggio di programmazione) · Mostra di più »

JavaScript

In informatica JavaScript è un linguaggio di scripting orientato agli oggetti e agli eventi, comunemente utilizzato nella programmazione Web lato client per la creazione, in siti web e applicazioni web, di effetti dinamici interattivi tramite funzioni di script invocate da eventi innescati a loro volta in vari modi dall'utente sulla pagina web in uso (mouse, tastiera, caricamento della pagina ecc...). Tali funzioni di script, utilizzati dunque nella logica di presentazione, possono essere opportunamente inserite in file HTML, in pagine JSP o in appositi file separati con estensione.js poi richiamati nella logica di business.

Nuovo!!: Macchina di Turing e JavaScript · Mostra di più »

Kaliningrad

Kaliningrad (in russo Калининград; AFI: kəlʲɪnʲɪnˈgrat; ex denominazione in tedesco: Königsberg; in Yiddish: קעניגסבערג, Kenigsberg; tr. russa: Кёнигсберг, Kjonigsberg; in antico prussiano: Twangste, Kunnegsgarbs, Knigsberg; in latino: Regiomontum) è una città della Russia di abitanti.

Nuovo!!: Macchina di Turing e Kaliningrad · Mostra di più »

Kurt Gödel

Ritenuto uno dei più grandi logici di tutti i tempi insieme ad Aristotele e Gottlob Frege, le sue ricerche ebbero un significativo impatto, oltre che sul pensiero matematico e informatico, anche sul pensiero filosofico del XX secolo.

Nuovo!!: Macchina di Turing e Kurt Gödel · 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!!: Macchina di 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!!: Macchina di Turing e Linguaggio di programmazione · Mostra di più »

Macchina astratta

In informatica il termine macchina astratta indica un modello teorico di hardware o software, in grado di eseguire operazioni, memorizzarne il risultato e seguire il flusso dell'algoritmo.

Nuovo!!: Macchina di Turing e Macchina astratta · Mostra di più »

Macchina di Turing probabilistica

Nella teoria della calcolabilità, una macchina di Turing probabilistica è una macchina di Turing non deterministica che sceglie a caso fra le transizioni disponibili in ogni fase secondo una determinata distribuzione di probabilità.

Nuovo!!: Macchina di Turing e Macchina di Turing probabilistica · 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!!: Macchina di Turing e Macchina di Turing universale · Mostra di più »

Macchina RAM

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

Nuovo!!: Macchina di 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!!: Macchina di Turing e Macchina RASP · Mostra di più »

Marvin Minsky

Fu cofondatore dellArtificial Intelligence Project (divenuto, in seguito, Artificial Intelligence Laboratory) presso il Massachusetts Institute of Technology (MIT) di Cambridge (Massachusetts) e autore di numerosi testi riguardanti l'AI e la filosofia.

Nuovo!!: Macchina di Turing e Marvin Minsky · Mostra di più »

Matematica

La matematica (dal greco μάθημα (máthema), traducibile con i termini "scienza", "conoscenza" o "apprendimento"; μαθηματικός (mathematikós) significa "incline ad apprendere") è la disciplina che studia le quantità (i numeri), lo spazio,.

Nuovo!!: Macchina di Turing e Matematica · Mostra di più »

MathWorld

MathWorld è un'opera enciclopedica on-line sulla matematica sponsorizzata dalla Wolfram Research Inc., una società nota per la creazione e sviluppo del programma informatico Mathematica.

Nuovo!!: Macchina di Turing e MathWorld · Mostra di più »

Modello matematico

Un modello matematico è una rappresentazione quantitativa di un fenomeno naturale.

Nuovo!!: Macchina di Turing e Modello matematico · Mostra di più »

Numero irrazionale

In matematica, un numero irrazionale è un numero reale che non è un numero razionale, cioè non può essere scritto come una frazione a / b con a e b interi e b diverso da 0.

Nuovo!!: Macchina di Turing e Numero irrazionale · Mostra di più »

Numero primo

In matematica, un numero primo (in breve anche primo) è un numero intero positivo che abbia esattamente due divisori distinti.

Nuovo!!: Macchina di Turing e Numero primo · Mostra di più »

Numero primo di Mersenne

In matematica un numero primo di Mersenne è un numero primo esprimibile come: M_p.

Nuovo!!: Macchina di Turing e Numero primo di Mersenne · Mostra di più »

Objective-C

Objective-C, spesso citato anche come Objective C o ObjC o Obj-C, è un linguaggio di programmazione riflessivo orientato agli oggetti, sviluppato da Brad Cox alla metà degli anni ottanta presso la Stepstone Corporation.

Nuovo!!: Macchina di Turing e Objective-C · Mostra di più »

Pi greco

Il Pi greco è una costante matematica, indicata con la lettera greca \pi (pi), scelta in quanto iniziale di περιφέρεια (perifereia), circonferenza in greco.

Nuovo!!: Macchina di Turing e Pi greco · Mostra di più »

Primo teorema di Shannon

Nella teoria dell'informazione, il primo teorema di Shannon (o teorema della codifica di sorgente), stabilisce dei limiti alla massima compressione possibile di un insieme di dati e definisce il significato operativo dell'entropia.

Nuovo!!: Macchina di Turing e Primo teorema di Shannon · Mostra di più »

Principia Mathematica

Principia Mathematica è un'opera sui fondamenti logici della matematica scritta da Alfred North Whitehead e Bertrand Russell.

Nuovo!!: Macchina di Turing e Principia Mathematica · Mostra di più »

Problema della terminazione

Il problema della terminazione (dall'inglese Halting problem, tradotto anche con problema dell'arresto o problema della fermata) chiede se sia sempre possibile, descritto un algoritmo e un determinato input finito, stabilire se l'algoritmo in questione termini o continui la sua esecuzione all'infinito.

Nuovo!!: Macchina di Turing e Problema della terminazione · Mostra di più »

Python

Python è un linguaggio di programmazione ad alto livello, orientato agli oggetti, adatto, tra gli altri usi, per sviluppare applicazioni distribuite, scripting, computazione numerica e system testing.

Nuovo!!: Macchina di Turing e Python · Mostra di più »

Stanford Encyclopedia of Philosophy

La Stanford Encyclopedia of Philosophy (SEP) è un'enciclopedia specialistica di filosofia, on-line e gratuita, curata dalla Università di Stanford.

Nuovo!!: Macchina di Turing e Stanford Encyclopedia of Philosophy · Mostra di più »

Stato interno

Nell'informatica, lo stato interno (o configurazione) di un sistema è la condizione in cui si trovano le sue componenti ad un determinato istante di tempo t. Si veda ad esempio la macchina di Turing.

Nuovo!!: Macchina di Turing e Stato interno · Mostra di più »

Stephen Kleene

Kleene fu ancor meglio conosciuto per la fondazione del ramo della logica matematica conosciuta come teoria della ricorsione insieme con Alonzo Church, Kurt Gödel, Alan Turing ed altri, e per l'aver inventato le espressioni regolari.

Nuovo!!: Macchina di Turing e Stephen Kleene · Mostra di più »

Teoremi di incompletezza di Gödel

In logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1931.

Nuovo!!: Macchina di Turing e Teoremi di incompletezza di Gödel · 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!!: Macchina di Turing e Teoria della calcolabilità · Mostra di più »

Teoria della complessità computazionale

In informatica, la teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.

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

Wilhelm Ackermann

Ackermann fu premiato con un Ph.D. all'Università di Gottinga nel 1925 per la sua tesi Begründung sul "Tertium non datur" mittels der Hilbertschen Theorie der Widerspruchsfreiheit che doveva essere una prova della consistenza dell'aritmetica senza l'induzione di Peano.

Nuovo!!: Macchina di Turing e Wilhelm Ackermann · Mostra di più »

1900

Nessuna descrizione.

Nuovo!!: Macchina di Turing e 1900 · Mostra di più »

1936

Nessuna descrizione.

Nuovo!!: Macchina di Turing e 1936 · Mostra di più »

Riorienta qui:

Macchina di Turing deterministica, Macchina di Turing non deterministica, Macchine di Turing.

UscenteArrivo
Ehi! Siamo su Facebook ora! »