Por que a fita não faz parte da definição de uma máquina de Turing?

Eu me perguntei por que as fitas não fazem parte da definição formal de uma máquina de Turing. Considere, por exemplo, a definição formal de uma máquina de Turing na página da Wikipedia . A definição, seguindo Hopcroft e Ullman, inclui: o conjunto finito de estados , o alfabeto de fita , o símbolo em branco , o estado inicial , o conjunto de estados finais , e a função de transição . Nenhuma delas é a própria fita.Γ b ∈ Γ q 0 ∈ Q F ⊆ Q δ : ( Q ∖ F ) × Γ → Q × Γ × { L , R $Q$ $\Gamma$$b \in \Gamma$$q_0\in Q$$F\subseteq Q$$\delta:(Q\backslash F)\times \Gamma\rightarrow Q\times\Gamma\times\{L,R\}$

Considera-se sempre que uma máquina de Turing trabalha em uma fita, e a função de transição é interpretada como mover a cabeça, substituir o símbolo e mudar o estado. Então, por que a fita é deixada de fora da definição matemática de uma máquina de Turing?

Pelo que posso ver, a definição formal em si não parece implicar que a Máquina de Turing opere como costuma ser descrita informalmente (com a cabeça se movendo em uma fita). Ou faz?

Para definir formalmente uma instância de uma máquina de Turing (não o conceito geral), não é necessário mencionar explicitamente a própria fita ou seu conteúdo. Para indicar uma configuração dessa máquina específica ou um cálculo realizado por ela, é quando você precisa de alguma forma de notação para descrever o conteúdo da fita.

É uma área um pouco cinza, mas eu diria que a definição divide o modelo da instância . Se você deseja ter uma idéia simples, pense em hardware x software.

O modelo é o hardware: o é uma cabeça. Há uma fita. A fita é infinita em um lado e contém espaços em branco (além da entrada). A cabeça pode se mover um passo de cada vez.

A instância é o software: a entrada determina o que a fita contém no início, a função de estado / transição informa como a cabeça se move e como a máquina "funciona". Os estados finais dão o significado de sucesso / fracasso.

Ambos os parâmetros são configuráveis ​​--- ambos podem ser alterados. Existem modelos alternativos com duas fitas, duas cabeças, fitas frente e verso, fita não vazia, etc. .

O que torna um parâmetro parte do modelo e não parte da instância? É apenas uma área cinzenta e não acho que haja uma boa resposta para isso (talvez eu esteja errado. Alguém?). Parece que a separação para "Hardware" / "Software" faz mais sentido para classificar parâmetros como parte do modelo ou parte da instância, mas podemos imaginar outros universos nos quais essa classificação é diferente (por exemplo, onde a MT é um Tupla de 8, que também contém = a posição da cabeça no início, ou = o número de fitas ou = um padrão que aparece repetidamente na fita após o final da entrada, etc.)M p a t t e r $P$$M$$pattern$

Aqui já são boas respostas, mas tento fazer uma sucinta.

As definições não devem ser excessivas ou detalhadas.

De fato, a definição da máquina de Turing também define a abstração da fita. O q0 - é o início da fita. O alfabeto é um conteúdo da fita. E δ: (Q ∖ F) × Γ → Q × Γ × {L, R} afirma que a fita esquerda e direita e o infinito nas duas direções.

Então, fita, cabeça, move apenas representações humanas do modelo, elas já estão no modelo matemático , mas elas mesmas não são um modelo formal.

Les fornece uma resposta concisa e correta: as definições matemáticas são tão concisas quanto possível, e incluir explicitamente uma fita infinita na definição de uma máquina de Turing tornaria sua definição muito menos concisa, por isso não o fazemos.

Isso não responde à pergunta: por que ? Como a definição pode excluir a fita infinita quando precisamos de uma?

A resposta: nós não. Em certo sentido, as máquinas de Turing na verdade não exigem fitas infinitas, e sua definição deixa isso claro.

Por definição, a movimentação de uma máquina de Turing leva a máquina de uma configuração para outra; uma configuração inclui uma cadeia finita , que consideramos um fragmento finito de fita escrita. Cada movimento move a cabeça da fita em uma posição ou sobrescreve o símbolo sob a cabeça da fita. No entanto - e isso é essencial para o seu funcionamento:

• sempre que removemos esse pedaço fininho de barbante, assumimos que o símbolo sob a cabeça da fita é , o símbolo em branco.$b$
• podemos fazer isso infinitamente com frequência .

Portanto, para que máquinas arbitrárias de Turing operem indefinidamente, é necessário um suprimento infinito de células de fita em branco nas duas extremidades. Enquanto isso, a qualquer momento, sua configuração, descrevendo o trecho de fita em que escreveu, é sempre finita: após etapas, a cabeça da fita nunca pode ter se desviado além de células do seu ponto inicial.$n$$n$

Uma maneira de reformular isso é dizer: a máquina opera em uma fita infinita, totalmente preenchida com espaços em branco, exceto por um fragmento finito em que sua cabeça está ligada. É o que a maioria das explicações diz.

Outra maneira de reformular isso é dizer: a máquina opera com uma fita finita, estendida com espaços em branco sempre que sua cabeça se afasta da fita em cada extremidade.

Ambas são formas válidas de conceituar como a máquina opera: nos dois casos, se você realmente tivesse uma máquina operando assim, ela implementaria corretamente uma máquina de Turing.

Se tudo o que você está interessado é ensinar aos alunos como as máquinas de Turing funcionam, provavelmente não importa qual conceitualização você escolher.

No entanto, acho que a primeira conceituação é um erro, por duas razões:

• Isso não é realista . Na verdade, não podemos construir uma máquina com uma fita infinita. Nós podemos construir uma máquina com uma fita finito estendido a pedido.
• É contra-intuitivo. Não pensamos nas máquinas que executam tarefas arbitrariamente frequentemente como contendo uma quantidade infinita de recursos. Por exemplo, não pensamos em uma fotocopiadora como contendo uma quantidade infinita de papel de cópia. Máquinas de Turing modelam a atividade da computação. Eles modelam o que aconteceria se substituíssemos um computador (que na época de sua invenção era uma mulher realizando cálculos em papel) por uma máquina capaz de realizar cálculos arbitrários programáveis. Não pensamos nessa mulher como contendo uma quantidade infinita de papel. Em vez disso, assumimos que ela receberá toda a quantidade de papel de que precisa e consideramos uma falha em fazê-lo como uma falha do meio ambiente, em vez de dizer que essa mulher não pode existir. Por que não fazer o mesmo com a máquina?
• Convida conclusões enganosas. Eu já vi muito isso. Por exemplo:
  • As pessoas dizem que máquinas de Turing não podem realmente ser construídas, enquanto máquinas de estado finito podem. Bem, não podemos construir máquinas arbitrárias de grandes estados finitos, assim como não podemos fornecer quantidades arbitrárias de fita a uma máquina de Turing.
  • As pessoas dizem que as máquinas de Turing não modelam computadores corretamente, enquanto as máquinas de estados finitos sim. Isso serve para destacar um ponto importante: se tudo o que nos interessa é usar uma máquina para decidir idiomas de entrada, um computador operando apenas em seu armazenamento interno (fixo) pode implementar totalmente qualquer máquina de estado finito até um determinado tamanho, enquanto ele não pode implementar completamente a maioria das máquinas de Turing, pois ficará sem armazenamento interno para muitas delas. No entanto, isso geralmente é generalizado ao se dizer: computadores são máquinas de estados finitos, o que é enganoso:
    • Não mostra uma imagem realista da maioria dos programas de computador. De fato, a programação de fluxo de dados é de fato baseada em máquinas de estados finitos, mas a programação imperativa tradicional não; ele usa programas muito mais próximos das instâncias da máquina de Turing.
    • Na prática, os computadores também interagem com fontes externas de entrada, saída e armazenamento que não têm tamanho fixo.
    • Máquinas de Turing não deveriam modelar computadores em primeiro lugar; eles modelam computação arbitrária.

Resumindo: a idéia de máquinas de Turing usando ou contendo uma fita infinita serve para enfatizar um ponto técnico importante, mas não é necessariamente a maneira mais intuitiva de pensar sobre as máquinas de Turing, e convida a conclusões incorretas. Use com cuidado.