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, è 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

Tipo

Sistema astratto

Interruzione

Incrementale

Utilizzo

Uso diffuso

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

Brevetti:

NA

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.

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)

Invenzioni, innovazioni e principi tecnici correlati

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

> Login <