Completezza di Turing
Un sistema di regole di manipolazione dei dati, come ad esempio una linguaggio di programmazione, è completa di Turing se può simulare qualsiasi macchina di Turing a singolo nastro. Ciò significa che è computazionalmente universale e può essere utilizzato per risolvere qualsiasi problema computabile, se si dispone di tempo e memoria sufficienti. La maggior parte dei linguaggi di programmazione di uso generale sono completi di Turing e costituiscono la base teorica della loro potenza espressiva.
La completezza di Turing è un concetto della teoria della computabilità che definisce la potenza di un sistema computazionale. Ha origine dall'articolo di Alan Turing del 1936 che descrive un dispositivo teorico noto come macchina di Turing. Questa macchina consiste in un nastro infinitamente lungo, una testina che può leggere, scrivere e muoversi lungo il nastro e un insieme di stati e regole di transizione. Nonostante la sua semplicità, una macchina di Turing può eseguire qualsiasi calcolo che possa essere descritto algoritmicamente. Un linguaggio di programmazione o qualsiasi altro sistema formale è considerato ‘completo di Turing’ se ha la capacità di simulare una macchina di Turing universale. Ciò implica che il linguaggio può calcolare qualsiasi cosa sia computabile.
I requisiti fondamentali affinché un sistema sia completo per Turing sono la ramificazione condizionale (ad esempio, gli enunciati if-then-else) e la capacità di eseguire cicli indefiniti o ricorsivi (ad esempio, i cicli while e for). Questi costrutti consentono al sistema di prendere decisioni e ripetere operazioni, il che è sufficiente per modellare il comportamento delle transizioni di stato e della manipolazione del nastro di una macchina di Turing. La tesi di Church-Turing, un principio fondamentale dell'informatica, sostiene che qualsiasi funzione considerata naturalmente ‘computabile’ può essere calcolata da una macchina di Turing. Pertanto, un linguaggio Turing-completo è, in teoria, in grado di esprimere qualsiasi algoritmo.
Tuttavia, questa potenza teorica comporta una conseguenza significativa: il problema dell'arresto. Turing ha dimostrato che è impossibile creare un algoritmo generale in grado di determinare, per tutti i possibili input, se un dato programma terminerà l'esecuzione o continuerà per sempre. Questa indecidibilità è una proprietà intrinseca di tutti i sistemi Turing-completi. Per questo motivo, alcuni linguaggi specifici di dominio sono intenzionalmente progettati per essere non-Turing-completi. Ad esempio, SQL e HTML standard non sono Turing-completi, il che garantisce che i loro script o definizioni termineranno e impedisce loro di entrare in loop infiniti accidentali, una proprietà auspicabile per le query di database e il rendering di documenti.
UNESCO Nomenclature: 1202
- Informatica
Interruzione
Incrementale
Precursori
- Il lavoro di Kurt Gödel sui teoremi di incompletezza
- Lo sviluppo del calcolo lambda da parte di Alonzo Church
- Il programma di David Hilbert per formalizzare la matematica
- Il concetto di algoritmo risale all'antichità
Applicazioni
- linguaggi di programmazione generici (python, c++, java)
- sistemi di fogli di calcolo con funzionalità macro (ad esempio, Excel con VBA)
- Il circuito redstone di Minecraft
- cellular automata like conway’s game of life
- alcune estensioni SQL avanzate con espressioni di tabella comuni ricorsive
- il sottosistema di metaprogrammazione dei template c++
- css3 con alcune combinazioni html
Idee e potenziali innovazioni
A causa dell'eliminazione del traffico generato dai bot, che attualmente supera i 40.000 al giorno, questo contenuto è riservato ai membri della community.
> Accedi O > Registrati L'accesso a questo contenuto, così come a tutti gli altri contenuti e strumenti riservati, è (100% gratuito).
Correlato a: completezza di turing, macchina di turing, teoria della computabilità, alan turing, tesi di church-turing, calcolo universale, algoritmo, linguaggio formale, decidibilità, problema di halting.