Cos'è Turing Complete?

Question

Cosa significa l'espressione "Turing Complete"?

Puoi dare una spiegazione semplice, senza entrare in troppi dettagli teorici?

Answer 1

Ecco la spiegazione più breve:

Per sistema Turing Complete si intende un sistema in cui è possibile scrivere un programma che troverà una risposta (anche se senza garanzie riguardo al tempo di esecuzione o alla memoria).

Quindi, se qualcuno dice "la mia nuova cosa è Turing Complete" significa che in linea di principio (anche se spesso non in pratica) potrebbe essere usato per risolvere qualsiasi problema di calcolo.

A volte è uno scherzo...un ragazzo ha scritto un simulatore di Turing Machine in vi, quindi è possibile dire che vi è l'unico motore computazionale mai necessario al mondo.

Answer 2

Ecco la spiegazione più semplice

Alan Turing ha creato una macchina in grado di prendere un programma, eseguirlo e mostrare alcuni risultati.Ma poi ha dovuto creare macchine diverse per programmi diversi.Così ha creato la "Macchina di Turing Universale" che può prendere QUALSIASI programma ed eseguirlo.

I linguaggi di programmazione sono simili a quelle macchine (anche se virtuali).Prendono i programmi e li eseguono.Ora, un linguaggio di programmazione si chiama "Turing completo", se può eseguire qualsiasi programma (indipendentemente dalla lingua) che una macchina di Turing può eseguire con tempo e memoria sufficienti.

Per esempio:Diciamo che c'è un programma che prende 10 numeri e li somma.La macchina di Turing può facilmente eseguire questo programma.Ma ora immagina che per qualche motivo il tuo linguaggio di programmazione non possa fare la stessa aggiunta, quindi la macchina di Turing è incompleta.D'altra parte, se può eseguire qualsiasi programma come può eseguire la macchina di Turing universale, allora è Turing completo.

La maggior parte dei linguaggi di programmazione moderni come Java, JavaScript, Perl ecc. sono tutti completi perché implementano tutte le funzionalità richieste per eseguire programmi come addizione, moltiplicazione, condizione if-else, istruzioni return, modi per archiviare/recuperare/cancellare dati e così via .

Aggiornamento:Puoi saperne di più sul mio post sul blog: "JavaScript è Turing completo" — Spiegato

Answer 3

Da Wikipedia:

La completezza di Turing, che prende il nome da Alan Turing, è significativa in quanto ogni progetto plausibile per un dispositivo di elaborazione finora avanzato può essere emulato da una macchina universale di Turing-un'osservazione che è diventata nota come tesi della chiesa.Pertanto, una macchina che può agire come una macchina universale di Turing può, in linea di principio, eseguire qualsiasi calcolo di cui è capace qualsiasi altro computer programmabile.Tuttavia, ciò non ha nulla a che fare con lo sforzo richiesto per scrivere un programma per la macchina, il tempo impiegato dalla macchina per eseguire il calcolo o eventuali abilità che la macchina può possedere non correlate al calcolo.

Mentre le macchine per veramente Turing-complete sono molto probabilmente fisicamente impossibili, poiché richiedono una conservazione illimitata, la completezza di Turing è spesso vagamente attribuita a macchine fisiche o linguaggi di programmazione che sarebbero universali se avessero una conservazione illimitata.Tutti i computer moderni sono completi in questo senso.

Non so come si possa essere più non tecnici di così, se non dicendo "essere completo significa 'capace di rispondere a un problema calcolabile dato abbastanza tempo e spazio'".

Answer 4

Definizione informale

Un linguaggio di Turing completo è quello che può eseguire qualsiasi calcolo.IL Tesi di Church-Turing afferma che qualsiasi calcolo eseguibile può essere eseguito da una macchina di Turing.UN Macchina di Turing è una macchina con memoria ad accesso casuale infinita e un "programma" finito che determina quando deve leggere, scrivere e spostarsi attraverso quella memoria, quando dovrebbe terminare con un determinato risultato e cosa dovrebbe fare dopo.L'input di una macchina di Turing viene inserito nella sua memoria prima che venga avviata.

Cose che possono rendere completa una lingua NON Turing

Una macchina di Turing può prendere decisioni in base a ciò che vede nella memoria - Il 'linguaggio' che supporta solo +, -, *, E / sugli interi non è Turing completo perché non può fare una scelta in base al suo input, ma una macchina di Turing può farlo.

Una macchina di Turing può funzionare per sempre - Se prendessimo Java, Javascript o Python e rimuovessimo la possibilità di eseguire qualsiasi tipo di loop, GOTO o chiamata di funzione, Turing non sarebbe completo perché non può eseguire un calcolo arbitrario che non termina mai. Coq è un dimostratore di teoremi che non può esprimere programmi che non terminano, quindi non è Turing completo.

Una macchina di Turing può utilizzare una memoria infinita - Un linguaggio che fosse esattamente come Java ma che terminasse una volta utilizzato più di 4 Gigabyte di memoria non sarebbe Turing completo, perché una macchina di Turing può utilizzare una memoria infinita.Questo è il motivo per cui in realtà non possiamo costruire una macchina di Turing, ma Java è ancora un linguaggio Turing completo perché Java lingua non ha alcuna restrizione che gli impedisca di utilizzare memoria infinita.Questo è uno dei motivi per cui le espressioni regolari non sono complete di Turing.

Una macchina di Turing ha una memoria ad accesso casuale - Un linguaggio che ti permette solo di lavorare con la memoria push E pop le operazioni su uno stack non sarebbero complete di Turing.Se ho un "linguaggio" che legge un file string una volta e può utilizzare la memoria solo spingendo ed estraendo da uno stack, può dirmi se ogni ( nella stringa ha il suo ) più tardi spingendo quando vede ( e scoppiando quando vede ).Tuttavia, non può dirmi se ogni ( ha il suo ) più tardi E ogni [ ha il suo ] più tardi (attenzione ([)] soddisfa questi criteri ma ([]] non).Una macchina di Turing può utilizzare la sua memoria ad accesso casuale per tracciare ()'sabbia []è separatamente, ma questo linguaggio con solo uno stack non può.

Una macchina di Turing può simulare qualsiasi altra macchina di Turing - Una macchina di Turing, quando le viene fornito un "programma" appropriato, può prendere il "programma" di un'altra macchina di Turing e simularlo su input arbitrario.Se avessi un linguaggio a cui fosse proibito implementare un interprete Python, non sarebbe Turing completo.

Esempi di linguaggi completi di Turing

Se la tua lingua ha una memoria ad accesso casuale infinita, esecuzione condizionale e qualche forma di esecuzione ripetuta, probabilmente è Turing completo.Esistono sistemi più esotici che possono ancora ottenere tutto ciò che può fare una macchina di Turing, il che rende anche loro Turing completi:

• Lambda calcolo non tipizzato
• Il gioco della vita di Conway
• Modelli C++
• Prologo

Answer 5

Fondamentalmente, la completezza di Turing è un requisito conciso, ricorsione illimitata.

Nemmeno limitato dalla memoria.

Ci ho pensato in modo indipendente, ma ecco qualche discussione dell'affermazione. La mia definizione di LSP fornisce più contesto.

Le altre risposte qui non definiscono direttamente l'essenza fondamentale della completezza di Turing.

Answer 6

Turing Complete significa che è potente almeno quanto a Macchina di Turing.Ciò significa che tutto ciò che può essere calcolato da una macchina di Turing può essere calcolato da un sistema Turing Complete.

Nessuno ha ancora trovato un sistema più potente di una macchina di Turing.Quindi, per il momento, dire che un sistema è Turing Complete equivale a dire che il sistema è potente quanto qualsiasi sistema informatico conosciuto (vedi Tesi di Church-Turing).

Answer 7

In termini più semplici, un sistema completo di Turing può risolvere qualsiasi possibile problema computazionale.

Uno dei requisiti chiave è che la dimensione dello Scratchpad sia illimitata e che sia possibile riavvolgere per accedere alle scritture precedenti sullo Scratchpad.

Quindi in pratica nessun sistema è completo di Turing.

Piuttosto, alcuni sistemi si avvicinano alla completezza di Turing modellando la memoria illimitata ed eseguendo qualsiasi calcolo possibile che possa rientrare nella memoria del sistema.

Answer 8

Penso che l'importanza del concetto "Turing Complete" risieda nella capacità di identificare una macchina informatica (non necessariamente un "computer" meccanico/elettrico) i cui processi possono essere decostruiti in istruzioni "semplici", composte da istruzioni sempre più semplici istruzioni, che una macchina universale potrebbe interpretare e quindi eseguire.

Consiglio vivamente The Annotated Turing

@Mark penso che quello che stai spiegando sia un mix tra la descrizione della Universal Turing Machine e Turing Complete.

Qualcosa che è Turing Complete, in senso pratico, sarebbe una macchina/processo/calcolo in grado di essere scritto e rappresentato come un programma, per essere eseguito da una Macchina Universale (un computer desktop).Sebbene non prenda in considerazione il tempo o l'archiviazione, come menzionato da altri.

Answer 9

Quello che capisco in parole semplici:

Turing completo: Un linguaggio/programma di programmazione in grado di eseguire calcoli è Turing Complete.

Per esempio :

1. Puoi aggiungere due numeri usando Just HTML.(Ans è 'NO', devi usare javascript per eseguire l'addizione.), Quindi HTML non è Turing Complete.

2. Linguaggi come Java, C++, Python, Javascript, Solidity for Ethereum ecc. sono Turing Complete perché puoi eseguire calcoli come aggiungere due numeri usando questi linguaggi.

Spero che questo ti aiuti.

Answer 10

COME ha detto Waylon Flinn:

Turing Complete significa che è potente almeno quanto una macchina di Turing.

Credo che questo non sia corretto, un sistema è Turing completo se è esattamente potente quanto la Macchina di Turing, cioèogni calcolo fatto dalla macchina può essere fatto dal sistema, ma anche ogni calcolo fatto dal sistema può essere fatto dalla macchina di Turing.

Answer 11

In termini linguistici pratici familiari alla maggior parte dei programmatori, il modo usuale per rilevare la completezza di Turing è se il linguaggio consente o consente la simulazione di istruzioni while annidate e illimitate (al contrario dello stile Pascal per le istruzioni, con limiti superiori fissi).

Answer 12

Può un database relazionale inserire latitudini e longitudini di luoghi e strade e calcolare il percorso più breve tra di loro - no.Questo è un problema che mostra che SQL non è Turing completo.

Ma C++ può farlo e può risolvere qualsiasi problema.Così è.