Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Cosa vuol dire Turing-completo

In informatica teorica un sistema di regole di manipolazione dei dati (come un modello di calcolo, il set di istruzioni di un computer, un linguaggio di programmazione o anche, volendo, un semplice automa cellulare) è detto Turing-completo o altresì computazionalmente universale se può essere usato per simulare qualsiasi macchina di Turing (ideata dal matematico e informatico inglese Alan Turing). Ciò significa che tale sistema Turing completo è in grado di riconoscere o decidere altri insiemi di regole di manipolazione dei dati, anche diversi da quelli originali. La completezza di Turing viene utilizzata per esprimere la potenza di un insieme di regole per la manipolazione dei dati. La totalità dei linguaggi di programmazione moderni sono considerati, per inciso, Turing-completi.

I computer costruiti fino ad oggi possono essere analizzati funzionalmente come una macchina di Turing a nastro singolo (il “nastro” corrisponde alla loro memoria); quindi la matematica associata può essere applicata astraendo il loro funzionamento abbastanza lontano. Tuttavia, i computer reali hanno risorse fisiche limitate, quindi sono completi solo di automi lineari vincolati. Al contrario, un computer universale è definito come un dispositivo con un set di istruzioni completo di Turing, memoria infinita e tempo disponibile infinito.


Cerchi un hosting economico per il tuo sito o blog? Tophost ti aspetta (clicca qui) - Puoi anche usare il coupon sconto esclusivo 7NSS5HAGD5UC2 per spendere di meno ;-)

Un concetto correlato è quello di equivalenza di Turing: due computer P e Q sono detti equivalenti se P può simulare Q e Q può simulare P. La tesi di Church-Turing congettura che qualsiasi funzione i cui valori possono essere calcolati da un algoritmo può essere calcolata da una macchina di Turing, e quindi che se qualsiasi computer del mondo reale può simulare una macchina di Turing, è equivalente a una macchina di Turing. Una macchina di Turing universale può essere utilizzata per simulare qualsiasi macchina di Turing e, per estensione, gli aspetti computazionali di qualsiasi possibile computer del mondo in cui viviamo.

Per dimostrare che qualcosa è Turing-completo, è sufficiente dimostrare che può essere usato per simulare un sistema Turing-completo. Nessun sistema fisico può disporre di una memoria infinita, chiaramente, ma se si ignora la limitazione della memoria finita, la maggior parte dei linguaggi di programmazione sono altrimenti Turing-completi.

Nell’uso colloquiale, i termini “Turing-completo” e “Turing-equivalente” sono usati per indicare che qualsiasi computer o linguaggio informatico di uso generale del mondo reale può simulare approssimativamente gli aspetti computazionali di qualsiasi altro computer o linguaggio informatico di uso generale del mondo reale. Nella vita reale, questo porta ai concetti pratici di virtualizzazione ed emulazione.

Immagine di copertina: ritratto di Alan Turing generato dall’intelligenza artificiale di StarryAI

👇 Da non perdere 👇



Questo portale web esiste da 4513 giorni (12 anni), e contiene ad oggi 4018 articoli (circa 3.214.400 parole in tutto) e 16 servizi online gratuiti. – Leggi un altro articolo a caso
Non ha ancora votato nessuno.

Ti sembra utile o interessante? Vota e fammelo sapere.

Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo - Pagare online (il blog) - Trovalost.it