Definição padrão de máquina de Turing

Eu segui dois livros famosos sobre "Autômatos e Teoria da Linguagem Formal":

1. Livro de Micheal Sipser
2. Livro de Jeffrey Ullman e John Hopcroft

nos dois livros, a definição de nível de tupla da máquina de Turing difere entre si. Embora o trabalho em nível abstrato seja o mesmo, mas os detalhes são diferentes. Por que não existe nenhuma definição padrão? Até alguns outros livros explicaram a máquina de Turing de maneira diferente.

Quando tentamos medir a complexidade de tempo do mesmo algoritmo nessas máquinas, o tempo exato também difere. Por que os autores / cientista não concordaram com uma definição padrão?

Não há definição padrão, pois é incomum usar os detalhes da definição de máquina de Turing. Em contraste com outras definições da matemática, as máquinas de Turing são objetos complicados cuja definição é difícil de usar diretamente. Em vez disso, invocamos a hipótese de Church-Turing e descrevemos as máquinas de Turing fornecendo algoritmos em vez de listar tuplas. Neste ponto, a definição exata de máquina de Turing não é importante.

Uma situação semelhante ocorre em outros casos, dos quais descreverei dois: sistemas numéricos e forçantes .

Os sistemas numéricos , especialmente os números reais, têm várias construções diferentes. Se você observar livros que contenham uma construção dos números reais, provavelmente verá construções diferentes, em alguns casos muito diferentes (por exemplo, cortes de Dedekind versus seqüências de Cauchy). No entanto, do ponto de vista do usuário, tudo o que nos preocupa é que os números reais que construímos satisfazem os axiomas do campo, além de serem completos e arquimedianos (o significado exato desses termos não é importante). Quase nunca usamos as definições subjacentes reais.

Forçar é uma importante técnica de prova na teoria dos conjuntos. Forçar pode ser definido de várias maneiras diferentes, sendo o mais popular forçar relações e modelos com valor booleano. (Um método menos popular é a lógica modal.) Esses métodos são todos equivalentes, mas o desenvolvimento formal pode ser um pouco diferente. Todos esses métodos levam às mesmas provas na teoria dos conjuntos, mas não há uma "oficial". Qual deles você escolhe apresentar em um livro ou curso de teoria dos conjuntos depende do seu gosto pessoal.

A definição exata de máquina de Turing importa se você estiver interessado no consumo exato de recursos, digamos, quantas etapas são necessárias para resolver um determinado problema. Como todas as definições razoáveis ​​das máquinas de Turing resultam nos mesmos tempos de execução até fatores constantes e, como geralmente não nos importamos com fatores constantes per se, a definição exata não importa e produz os mesmos resultados.

A mesma situação ocorre ao provar outros teoremas nos quais a hipótese de Church-Turing não pode ser usada. Por exemplo, ao provar o teorema de Cook de que SAT é NP completo, precisamos realmente nos referir à definição de máquina de Turing; mas a construção funcionará para muitas definições diferentes, da mesma maneira. Escolhemos uma definição arbitrariamente e a cumprimos, sabendo que o uso de qualquer outra variante resultará em uma prova um pouco diferente, mas ainda válida.

Isso acontece frequentemente; por exemplo, existem várias definições de autômatos finitos.

Geralmente, há duas coisas em que estamos interessados ​​em modelos de computação (e no TCS):

1. poder computacional e
2. medidas de custo.

Se 1. é o mesmo e 2. apenas difere insignificantemente (diriam os teóricos da complexidade, por um fator polinomial / polilogarítmico / constante / ...), podemos alternar entre (aproximadamente) definições equivalentes.

As condições podem ser comprovadas formalmente, desde que os modelos sejam formalmente definidos. Pode ser um exercício ilustrativo para você fazer isso.

Por que ter definições diferentes, então? Como uma ou outra prova pode ser mais fácil, ou um ou outro conceito é descrito com mais detalhes. Portanto, o objetivo de um curso / livro, a seleção de tópicos, a abordagem didática e o gosto do autor podem fazer com que uma definição funcione melhor que a outra.

Vou tentar adotar uma abordagem ligeiramente diferente das outras respostas e examinar em particular a questão da padronização.

É um pouco surpreendente que você se pergunte sobre essa situação. O livro Hopcroft-Ullman (eu uso a edição de 1979) fornece duas definições de PushDown Automaton (PDA): aceitação pelo estado final ou pela pilha vazia.

Se você ler a seção sobre técnicas de construção da Turing Machines (TM) (seção 7.4 na edição de 1979), elas declaram explicitamente:

Projetar máquinas de Turing escrevendo um conjunto completo de estados e uma função de próximo passo é uma tarefa visivelmente recompensadora. Para descrever construções complicadas de máquinas de Turing, precisamos de algumas ferramentas conceituais de "nível superior".

O restante da seção e as seções a seguir mostram todos os tipos de variações na definição de uma TM, estendendo ou limitando a definição, todas equivalentes.

O ponto é que, para cada problema em questão, escolheremos a definição que melhor será adaptada para resolver esse problema. Obviamente, cada uma dessas definições poderia funcionar em princípio. Mas, dependendo do problema, algumas definições fornecerão mais perspicácia em um problema específico e, assim, facilitarão as provas.

Considerando o caso das linguagens e gramáticas livres de contexto (CF), existem muitas formas normais que foram definidas: forma normal de Chomsky, forma normal de Greibach, forma binária. Todos podem gerar qualquer linguagem CF e podem ser vistos como variações da definição da gramática CF. É bom tê-los coexistindo, porque cada um deles tem um papel a desempenhar em algum contexto. Eles são intraduzíveis, mas a custo.

Se você tentar analisar o custo / complexidade da análise de CF, eles não são equivalentes, e isso deve ser levado em consideração. Esse problema de complexidade é muito mais crítico no caso do CF do que no TM, porque os analisadores de CF são muito usados ​​em situações de engenharia, enquanto o MT é uma ferramenta puramente teórica. Isso não impede que os engenheiros que usam a análise de CFs utilizem várias formas gramaticais para o mesmo idioma, de alguma maneira coordenada, a fim de levar em consideração vários problemas.

No caso das linguagens CF, pode ser uma questão crítica de engenharia , e era de se esperar que as gramares de CF e suas diferentes formas fossem normalizadas / padronizadas tanto quanto o tamanho das chaves ou o diâmetro dos fios elétricos. Na verdade, chegou a definir uma sintaxe precisa para escrever gramáticas de CF, o Backus Naur Form (BNF) .

A TM possui poucas aplicações de engenharia que justificariam a normalização e uma variabilidade potencial muito maior (o que é, no entanto, parcialmente levado em consideração ao considerar grandes variações, como fitas múltiplas, cabeças múltiplas, ...). Isso explica que havia pouca pressão para adotar uma forma padrão, dado que os matemáticos que os usam são tecnicamente maduros o suficiente para serem cuidadosos quando podem fazer a diferença, contando com precisão o número de movimentos. Mesmo para a complexidade, as pequenas variações nas definições geralmente não importam, porque consideramos apenas a complexidade assintótica e, muitas vezes, a complexidade assintótica até uma função polinomial.

É bastante comum em matemática (entre outras ciências) que diferentes autores escolham definições diferentes, que sejam equivalentes (ou equivalentes na maioria dos contextos), dependendo de seu gosto, visão de aplicações, visão da estrutura do problema, seus propósitos pedagógicos etc. As definições também evoluem com o tempo, à medida que mais se sabe sobre um problema e à medida que as perspectivas mudam. O mesmo vale para anotações. Essa variabilidade é uma fonte importante de progresso e entendimento. Os gregos estavam fazendo matemática excelente, mas é muito mais fácil com conceitos modernos (por exemplo, variáveis ), definições e notações.

Os padrões são frequentemente vistos como extremamente convenientes (chaves de boca e diâmetros de fio). Mas eles também podem ser um fator de rigidez que impede o progresso. A padronização é uma faca de dois gumes, por isso devemos embotá-la um pouco por segurança. As várias definições geralmente não são idênticas, mas próximas o suficiente para que as teorias possam se desenvolver mais ou menos da mesma maneira.