Importância prática das máquinas de Turing?

Sou engenheiro eletricista e só tive um curso de CS na faculdade há 26 anos. No entanto, eu também sou um usuário dedicado do Mathematica.

Tenho a sensação de que as máquinas de Turing são muito importantes na ciência da computação. A importância é apenas na teoria da ciência da computação? Se existem implicações / aplicações práticas, quais são algumas delas?

A importância das máquinas de Turing é dupla. Primeiro, as máquinas de Turing foram um dos primeiros (se não o primeiro) modelo teórico para computadores, datado de 1936. Segundo, muita ciência da computação teórica foi desenvolvida com as máquinas de Turing em mente e, portanto, muitos dos resultados básicos são na linguagem das máquinas de Turing. Uma razão para isso é que as máquinas de Turing são simples e, portanto, passíveis de análise.

Dito isto, as máquinas de Turing não são um modelo prático para a computação. Como engenheiro e usuário do Mathematica, eles não devem se preocupar com você. Mesmo na comunidade teórica da ciência da computação, as máquinas de RAM mais realistas são usadas nas áreas de algoritmos e estruturas de dados.

De fato, do ponto de vista da teoria da complexidade, as máquinas de Turing são polinomialmente equivalentes a muitos outros modelos de máquinas e, portanto, classes de complexidade como P e NP podem ser equivalentemente definidas em termos desses modelos. (Outras classes de complexidade são mais delicadas.)

As máquinas de Turing foram um dos primeiros modelos de computação, ou seja, foram desenvolvidas quando a computação em si não era muito bem compreendida (por volta de 1940). Quero focar em dois aspectos que (indiscutivelmente) os levaram a ser o modelo preferido na época, o que levou a ser o modelo mais estabelecido e, portanto, eventualmente padrão.

1. Simplicidade das provas
   Como modelo teórico, as máquinas de Turing têm o charme de serem "simples" no sentido de que o estado atual da máquina tem apenas tamanho constante. Todas as informações necessárias para determinar o próximo estado da máquina são um símbolo e um número de estado (controle). A alteração no estado da máquina é igualmente pequena, adicionando apenas o movimento da cabeça da máquina. Isso simplifica consideravelmente as provas (formais), em particular o número de casos a serem distinguidos.

   Compare esse aspecto com o modelo de RAM (quando não usado em sua forma minimalista): a próxima operação pode ser uma das várias operações, que pode acessar qualquer (dois) registros. Existem também várias estruturas de controle.

2. 
   $\lambda$$\mu$

   Para máquinas de Turing, no entanto, ambas as noções são facilmente definidas (e estavam no primeiro artigo de Turing sobre seu modelo, se bem me lembro). Como as considerações de eficiência logo foram muito importantes para realmente fazer coisas, essa foi uma vantagem definitiva das máquinas de Turing.

Assim, as máquinas de Turing foram estabelecidas como o modelo de computação, que pode ser visto como uma combinação de "acidente" histórico e algumas de suas principais propriedades. No entanto, muitos modelos foram definidos desde então e são avidamente usados, em particular para superar as deficiências das máquinas de Turing; por exemplo, eles são tediosos para "programar" (ou seja, definir).

Não conheço nenhuma aplicação direta na prática. Em particular, a prática da computação evoluiu paralelamente à (e, no começo, principalmente independentemente da) teoria da computação. As linguagens de programação foram desenvolvidas sem modelos formais de máquina. No entanto, é claro (em retrospectiva) que muitos avanços na prática da computação foram possibilitados pela teoria.

Além disso, lembre-se de que o valor que um conceito teórico teve para a prática deve ser medido considerando todos os descendentes, ou seja, trabalhos de acompanhamento, resultados e novas idéias possibilitadas por esse conceito. E a esse respeito, acho justo dizer que o conceito de máquinas de Turing (entre outras) revolucionou o mundo.

A única aplicação razoavelmente prática em que posso pensar (no sentido de que você pode realmente implementar uma máquina de Turing) é provar que uma linguagem de algum tipo tem poder suficiente.

Se você estiver projetando algum tipo de linguagem de programação (ou qualquer outra coisa destinada a computar as coisas), convém garantir que ela seja completa em Turing (ou seja, capaz de computar qualquer coisa computável) implementando uma máquina de Turing nisso.

Obviamente, você também pode implementar qualquer outra coisa que seja completa em Turing (como C ou lógica combinatória), mas às vezes uma máquina de Turing é a opção mais fácil.

A máquina de Turing é um modelo matemático de computação. Seus benefícios são: -

1. Verifique a decidibilidade Se a TM não puder resolver um problema em tempo contável, não poderá haver nenhum algoritmo que possa resolver esse problema (esse é o problema é indecidível).

Para um problema de decisão, se sua MT parar no tempo contável para todas as entradas de comprimento finito, podemos dizer que o problema pode ser resolvido por um algoritmo em tempo contável.

2. Classificar Problema TM ajuda a classificar problemas decidíveis em classes da Hierarquia Polinomial.

Suponha que descobrimos que o problema é decidível. Então, o objetivo se torna a eficiência com que podemos resolvê-lo. A eficiência foi calculada em número de etapas, espaço extra usado, comprimento do código / tamanho do FSM.

3. Projetar e implementar algoritmos para máquinas práticas TM ajuda a propagar a idéia de algoritmo em outras máquinas práticas. Após a verificação bem-sucedida de 1,2 critérios, podemos usar nossos dispositivos / computadores práticos para projetar e implementar algoritmos.

Máquinas de Turing são exercícios de boa mente com pouco uso prático. Não há mal em não ter um. Todas as aplicações de uma máquina de Turing são intuitivas ou uma questão de religião, porque não podem ser provadas ou refutadas.