Por que a máquina de Turing é um modelo popular de computação?

Eu sou um graduado em CS. Entendo como Turing criou sua máquina abstrata (modelar uma pessoa fazendo um cálculo), mas me parece uma abstração desajeitada e deselegante. Por que consideramos uma "fita" e um cabeçote de máquina escrevendo símbolos, mudando de estado, mudando a fita para frente e para trás?

Qual é o significado subjacente? Um DFA é elegante - parece capturar com precisão o que é necessário para reconhecer os idiomas comuns. Mas a máquina de Turing, para meu julgamento iniciante, é apenas uma engenhoca abstrata desajeitada.

Depois de pensar sobre isso, acho que o modelo de computação mais idealizado seria dizer que algum sistema físico correspondente à sequência de entrada, depois de acionado, atingisse um equilíbrio estático que, por interpretação equivalente ao usado para formar o sistema da sequência original corresponderia à sequência de saída correta. Isso captura a noção de "automação", pois o sistema mudaria deterministicamente com base apenas no estado original.

Editar :

Depois de ler algumas respostas, percebi que o que me confunde sobre a máquina de Turing é que ela não parece mínima. O modelo canônico de computação não deveria obviamente transmitir a essência da computabilidade?

Além disso, caso não estivesse claro, eu sei que os DFAs não são modelos completos de computação.

Obrigado pelas respostas.

Bem, um DFA é apenas uma máquina de Turing que só pode se mover para a direita e que deve aceitar ou rejeitar assim que ficar sem caracteres de entrada. Portanto, não tenho certeza se alguém realmente pode dizer que um DFA é natural, mas uma máquina de Turing não.

Crítica da questão à parte, lembre-se de que Turing estava funcionando antes da existência dos computadores. Como tal, ele não estava tentando codificar o que os computadores eletrônicos fazem, mas sim a computação em geral. Meus pais têm um dicionário da década de 1930 que define computador como "alguém que calcula" e é basicamente de onde Turing vinha: para ele, naquela época, o cálculo era sobre regras de slides, tabelas de log, lápis e pedaços de papel. Nessa mentalidade, reescrever símbolos em uma fita de papel não parece uma má abstração.

OK, tudo bem, você está dizendo (espero!), Mas não estamos mais na década de 1930, por que ainda usamos isso? Aqui, não acho que exista uma razão específica. A vantagem das máquinas Turing é que elas são razoavelmente simples e somos decentemente bons em provar coisas sobre elas. Embora especificar formalmente um programa de máquina de Turing para executar uma tarefa específica seja muito entediante, uma vez que você o tenha feito algumas vezes, você tem uma intuição razoável sobre o que eles podem fazer e não precisa mais escrever as especificações formais. O modelo também é facilmente estendido para incluir outros recursos naturais, como acesso aleatório à fita. Portanto, eles são um modelo bastante útil que entendemos bem e também temos um entendimento muito bom de como eles se relacionam com computadores reais.

Poder-se-ia usar outros modelos, mas seria preciso fazer uma enorme tradução entre os resultados do novo modelo e o vasto corpo de trabalho existente sobre o que as máquinas de Turing podem fazer. Ninguém inventou um substituto para as máquinas de Turing que tiveram grandes vantagens o suficiente para fazer com que parecesse uma boa idéia.

Você está fazendo várias perguntas diferentes. Deixe-me responder brevemente, um por um.

O que é tão importante no modelo de máquina de Turing?

$\lambda$

Na época, a tentativa de Turing de definir computabilidade parecia a mais satisfatória. Acabou que todos os modelos de computação descritos acima são equivalentes - todos descrevem a mesma noção de computabilidade. Por razões históricas, o modelo de Turing surgiu como a maneira mais canônica de definir computabilidade. O modelo também é muito rudimentar e fácil de trabalhar, em comparação com muitos outros modelos, incluindo os listados acima.

A ciência da computação usual ensina as máquinas de Turing como a definição de computabilidade e as usa também para explorar a teoria da complexidade. Porém, os algoritmos são analisados ​​com relação a um modelo mais realista conhecido como máquina de RAM, embora esse problema geralmente seja varrido para debaixo do tapete como um segredo para os conhecedores.

Os DFAs não são um modelo melhor?

Essa foi a motivação original por trás do famoso artigo de Rabin e Scott, autômatos finitos e seus problemas de decisão:

As máquinas de Turing são amplamente consideradas o protótipo abstrato dos computadores digitais; Os trabalhadores no campo, no entanto, sentem cada vez mais que a noção de uma máquina de Turing é muito geral para servir como um modelo preciso de computadores reais. É sabido que, mesmo para cálculos simples, é impossível atribuir um limite superior a priori à quantidade de fita que uma máquina de Turing precisará para qualquer cálculo. É precisamente esse recurso que torna o conceito de Turing irrealista.

Nos últimos anos, a idéia de um autômato finito apareceu na literatura. São máquinas com apenas um número finito de estados internos que podem ser usados ​​para memória e computação. A restrição de finitude parece dar uma melhor aproximação à idéia de uma máquina física. Obviamente, essas máquinas não podem fazer tanto quanto as máquinas de Turing, mas a vantagem de poder calcular uma função recursiva geral arbitrária é questionável, uma vez que poucas dessas funções aparecem em aplicações práticas.

Porém, apesar de as máquinas de Turing serem fortes demais, os DFAs são fracos demais . Atualmente, os teóricos preferem a noção de computação do tempo polinomial , embora essa noção também não esteja isenta de problemas. Dito isto, os DFAs e os NFAs ainda têm seus usos, principalmente em compiladores (usados ​​para análise lexical) e dispositivos de rede (usados ​​para filtragem extremamente eficiente).

O modelo da máquina de Turing não é muito limitado?

A tese de Church-Turing afirma que as máquinas de Turing capturam a noção física de computabilidade. Yuri Gurevich liderou uma tentativa de provar esta tese, formulando uma classe mais geral de dispositivos de computação conhecidos como máquinas de estado abstrato e provando que eles são equivalentes em potência às máquinas de Turing. Talvez essas máquinas sejam análogas ao seu modelo idealizado.

O significado subjacente é sobre a ideia da equivalência de Turing. O modelo exato não é importante, desde que seja equivalente a Turing. Mas é melhor usar um modelo mais simples para que você possa provar a equivalência com outros modelos com mais facilidade.

Mais exatamente, é melhor facilitar a simulação desse modelo em outros modelos, pois sabemos que a maioria das linguagens de programação avançadas são equivalentes a Turing (com certas suposições sobre endereços de memória) e podem ser usadas para simular outros modelos.

Existem outros modelos, como o cálculo lambda e as gramáticas (reescrita de cadeias). Mas é mais fácil definir restrições de tempo e espaço em uma máquina de Turing. Você também pode usar uma linguagem de programação como o Brainfuck, mas requer trabalho desnecessário para, por exemplo, redefinir os símbolos para obter uma modificação logicamente trivial às vezes.

Portanto, a máquina de Turing parecia bastante apropriada para mim se você tivesse que aprender um único modelo para tudo. Mas se você quiser aprender vários modelos de qualquer maneira, não vejo nada errado em aprender cálculo lambda para a idéia de equivalência de Turing, Brainfuck por provar outros modelos equivalentes a Turing e linguagens de programação práticas (melhor com pilha acessível e sem variáveis ​​ocultas) para restrições de tempo / espaço, e apenas considere a máquina de Turing uma ferramenta para provar essas coisas equivalentes se ninguém se incomodar em encontrar uma maneira de contorná-la. Isso acontece naturalmente se você não começou aprendendo a teoria subjacente primeiro, mas somente quando as achou úteis.

Gostaria de responder a esta parte da pergunta, adicionada em uma edição:

"O modelo canônico de computação não deveria obviamente transmitir a essência da computabilidade?"

$T$$T$$T$

Essa é uma das essências da computabilidade: qualquer que seja a noção geral de computabilidade que se tenha em mente, deve haver uma única máquina que faça tudo isso. É exatamente isso que uma máquina universal de Turing faz. É também o que os computadores modernos fazem (sujeito à idealização fisicamente irrealista de ter memória infinita).

Outra maneira de colocar isso, que aborda diretamente sua preocupação de que as máquinas de Turing não são mínimas, é que elas são tão mínimas quanto possível, sujeitas ao requisito de que descrevam uma noção geral de computabilidade para a qual existe uma máquina universal.

Máquinas de Turing não devem ser usadas literalmente; programar neles é algo que se faria apenas uma vez como exercício, para entender como eles funcionam.

Eles não foram especificamente feitos para "fazer" nada. Eles não precisam ser mínimos, não precisam se sentir confortáveis ​​para trabalhar.

Eles são simplesmente o modelo de uma máquina que você poderia construir, que seria tão expressiva e poderosa quanto qualquer outra máquina que você pudesse construir no universo físico (tanto quanto sabemos hoje).

Eles foram definidos por Turing da maneira como são, pelos seguintes motivos:

• Ser capaz de provar que eles abrangem todo e qualquer algoritmo em que poderíamos pensar.
• Trabalhar no problema de parada / problema de decisão.
• Ser capaz de reduzir qualquer outra máquina / idioma para esta.

Teria sido possível escolher outro idioma? Com certeza! Qualquer um dos idiomas completos que conhecemos hoje poderia ter sido usado. Mas teria sido muito mais difícil construir a base teórica em uma máquina mais complexa.

Eu argumentaria que eles nem sequer são um "modelo popular de computação"; ninguém jamais computaria nada com uma máquina de Turing. É um conceito puramente teórico, elaborado por cientistas da computação teórica, para tcs.

Por que é popular, talvez o mais popular? Você deve se lembrar que Turing evitou essa "máquina" muitos anos antes dos computadores eletrônicos. A MT é operada com um papel, uma caneta, uma borracha e, por último mas não menos importante, um cérebro humano. Então todo mundo é capaz de executar um "cálculo" com esta máquina. Todo mundo significa uma pessoa que nunca aprendeu computadores, programação de idiomas. É simples de usar. Quando você pensa sobre isso, descobre um paradoxo: esta máquina é uma montagem de quase nada, mas você pode operar tudo. Na minha opinião, o paradoxo do "quase nada / versus / tudo" é a razão pela qual é popular. Eu observaria que a MT não explica explicitamente a recursão, mas trata apenas de "salto". Esse recurso (explicitamente falando sobre recursão) pode ser uma fonte de dor de cabeça para novatos, por exemplo, no cálculo lambda, o conceito de combinador Y é quase incompreensível; Mais precisamente, a MT é popular porque o paradoxo do "quase nada / versus / tudo" sem a dor de cabeça da recursão.