Casa » Completezza di Turing

Completezza di Turing

1936
  • Alan Turing
Computer science lab showcasing Turing completeness in programming languages.

A system of data-manipulation rules, such as a 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 programming language 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.

The core requirements for a system to be Turing complete are conditional branching (e.g., if-then-else statements) and the ability to loop indefinitely or recursively (e.g., while, for loops). These constructs allow the system to make decisions and repeat operations, which is sufficient to model the behavior of a Turing machine’s state transitions and tape manipulation. The Church-Turing thesis, a fundamental principle in computer science, posits that any function that is naturally considered ‘computable’ can be computed by a Turing machine. Therefore, a Turing-complete language is, in theory, capable of expressing any algorithm.

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ödel’s work on incompleteness theorems
  • Alonzo Church’s development of lambda calculus
  • David Hilbert’s program to formalize mathematics
  • 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)
  • minecraft’s redstone circuitry
  • cellular automi like conway’s 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

Potenziali idee innovative

Livelli! Iscrizione richiesta

Per accedere a questo contenuto devi essere un membro di !Professionals (100% free)!

Iscriviti ora

Siete già membri? Accedi
Related to: turing completeness, turing machine, computability theory, alan turing, church-turing thesis, universal computation, algorithm, formal language, decidability, halting problem.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

DISPONIBILE PER NUOVE SFIDE
Ingegnere meccanico, responsabile di progetto, ingegneria di processo o ricerca e sviluppo
Sviluppo efficace del prodotto

Disponibile per una nuova sfida con breve preavviso.
Contattami su LinkedIn
Integrazione di componenti elettronici in plastica e metallo, progettazione in base ai costi, GMP, ergonomia, dispositivi e materiali di consumo di medio-alto volume, produzione snella, settori regolamentati, CE e FDA, CAD, Solidworks, Lean Sigma Black Belt, ISO 13485 in ambito medico

Stiamo cercando un nuovo sponsor

 

La tua azienda o istituzione si occupa di tecnica, scienza o ricerca?
> inviaci un messaggio <

Ricevi tutti i nuovi articoli
Gratuito, no spam, email non distribuita né rivenduta

oppure puoi ottenere la tua iscrizione completa -gratuitamente- per accedere a tutti i contenuti riservati >Qui<

Contesto storico

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

Principi di invenzione, innovazione e tecnica correlati

Torna in alto

Potrebbe anche piacerti