Product Design, Manufacturing & Innovation Resources
Casa » Completezza di Turing

Completezza di Turing

1936
  • Alan Turing
Laboratorio di informatica che mostra la completezza di Turing nei linguaggi di programmazione.

(Immagine generata a solo scopo illustrativo)

Un sistema di regole di manipolazione dei dati, come ad esempio una linguaggio di programmazione, is Turing complete if it can simulate any single-taped Turing machine. This means it is computationally universal and can be used to solve any computable problem, given enough time and memory. Most general-purpose programming languages are Turing complete, forming the theoretical foundation for their expressive power.

Turing completeness is a concept from computability theory that defines the power of a computational system. It originates from Alan Turing’s 1936 paper describing a theoretical device known as the Turing machine. This machine consists of an infinitely long tape, a head that can read, write, and move along the tape, and a set of states and transition rules. Despite its simplicity, a Turing machine can perform any computation that can be described algorithmically. A linguaggio di programmazione or any other formal system is deemed ‘Turing complete’ if it has the capability to simulate a universal Turing machine. This implies that the language can compute anything that is computable.

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

Tipo

Sistema astratto

Interruzione

Incrementale

Utilizzo

Uso diffuso

Precursori

  • Kurt Gödelil lavoro sui teoremi di incompletezza
  • Alonzo Church’s development of calcolo lambda
  • 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 come quello di Conway gioco della vita
  • alcune estensioni SQL avanzate con espressioni di tabella comuni ricorsive
  • il sottosistema di metaprogrammazione dei template c++
  • css3 con alcune combinazioni html

Brevetti:

NA

Idee e potenziali innovazioni

  • un linguaggio di smart contract completo, verificabile e non-turing per transazioni finanziarie critiche, per prevenire loop infiniti e attacchi di rientro.
  • un gioco educativo in cui i giocatori costruiscono macchine di Turing complete a partire da porte logiche di base per insegnare i fondamenti dell'informatica.
  • un sistema di elaborazione basato sul DNA che sfrutta la completezza di Turing per simulazioni biologiche complesse a livello molecolare.
  • un paradigma di programmazione quantistica che estende la completezza di Turing per gestire la sovrapposizione e l'entanglement per nuovi algoritmi.
  • UN verifica formale tool that can prove or disprove the turing completeness of any given formal system or esoteric language.
  • un protocollo di rete decentralizzato in cui il comportamento del nodo è definito da piccoli script sandbox completi di turing per un routing personalizzabile.
  • un'intelligenza artificiale artistica che genera nuovi modelli visivi esplorando lo spazio di stato di macchine di Turing minimaliste e generate casualmente.
  • un framework di analisi della sicurezza che identifica potenziali vulnerabilità di tipo denial-of-service causate da una completezza di turing involontaria nei file di configurazione.
  • a neuro-symbolic ai architecture where a rete neurale learns to manipulate a turing-complete symbolic computation engine.
  • un sistema hardware automodificante basato su FPGA in cui la logica hardware stessa è un sistema Turing-completo in grado di evolversi.
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.

Contesto storico

Completezza di Turing

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

(se la data è sconosciuta o non rilevante, ad esempio "meccanica dei fluidi", viene fornita una stima approssimativa della sua notevole comparsa)

decimo anno anniversario

Le immagini a grandezza naturale e i download sono disponibili, gratuitamente al 100%, solo per gli utenti registrati.

> Login <