l'accesso più veloce di browser!
118 relazioni: Abstract state machine, Alacre castoro, Alan Turing, Algoritmo, Alonzo Church, Aree della matematica, Automa (informatica), Automa a stati finiti, Automa cellulare, Automa lineare limitato, Bernard Bolzano, Blade server, Bomba (calcolatore), BPP (complessità), BQP (complessità), Brainfuck, Calcolatrice, Calcolo distribuito, Cedric (computer), Cibernetica, Classe di complessità, Classi di complessità P e NP, Complessità dei circuiti, Complessità temporale, Computabilità, Computer, Computer a DNA, Computer analogico, Connessionismo, Corrado Böhm, COW (linguaggio di programmazione), Crittografia nella seconda guerra mondiale, Cronologia dei computer fino al 1950, Cronologia della matematica, David Deutsch, Dimostrazione a conoscenza zero, DLOGTIME, E (complessità), EXPSPACE, EXPTIME, Filosofia della matematica, Formica di Langton, Funzionalismo (filosofia della mente), Funzione calcolabile, Funzione ricorsiva, Funzione ricorsiva primitiva, Gerarchia di Chomsky, Glossario delle strutture matematiche, GPGPU, Grammatica formale, ..., Informatica, Informatica quantistica, Insieme ricorsivamente enumerabile, Intelligenza artificiale, Jerry Fodor, JFLAP, L (complessità), La mente nuova dell'imperatore, Lev Manovich, Lewis Carroll, Linguaggio dipendente dal contesto, Linguaggio formale, Linguaggio ricorsivo, Linguaggio Wolfram, Logo Google, Macchina astratta, Macchina che termina sempre, Macchina di Turing probabilistica, Macchina di Turing quantistica, Macchina di Turing universale, Macchina Gödel-incompleta, Macchina RAM, Macchina URM, Matematica, MDT, MT, NC (complessità), NL (complessità), NP (complessità), NP-difficile, One instruction set computer, P (complessità), P (disambigua), Problema di funzione, PSPACE, Qualia, Scienze cognitive, Sharp-P, Sharp-P-completo, Sistema (fisica), Small Scale Experimental Machine, Stanza cinese, Stato interno, Storia dell'informatica, Storia della matematica, Storia della nozione di funzione matematica, Stringa (linguaggi formali), Struttura relazionale, Teorema dello speedup, Teorema dello speedup di Blum, Teorema di Böhm-Jacopini, Teorema di Church, Teorema di Cook-Levin, Teorema di Savitch, Teorema di Turing, Teoremi di incompletezza di Gödel, Teoria assiomatica degli insiemi, Teoria degli insiemi, Teoria della calcolabilità, Teoria della complessità computazionale, Tesi di Church-Turing, Test di Turing, The Imitation Game, TM, Warren McCulloch, ZPP (complessità), 2-EXPTIME, 4GL. Espandi índice (68 più) »
Abstract state machine
Nel campo dell'informatica il termine Abstract State Machine (letteralmente macchina a stati astratti) o ASM è usato spesso come sinonimo di macchina a stati finiti per quanto riguarda gli algoritmi astratti (come l'ordinamento, la ricerca, ecc.). Una particolare teoria sull'utilizzo degli ASM per la specifica formale è stata sviluppata da Yuri Gurevich.
Nuovo!!: Macchina di Turing e Abstract state machine · Mostra di 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ù »
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ù »
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ù »
Aree della matematica
La matematica, nel corso della sua storia, è diventata una materia estremamente diversificata, di conseguenza si è reso necessario categorizzarne le aree.
Nuovo!!: Macchina di Turing e Aree della matematica · Mostra di più »
Automa (informatica)
In teoria dei sistemi dinamici, un automa è un sistema dinamico discreto (nella scansione del tempo e nella descrizione del suo stato) e invariante (il sistema si comporta alla stessa maniera indipendentemente dall'istante di tempo in cui agisce).
Nuovo!!: Macchina di Turing e Automa (informatica) · 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ù »
Automa cellulare
Un automa cellulare (dall'inglese Cellular automaton o Cellular automata, abbrev. CA) è un modello matematico usato per descrivere l'evoluzione di sistemi complessi discreti, studiati in teoria della computazione, matematica, fisica e biologia.
Nuovo!!: Macchina di Turing e Automa cellulare · Mostra di più »
Automa lineare limitato
Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input.
Nuovo!!: Macchina di Turing e Automa lineare limitato · Mostra di più »
Bernard Bolzano
Bernard Bolzano.
Nuovo!!: Macchina di Turing e Bernard Bolzano · Mostra di più »
Blade server
Un blade server è un server auto-contenuto pensato per minimizzare l'occupazione di spazio.
Nuovo!!: Macchina di Turing e Blade server · Mostra di più »
Bomba (calcolatore)
La Bomba (da cryptological bombe, nome inglese derivato dal polacco bomba kryptologiczna) fu una speciale macchina calcolatrice utilizzata dapprima dal controspionaggio polacco ed in seguito da quello inglese per decifrare i messaggi segreti tedeschi codificati con la macchina Enigma, ideata da Arthur Scherbius.
Nuovo!!: Macchina di Turing e Bomba (calcolatore) · Mostra di più »
BPP (complessità)
Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta.
Nuovo!!: Macchina di Turing e BPP (complessità) · Mostra di più »
BQP (complessità)
Nella teoria della complessità computazionale, BQP (Bounded-error Quantum Polynomial-time, "tempo polinomiale quantistico con errore limitato") è una classe di complessità a cui appartengono quei problemi che richiedono un tempo polinomiale da parte di un computer quantistico per avere una soluzione corretta con probabilità maggiore o uguale a 2/3 e quindi, corrispondentemente, con una probabilità di errore minore o uguale a 1/3.
Nuovo!!: Macchina di Turing e BQP (complessità) · Mostra di più »
Brainfuck
Brainfuck è un linguaggio di programmazione esoterico per computer, creato da Urban Müller intorno al 1993.
Nuovo!!: Macchina di Turing e Brainfuck · Mostra di più »
Calcolatrice
Una calcolatrice è una macchina da calcolo automatizzata, di dimensioni fisiche contenute, in grado di eseguire calcoli matematici e dedicata a tale tipologia di elaborazione dati.
Nuovo!!: Macchina di Turing e Calcolatrice · Mostra di più »
Calcolo distribuito
Il calcolo distribuito è un campo dell'informatica che studia i sistemi distribuiti.
Nuovo!!: Macchina di Turing e Calcolo distribuito · Mostra di più »
Cedric (computer)
Cedric è un prototipo di computer a nanotubi di carbonio.
Nuovo!!: Macchina di Turing e Cedric (computer) · Mostra di più »
Cibernetica
Il termine cibernetica indica un vasto programma di ricerca interdisciplinare, rivolto allo studio matematico unitario degli organismi viventi e, più in generale, di sistemi, sia naturali che artificiali.
Nuovo!!: Macchina di Turing e Cibernetica · Mostra di più »
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.
Nuovo!!: Macchina di Turing e Classe di complessità · Mostra di più »
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.
Nuovo!!: Macchina di Turing e Classi di complessità P e NP · Mostra di più »
Complessità dei circuiti
In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano.
Nuovo!!: Macchina di Turing e Complessità dei circuiti · Mostra di più »
Complessità temporale
In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.
Nuovo!!: Macchina di Turing e Complessità temporale · Mostra di più »
Computabilità
La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi.
Nuovo!!: Macchina di Turing e Computabilità · Mostra di più »
Computer
Un computer (pronuncia italiana), in italiano anche elaboratore (vedi «aspetti linguistici»), è una macchina automatizzata in grado di eseguire complessi calcoli matematici ed eventualmente altri tipi di elaborazioni dati.
Nuovo!!: Macchina di Turing e Computer · Mostra di più »
Computer a DNA
Con il termine generico di computer a DNA ci si riferisce ad una forma di computer che utilizza il DNA (e quindi la biochimica e la biologia molecolare) al posto dei tradizionali computer a base di silicio.
Nuovo!!: Macchina di Turing e Computer a DNA · Mostra di più »
Computer analogico
Un computer analogico è un computer che sfrutta fenomeni fisici associati a variabili continue per modellare il problema da risolvere; per esempio si possono usare quantità elettriche, idrauliche o meccaniche.
Nuovo!!: Macchina di Turing e Computer analogico · Mostra di più »
Connessionismo
Il connessionismo è un approccio delle scienze cognitive che spera di spiegare la mente usando reti neurali artificiali.
Nuovo!!: Macchina di Turing e Connessionismo · Mostra di più »
Corrado Böhm
Studente di ingegneria, nel 1942 lascia l'Italia per la Svizzera e continua gli studi presso l'École Polytechnique Fédérale di Losanna, dove nel 1946 ottiene il diploma di ingegnere elettronico.
Nuovo!!: Macchina di Turing e Corrado Böhm · Mostra di più »
COW (linguaggio di programmazione)
COW è un linguaggio di programmazione esoterico, creato all'inizio del 2003 da Alex van Oostenrijk e Martijn van Beek.
Nuovo!!: Macchina di Turing e COW (linguaggio di programmazione) · Mostra di più »
Crittografia nella seconda guerra mondiale
La crittografia nella seconda guerra mondiale riguarda i mezzi e i metodi, adottati dalle principali potenze che presero parte al secondo conflitto mondiale, in grado di impossibilitare i propri nemici a decifrare, e quindi comprendere, i propri messaggi.
Nuovo!!: Macchina di Turing e Crittografia nella seconda guerra mondiale · Mostra di più »
Cronologia dei computer fino al 1950
Questo articolo presenta una cronologia di eventi nella storia dei computer dall'Antichità al 1950.
Nuovo!!: Macchina di Turing e Cronologia dei computer fino al 1950 · Mostra di più »
Cronologia della matematica
Una cronologia degli sviluppi più rilevanti della matematica.
Nuovo!!: Macchina di Turing e Cronologia della matematica · Mostra di più »
David Deutsch
Premiato con il premio Dirac nel 1998, è professore presso il dipartimento di fisica atomica e laser presso il centro per la computazione quantistica, nel laboratorio Clarendon dell'Università di Oxford.
Nuovo!!: Macchina di Turing e David Deutsch · Mostra di più »
Dimostrazione a conoscenza zero
In crittografia una dimostrazione a conoscenza zero o protocollo a conoscenza zero è un metodo interattivo utilizzato da un soggetto per dimostrare ad un altro soggetto che una affermazione (solitamente matematica) è vera, senza rivelare nient'altro oltre alla veridicità della stessa.
Nuovo!!: Macchina di Turing e Dimostrazione a conoscenza zero · Mostra di più »
DLOGTIME
Nella teoria della complessità computazionale DLOGTIME è la classe di complessità di tutti i problemi computazionali risolvibili in una quantità logaritmica di tempo computazionale da una macchina di Turing deterministica.
Nuovo!!: Macchina di Turing e DLOGTIME · Mostra di più »
E (complessità)
Nella teoria della complessità computazionale, la classe di complessità E è l'insieme di problemi decisionali che possono essere risolti da una macchina deterministica di Turing nel tempo 2O(n) ed è perciò uguale alla classe di complessità DTIME(2O(n)).
Nuovo!!: Macchina di Turing e E (complessità) · Mostra di più »
EXPSPACE
Nella teoria della complessità, EXPSPACE è l'insieme di tutti i problemi di decisione risolvibili da una macchina deterministica di Turing nello spazio O(2p(n)), dove p(n) è una funzione polinomiale di n. (Alcuni autori restringono p(n) all'essere una funzione lineare, ma la maggior parte degli autori invece chiamano la classe risultante ESPACE.) Se usiamo invece una macchina non deterministica, otteniamo la classe NEXPSPACE, che è uguale a EXPSPACE per il teorema di Savitch.
Nuovo!!: Macchina di Turing e EXPSPACE · Mostra di più »
EXPTIME
Nella teoria della complessità computazionale la classe di complessità EXPTIME (a volte chiamata EXP, da Exponential Time, "tempo esponenziale"), è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(2p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, Sappiamo che e inoltre, dal teorema della gerarchia temporale e dal teorema della gerarchia spaziale, che così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti credono che tutte le inclusioni siano corrette.
Nuovo!!: Macchina di Turing e EXPTIME · 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ù »
Funzionalismo (filosofia della mente)
Il funzionalismo è una teoria della mente, sviluppata da Hilary Putnam nel 1950, in contrapposizione al riduzionismo materialista (ad es. la teoria dell'identità) e al comportamentismo per superare la diatriba mente-corpo in filosofia della mente contemporanea.
Nuovo!!: Macchina di Turing e Funzionalismo (filosofia della mente) · 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ù »
Funzione ricorsiva primitiva
Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità.
Nuovo!!: Macchina di Turing e Funzione ricorsiva primitiva · Mostra di più »
Gerarchia di Chomsky
La gerarchia di Chomsky è un insieme di classi di grammatiche formali che generano linguaggi formali.
Nuovo!!: Macchina di Turing e Gerarchia di Chomsky · Mostra di più »
Glossario delle strutture matematiche
Questo glossario delle strutture matematiche raccoglie, le principali strutture utilizzate in matematica (strutture algebriche, relazionali, topologiche, ecc.) e le tipologie di spazi su cui esse si basano.
Nuovo!!: Macchina di Turing e Glossario delle strutture matematiche · Mostra di più »
GPGPU
In informatica per GPGPU, sigla di general-purpose computing on graphics processing units (letteralmente "calcolo a scopo generale su unità di elaborazione grafica"), si intende l'uso di un'unità di elaborazione grafica (GPU) per scopi diversi dal tradizionale utilizzo nella grafica computerizzata.
Nuovo!!: Macchina di Turing e GPGPU · Mostra di più »
Grammatica formale
In teoria dei linguaggi formali una grammatica formale è una struttura astratta che descrive un linguaggio formale in modo preciso, è cioè un sistema di regole che delineano matematicamente un insieme (di solito infinito) di sequenze finite di simboli (stringhe) appartenenti ad un alfabeto anch'esso finito.
Nuovo!!: Macchina di Turing e Grammatica formale · 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ù »
Insieme ricorsivamente enumerabile
Nella teoria della calcolabilità esistono due definizioni di insieme ricorsivamente enumerabile (spesso abbreviato in insieme r.e.) o insieme semi-decidibile.
Nuovo!!: Macchina di Turing e Insieme ricorsivamente enumerabile · Mostra di più »
Intelligenza artificiale
Definizioni specifiche possono essere date focalizzandosi o sui processi interni di ragionamento o sul comportamento esterno del sistema intelligente ed utilizzando come misura di efficacia o la somiglianza con il comportamento umano o con un comportamento ideale, detto razionale.
Nuovo!!: Macchina di Turing e Intelligenza artificiale · Mostra di più »
Jerry Fodor
Scienziato cognitivo e filosofo del linguaggio presso la Rutgers University, New Jersey.
Nuovo!!: Macchina di Turing e Jerry Fodor · Mostra di più »
JFLAP
JFLAP è un software freeware per lo studio dell'informatica teorica, in particolare gli automi a stati finiti e i linguaggi formali.
Nuovo!!: Macchina di Turing e JFLAP · Mostra di più »
L (complessità)
Nella teoria della complessità computazionale, L è la classe di complessità che contiene i problemi di decisione che possono essere risolti da una macchina di Turing deterministica usando una quantità logaritmica di memoria.
Nuovo!!: Macchina di Turing e L (complessità) · Mostra di più »
La mente nuova dell'imperatore
La mente nuova dell'imperatore è un saggio scientifico del fisico e matematico Roger Penrose pubblicato nel 1989 e nel 1991 in Italia da Rizzoli.
Nuovo!!: Macchina di Turing e La mente nuova dell'imperatore · Mostra di più »
Lev Manovich
Lev Manovich è un autore di libri riguardanti la teoria dei nuovi media, docente del Computer Science Program al City University di New York, Graduate Center, U.S. Manovich si occupa principalmente sul rapporto tra il digitale e la persona, teoria della new media art, e studi di software.
Nuovo!!: Macchina di Turing e Lev Manovich · Mostra di più »
Lewis Carroll
È celebre soprattutto per i due romanzi Le avventure di Alice nel Paese delle Meraviglie e Attraverso lo specchio e quel che Alice vi trovò, opere che sono state apprezzate da una straordinaria varietà di lettori, dai bambini a grandi scienziati e pensatori.
Nuovo!!: Macchina di Turing e Lewis Carroll · Mostra di più »
Linguaggio dipendente dal contesto
Un linguaggio dipendente dal contesto (o anche sensibile al contesto, vincolato al contesto, o contestuale) è un linguaggio formale che può essere definito da una grammatica dipendente dal contesto.
Nuovo!!: Macchina di Turing e Linguaggio dipendente dal contesto · Mostra di più »
Linguaggio formale
Per linguaggio formale, in matematica, logica, informatica e linguistica, si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.
Nuovo!!: Macchina di Turing e Linguaggio formale · Mostra di più »
Linguaggio ricorsivo
In matematica, logica e informatica teorica, i linguaggi decidibili o ricorsivi sono una classe di linguaggi formali che corrisponde alla classe dei problemi decidibili.
Nuovo!!: Macchina di Turing e Linguaggio ricorsivo · Mostra di più »
Linguaggio Wolfram
Il Linguaggio Wolfram è un linguaggio di programmazione multi-paradigma sviluppato da Wolfram Research, usato in Mathematica e Wolfram Programming Cloud.
Nuovo!!: Macchina di Turing e Linguaggio Wolfram · Mostra di più »
Logo Google
Google ha avuto diversi loghi dalla sua nascita.
Nuovo!!: Macchina di Turing e Logo Google · 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 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!!: Macchina di Turing e Macchina che termina sempre · 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 quantistica
Una macchina di Turing quantistica (MTQ), detta anche computer quantistico universale, è una macchina astratta usata per modellare l'effetto di un computer quantistico.
Nuovo!!: Macchina di Turing e Macchina di Turing quantistica · 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 Gödel-incompleta
Per macchina Gödel-incompleta si intende una macchina che può operare quanto si reputa necessario, la quale può emettere su un proprio nastro illimitatamente estendibile (in breve: può stampare) stringhe interpretabili come affermazioni sul proprio comportamento, sapendo distinguere entro queste le affermazioni vere.
Nuovo!!: Macchina di Turing e Macchina Gödel-incompleta · 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 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!!: Macchina di Turing e Macchina URM · 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ù »
MDT
MDT può indicare.
Nuovo!!: Macchina di Turing e MDT · Mostra di più »
MT
Nessuna descrizione.
Nuovo!!: Macchina di Turing e MT · Mostra di più »
NC (complessità)
Nella teoria della complessità i problemi NC sono i problemi efficientemente parallelizzabili cioè che possono essere risolti in tempo polilogaritmico avendo a disposizione una quantità di hardware polinomiale rispetto alla dimensione dell'input.
Nuovo!!: Macchina di Turing e NC (complessità) · Mostra di più »
NL (complessità)
La classe NL è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con S_M(n).
Nuovo!!: Macchina di Turing e NL (complessità) · Mostra di più »
NP (complessità)
La classe di problemi NP comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale.
Nuovo!!: Macchina di Turing e NP (complessità) · Mostra di più »
NP-difficile
In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP.
Nuovo!!: Macchina di Turing e NP-difficile · Mostra di più »
One instruction set computer
Uno One Instruction Set Computer (OISC) è una macchina di Turing che usa una sola istruzione, e non necessita quindi di opcode.
Nuovo!!: Macchina di Turing e One instruction set computer · Mostra di più »
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Nuovo!!: Macchina di Turing e P (complessità) · Mostra di più »
P (disambigua)
*P – quattordicesima lettera dell'alfabeto italiano.
Nuovo!!: Macchina di Turing e P (disambigua) · Mostra di più »
Problema di funzione
Nella teoria della complessità computazionale, un problema di funzione è un problema computazionale dove ci si aspetta una singola uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quello di un problema di decisione, cioè, non è solo "SÌ" o "NO".
Nuovo!!: Macchina di Turing e Problema di funzione · Mostra di più »
PSPACE
Nella teoria della complessità algoritmica, la classe di problemi PSPACE (da polynomial space) è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di O(n^k), dove n è la dimensione dei dati di ingresso e k è un qualsiasi valore finito.
Nuovo!!: Macchina di Turing e PSPACE · Mostra di più »
Qualia
I qualia (plurale neutro latino di quale, is cioè qualità, attributo, modo) sono, nella filosofia della mente, gli aspetti qualitativi delle esperienze coscienti.
Nuovo!!: Macchina di Turing e Qualia · Mostra di più »
Scienze cognitive
cervello umano Con il termine scienze cognitive si definisce l'insieme di discipline che hanno come oggetto di studio scientifico e filosofico la cognizione di un sistema pensante, sia esso naturale o artificiale.
Nuovo!!: Macchina di Turing e Scienze cognitive · Mostra di più »
Sharp-P
Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP.
Nuovo!!: Macchina di Turing e Sharp-P · Mostra di più »
Sharp-P-completo
#P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale.
Nuovo!!: Macchina di Turing e Sharp-P-completo · Mostra di più »
Sistema (fisica)
In fisica, con il termine sistema si indica la porzione dell'universo oggetto dell'indagine scientifica.
Nuovo!!: Macchina di Turing e Sistema (fisica) · Mostra di più »
Small Scale Experimental Machine
Lo Small-Scale Experimental Machine (traducibile dall'inglese come "macchina sperimentale in scala ridotta", sigla SSEM, soprannominato Manchester Baby "bimbo di Manchester" o Baby) è, tra quelli di cui si ha notizia, il sesto computer elettronico digitale della storia, dopo l'IBM 603 Electronic Multiplier.
Nuovo!!: Macchina di Turing e Small Scale Experimental Machine · Mostra di più »
Stanza cinese
La Stanza cinese è un esperimento mentale ideato da John Searle come controesempio rispetto alla teoria dell'intelligenza artificiale forte.
Nuovo!!: Macchina di Turing e Stanza cinese · 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ù »
Storia dell'informatica
La storia dell'informatica è la storia della ominima scienza applicata.
Nuovo!!: Macchina di Turing e Storia dell'informatica · Mostra di più »
Storia della matematica
La storia della matematica ha origine con le scoperte matematiche e prosegue attraverso l'evoluzione nel corso dei secoli dei propri metodi e delle notazioni matematiche il cui uso si sussegue nel tempo.
Nuovo!!: Macchina di Turing e Storia della matematica · Mostra di più »
Storia della nozione di funzione matematica
Il termine funzione è stato introdotto nella matematica da Gottfried Leibniz nel 1694, per denotare una quantità collegata ad una curva, come la pendenza di una curva o uno specifico punto di una curva.
Nuovo!!: Macchina di Turing e Storia della nozione di funzione matematica · Mostra di più »
Stringa (linguaggi formali)
Nella teoria dei linguaggi formali, una stringa è una sequenza composta da un certo numero di oggetti che ci si aspetta venga sottoposta ad elaborazioni come analisi, composizioni e trasformazioni in altre stringhe o strutture discrete come grafi o configurazioni numeriche, senza modificare gli oggetti componenti.
Nuovo!!: Macchina di Turing e Stringa (linguaggi formali) · Mostra di più »
Struttura relazionale
In matematica per struttura relazionale si intende una struttura matematica tra le cui componenti compare qualche relazione matematica, oppure qualche funzione o qualche famiglia che non può considerarsi una operazione algebrica o una legge di composizione esterna.
Nuovo!!: Macchina di Turing e Struttura relazionale · Mostra di più »
Teorema dello speedup
Nella teoria della complessità computazionale un teorema dello speedup (in inglese speed-up significa velocizzare) è un teorema che considera alcuni algoritmi che risolvono determinati problemi e dimostra l'esistenza di algoritmi più efficienti per risolvere gli stessi problemi.
Nuovo!!: Macchina di Turing e Teorema dello speedup · Mostra di più »
Teorema dello speedup di Blum
Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili.
Nuovo!!: Macchina di Turing e Teorema dello speedup di Blum · Mostra di più »
Teorema di Böhm-Jacopini
Il teorema di Böhm-Jacopini, enunciato nel 1966 dagli informatici Corrado Böhm e Giuseppe Jacopini, è un teorema di informatica teorica il quale afferma che qualunque algoritmo può essere implementato in fase di programmazione (in diagramma di flusso, pseudocodice o codice sorgente) utilizzando tre sole strutture dette strutture di controllo: la sequenza, la selezione ed il ciclo (iterazione), da applicare ricorsivamente alla composizione di istruzioni elementari (ad esempio, istruzioni eseguibili con il modello di base della macchina di Turing).
Nuovo!!: Macchina di Turing e Teorema di Böhm-Jacopini · Mostra di più »
Teorema di Church
Il teorema di Church, dimostrato dal matematico Alonzo Church, nel 1936, afferma che la logica predicativa è indecidibile.
Nuovo!!: Macchina di Turing e Teorema di Church · Mostra di più »
Teorema di Cook-Levin
Nella teoria della complessità algoritmica, il teorema di Cook-Levin, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.
Nuovo!!: Macchina di Turing e Teorema di Cook-Levin · Mostra di più »
Teorema di Savitch
Nella teoria della complessità computazionale, il teorema di Savitch, dimostrato da Walter Savitch nel 1970, afferma che per ogni funzione f\left(n\right) \ge n: In altre parole, se una macchina di Turing non deterministica è in grado di risolvere un problema in spazio f(n), una macchina di Turing deterministica può risolvere lo stesso problema nel quadrato dello spazio.
Nuovo!!: Macchina di Turing e Teorema di Savitch · Mostra di più »
Teorema di Turing
Il teorema di Turing asserisce l'esistenza di problemi non decidibili, per i quali cioè non esiste alcun algoritmo in grado di dare una risposta in tempo finito su tutte le istanze del problema.
Nuovo!!: Macchina di Turing e Teorema di Turing · 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 assiomatica degli insiemi
La teoria degli insiemi è una branca della matematica sviluppata principalmente dal matematico tedesco Georg Cantor alla fine del XIX secolo.
Nuovo!!: Macchina di Turing e Teoria assiomatica degli insiemi · Mostra di più »
Teoria degli insiemi
La teoria degli insiemi è una teoria matematica posta ai fondamenti della matematica stessa, collocandosi nell'ambito della logica matematica.
Nuovo!!: Macchina di Turing e Teoria degli insiemi · 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ù »
Test di Turing
Il test di Turing è un criterio per determinare se una macchina sia in grado di pensare.
Nuovo!!: Macchina di Turing e Test di Turing · Mostra di più »
The Imitation Game
The Imitation Game è un film del 2014 diretto da Morten Tyldum, con protagonista Benedict Cumberbatch nei panni del matematico e crittoanalista Alan Turing.
Nuovo!!: Macchina di Turing e The Imitation Game · Mostra di più »
TM
Nessuna descrizione.
Nuovo!!: Macchina di Turing e TM · Mostra di più »
Warren McCulloch
Warren Sturgis McCulloch nacque ad Orange, nel New Jersey, nel 1898.
Nuovo!!: Macchina di Turing e Warren McCulloch · Mostra di più »
ZPP (complessità)
Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà.
Nuovo!!: Macchina di Turing e ZPP (complessità) · Mostra di più »
2-EXPTIME
Nella teoria della complessità computazionale, la classe di complessità 2-EXPTIME (talvolta chiamata 2-EXP, da 2-Exponential Time, "tempo 2-esponenziale") è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(22p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, Sappiamo che 2-EXPTIME può anche essere riformulato come la classe di spazio AEXPSPACE, i problemi che possono essere risolti da una macchina di Turing alternante in spazio esponenziale.
Nuovo!!: Macchina di Turing e 2-EXPTIME · Mostra di più »
4GL
Acronimo di fourth-generation programming language (1970-1990), linguaggio formale di quarta generazione (abbreviato 4GL).
Nuovo!!: Macchina di Turing e 4GL · Mostra di più »
Riorienta qui:
Macchina di Turing deterministica, Macchina di Turing non deterministica, Macchine di Turing.
