Product Design, Manufacturing & Innovation Resources
Lar » Completude de Turing

Completude de Turing

1936
  • Alan Turing
Laboratório de ciência da computação mostrando a completude de Turing em linguagens de programação.

(Imagem gerada apenas para fins ilustrativos)

Um sistema de regras de manipulação de dados, como um linguagem de programaçãoUma linguagem de programação é Turing completa se puder simular qualquer máquina de Turing de fita única. Isso significa que ela é computacionalmente universal e pode ser usada para resolver qualquer problema computável, dado tempo e memória suficientes. A maioria das linguagens de programação de propósito geral são Turing completas, formando a base teórica para seu poder expressivo.

A completude de Turing é um conceito da teoria da computabilidade que define o poder de um sistema computacional. Ela tem origem no artigo de Alan Turing de 1936, que descreve um dispositivo teórico conhecido como Máquina de Turing. Essa máquina consiste em uma fita infinitamente longa, uma cabeça que pode ler, escrever e se mover ao longo da fita, e um conjunto de estados e regras de transição. Apesar de sua simplicidade, uma Máquina de Turing pode realizar qualquer computação que possa ser descrita algoritmicamente. Uma linguagem de programação ou qualquer outro sistema formal é considerado "Turing completo" se tiver a capacidade de simular uma Máquina de Turing universal. Isso implica que a linguagem pode computar qualquer coisa que seja computável.

Os requisitos fundamentais para que um sistema seja Turing completo são o desvio condicional (por exemplo, instruções if-then-else) e a capacidade de executar loops indefinidamente ou recursivamente (por exemplo, loops while e for). Essas construções permitem que o sistema tome decisões e repita operações, o que é suficiente para modelar o comportamento das transições de estado e da manipulação de fita de uma Máquina de Turing. A tese de Church-Turing, um princípio fundamental da ciência da computação, postula que qualquer função que seja naturalmente considerada "computável" pode ser computada por uma Máquina de Turing. Portanto, uma linguagem Turing-completa é, em teoria, capaz de expressar qualquer algoritmo.

No entanto, esse poder teórico traz consigo uma consequência significativa: o problema da parada. Turing provou que é impossível criar um algoritmo geral que possa determinar, para todas as entradas possíveis, se um determinado programa terminará sua execução ou continuará indefinidamente. Essa indecidibilidade é uma propriedade inerente a todos os sistemas Turing-completos. Por essa razão, algumas linguagens de domínio específico são intencionalmente projetadas para não serem Turing-completas. Por exemplo, SQL padrão e HTML não são Turing-completos, o que garante que seus scripts ou definições terminarão e impede que entrem em loops infinitos acidentais, uma propriedade desejável para consultas a bancos de dados e renderização de documentos.

UNESCO Nomenclature: 1202
Ciência da Computação

Tipo

Sistema abstrato

Interrupção

Incremental

Uso

Uso generalizado

Precursores

  • Kurt Gödel’s work on incompleteness theorems
  • O desenvolvimento do cálculo lambda por Alonzo Church
  • O programa de David Hilbert para formalizar a matemática
  • O conceito de algoritmo remonta à antiguidade.

Aplicações

  • linguagens de programação de propósito geral (python, c++, java)
  • Sistemas de planilhas com recursos de macro (por exemplo, Excel com VBA)
  • Circuitos de redstone do Minecraft
  • cellular automata like conway’s game of life
  • Algumas extensões SQL avançadas com expressões de tabela comuns recursivas.
  • o subsistema de metaprogramação de modelos C++
  • CSS3 com certas combinações de HTML

Patentes:

NA

Ideias de Inovação Potencial

Devido ao tráfego de bots de coleta de dados, atualmente superior a 40 mil por dia, este conteúdo é reservado aos membros da comunidade.
> Login < ou > Registrar < (100% gratuito) para acessar isso, assim como todo o restante do conteúdo e das ferramentas restritas.

Relacionado a: completude de Turing, máquina de Turing, teoria da computabilidade, Alan Turing, tese de Church-Turing, computação universal, algoritmo, linguagem formal, decidibilidade, problema da parada.

Contexto histórico

Completude de Turing

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

(Caso a data seja desconhecida ou irrelevante, por exemplo, "mecânica dos fluidos", é fornecida uma estimativa aproximada de seu surgimento notável)

Princípios relacionados à invenção, inovação e tecnologia

Imagens em tamanho real e downloads estão disponíveis apenas, 100% gratuitos, para membros registrados.