O que é a plenitude de Turing?
A integridade de Turing é quando uma linguagem de programação é capaz de executar as funções de uma máquina de Turing. Esse é um conceito para um computador mecânico muito básico, algumas vezes descrito como a máquina mais simples que pode ser considerada um computador. Praticamente todas as linguagens de programação em uso atualmente e, em teoria, os computadores que as executam, possuem a integridade de Turing.
O conceito de integridade de Turing vem de Alan Turing, um cientista britânico da computação cujo trabalho incluiu decifrar mensagens codificadas durante a Segunda Guerra Mundial. Entre seu trabalho em computação, estava o desenvolvimento de uma filosofia do que um computador poderia realmente fazer. Isso incluía o conceito de que os computadores funcionam simplesmente executando algoritmos. Ou seja, eles seguem um conjunto fixo de regras para processar dados e, por sua vez, resolver problemas. Isso significa que um computador não "pensa" ou toma decisões como uma pessoa pode.
Para ilustrar o conceito, Turing descreveu uma máquina hipotética que ele chamou de "a-machine", com o "a" como automático; outros mais tarde a chamaram de máquina de Turing. A máquina processaria um rolo de fita que poderia recuar ou avançar e continha uma linha de símbolos. A qualquer momento, a máquina pode processar um símbolo e, se necessário, alterá-lo. Para os propósitos do conceito, o rolo de fita poderia ser infinitamente longo, o que significa que a memória do computador não era inerentemente limitada. Essa é uma analogia da idéia de que, uma vez que um computador tenha um conjunto de instruções a seguir, a quantidade de dados à qual ele pode aplicar essas instruções estará sujeita apenas a limites físicos.
Ironicamente, a maioria dos computadores atualmente não possui a integridade de Turing. Isso ocorre porque eles têm limitações no espaço de armazenamento disponível e, portanto, nos dados que podem processar. Eles também têm limitações físicas, principalmente porque acabarão se desgastando. Na verdade, é a linguagem de programação que possui a integridade de Turing. Por esse motivo, um computador executando esse programa não é um computador de Turing, mas pode ser usado para simular um.
A integridade de Turing não deve ser confundida com o teste de Turing. Este foi um experimento desenvolvido por Turing para verificar se os computadores podem conversar em linguagem natural. O princípio do teste é que, se um humano não pode distinguir a diferença entre uma conversa somente de texto com o computador e outro humano, o computador passa no teste. Enquanto alguns computadores passaram no teste quando o intervalo de assuntos da conversa é restrito, nenhum o fez em conversas irrestritas.