O que é essa tal Máquina de Turing que o fez o Turing ser reconhecido como o "Pai da Computação"? Como é o seu funcionamento e como ela faz pra ler uma fita de binários?
-
Onde ele é conhecido como o pai da computação ?– MagicHatCommented 11/10/2016 às 16:48
-
2Será que é duplicata dessa? (que consideraram duplicata e eu achei que não é, mas não vou mexer por conta própria) pt.stackoverflow.com/q/102452/101. Relacionadas ou pelo menos que fazem citações práticas: pt.stackoverflow.com/q/101683/101, pt.stackoverflow.com/q/35547/101, pt.stackoverflow.com/q/99642/101, pt.stackoverflow.com/q/46983/101, pt.stackoverflow.com/q/7740/101, pt.stackoverflow.com/q/81854/101, pt.stackoverflow.com/q/113985/101, pt.stackoverflow.com/q/28297/101, pt.stackoverflow.com/q/30749/101, entre outras– Maniero ♦Commented 11/10/2016 às 16:52
-
2A pergunta é boa, mas acho ser duplicata sim :P– MarceloBoniCommented 11/10/2016 às 16:53
-
3Acredito que o termo seja usado muito como licença poética. É complicado fazer tal afirmação quando na verdade várias pessoas contribuíram muito para a base da computação moderna, uma sem a outra não serviria para nada do que temos hoje.– Maniero ♦Commented 11/10/2016 às 16:55
-
1@bigown acho que essa sua resposta pt.stackoverflow.com/a/35548/14262 já responde essa pergunta– MarceloBoniCommented 11/10/2016 às 16:57
1 Resposta
Segundo a Wikipedia a Máquina de Turing é um modelo matemático de computação que descreve uma máquina abstrata que manipula símbolos em uma fita de acordo com uma tabela de regras. Apesar da simplicidade do modelo, ele é capaz de implementar qualquer algoritmo de computador.
Em termos bem leigos é a forma como uma pessoa resolve um problema matemático.
Note que não o termo não se refere a uma máquina real, embora possamos construir uma máquina que atende o modelo que ela define. Ou quase, já que ela prega memória infinita, o que não é possível no mundo real.
Em 1936 o termo algoritmo foi formalizado como sendo um conjunto finito de instruções simples e precisas, que são descritas com um número finito de símbolos.
Qualquer dispositivo, seja hardware ou software, que se conforme com o modelo definido pelo Alan Turing, seu criador, pode ser considerado um dispositivo Turing Complete, portanto ele atende aos critérios da Máquina de Turing. A ideia do algoritmo iniciou-se a partir daí através da proposição de Alonzo Church:
Qualquer processo aceito por nós homens como um algoritmo é precisamente o que uma máquina de Turing pode fazer
Estritamente falando nada real pode ser Turing Complete, então a infinitude costuma ser desconsiderada.
De fato, algumas máquinas foram produzidas para demonstrar o conceito.
Seguindo a Wikipedia, a máquina opera em uma fita de memória infinita dividida em células discretas, cada uma das quais pode conter um único símbolo extraído de um conjunto finito de símbolos chamado alfabeto da máquina. Possui uma "cabeça" que, em qualquer ponto da operação da máquina, é posicionada sobre uma dessas células, e um "estado" selecionado a partir de um conjunto finito de estados. A cada passo de sua operação, a cabeça lê o símbolo em sua célula. Então, com base no símbolo e no estado atual da própria máquina, a máquina escreve um símbolo na mesma célula e move a cabeça um passo para a esquerda ou para a direita, ou interrompe a computação. A escolha de qual símbolo de substituição escrever e qual direção mover é baseada em uma tabela finita que especifica o que fazer para cada combinação do estado atual e o símbolo que é lido.
Se desejar pode experimentar a máquina virtualmente.
O modelo foi importante para que o Turing tivesse um parâmetro do que faria para atingir os objetivos da criação de um computador, como é o computador moderno que usamos hoje.
Dispositivos de software podem se conformar com a Máquina de Turing também. E de fato a definição do que é uma linguagem de programação passou adotar essa capacidade, já que a Máquina de Turing é capaz de executar computações arbitrárias, exatamente o que se espera de uma linguagem de programação, que vai além do que outras linguagens mais simples podem oferecer. Alguns testes podem ser feitos para determinar isso. Exemplo de linguagem que não passa no teste, sendo que universalmente temos o Teste de Turing. E um que passa. A linguagem pode ser fora do comum ou ser inútil na prática. Pode-se ver mais sobre o assunto. Também.
Existem variantes da máquina para atender cenários específicos, e justamente uma variante que aceita a finitude é usada na maioria dos casos. É possível ter máquinas determinísticas e não determinísticas, ter mais de uma fita, etc.
Daí surgiu a Teoria dos Autômatos e o Problema da Condição de Parada.
Ainda que existam pessoas que dizem que não é a completeza de Turing que define o que é uma linguagem de programação, há muito material e apoio dessa ideia, e nenhuma ideia superior claramente é apresentada para dar uma definição melhor.
Como não é fácil fazer uma demonstração do funcionamento da MT e para não incorrer em plágio, como a outra resposta existente (quem sabe não mais quando ler isso), vou deixar alguns links que pode ajudar: