Por que o símbolo em branco não é considerado parte do alfabeto de entrada de uma máquina de Turing?

Definições de máquinas de Turing são sempre explícitas sobre o símbolo em branco não fazer parte do alfabeto de entrada.

Eu me pergunto o que dá errado quando você faria parte do alfabeto de entrada, porque efetivamente o símbolo em branco já parece fazer parte da entrada.

Para explicar que 'parece' na última frase, considere o seguinte.

Na configuração padrão, um número infinito de símbolos em branco aparece à direita da entrada. Quando a cabeça da fita se move sobre o primeiro símbolo em branco, a computação pode simplesmente continuar, pois não precisa ser um estado de aceitação ou rejeição.

Agora, suponha que o cálculo escreva símbolos subsequentemente do alfabeto de entrada à direita do primeiro símbolo em branco e retorne à posição mais à esquerda enquanto também retorna ao estado inicial. 'Começaria de novo' com uma fita diferente. Efetivamente, agora começa com uma entrada diferente, na qual existem símbolos de entrada à direita do espaço em branco que não existiam antes. A entrada parece incluir efetivamente o símbolo em branco. O comportamento adicional da máquina agora também pode ser diferente: depois de encontrar o espaço em branco novamente, ele agora encontrará símbolos diferentes à direita.

Supondo que esse cenário seja realmente possível, por que você não consideraria o símbolo em branco como parte do alfabeto de entrada e por que não permitiria incluí-lo como parte da entrada 'inicial'?

Talvez seja apenas uma maneira de definir a entrada de modo que nem sempre seja infinita?

turing-machines Confusão
fonte

Quando estava na aula, projetei máquinas de Turing que utilizavam a permissão β (o símbolo em branco local) em suas entradas como separadores de campo.

197 Joshua

Respostas:

O principal motivo é que ele permite que a máquina detecte o final de sua entrada: é (o caractere anterior) o primeiro espaço em branco. Se você permitir espaços em branco na entrada, a máquina nunca poderá saber se poderá encontrar mais entradas digitalizando mais para a direita. Obviamente, você pode resolver isso tendo um caractere especial "final de entrada", mas depois insistindo para que isso não apareça na entrada, para que você tenha mudado o problema para um nível mais profundo.

Também facilita muito a especificação das condições iniciais: a entrada é a seção não em branco da fita inicial, que deve ser finita e contígua. E se você quiser que um caractere em branco faça parte do alfabeto de entrada, sempre poderá adicionar um caractere extra (chame-o de "espaço" ou algo assim) e fazer com que a máquina se comporte da maneira que desejar quando a vir.

David Richerby
fonte

Ah, é claro, sem poder determinar o final da entrada inicial, alguns cálculos seriam impossíveis. Mas, caso contrário, não há nada de especial no símbolo. E acho que é questão de economia terminológica usar o símbolo em branco, já que você precisa desse em seu alfabeto. Eu acho que teria sido mais óbvio para mim quando definido inicialmente com um símbolo explícito de final de entrada e uma observação que não era estritamente necessária e geralmente deixada de fora.

Confusão

{00} \to 0, {11} \to 1, {10, 01} \to b

$\{00\} \rightarrow 0, \{11\} \rightarrow 1, \{10, 01\} \rightarrow b$

Vendo que a máquina de Turing precisa de regras que governem o que faz se ler um espaço em branco, e pode ter uma regra que diga para ele escrever um espaço em branco, isso não significa que o espaço em branco é realmente parte de seu alfabeto? Não vejo por que a entrada pode não conter espaços em branco. Que tal codificar itens de entrada usando caracteres não em branco e um único espaço em branco como separador? Em seguida, vários espaços em branco consecutivos indicam o final da entrada.

Rosie F

@YonatanN Claro. Isso é "simples", mas ter um símbolo em branco é mais simples.

David Richerby

@RosieF O espaço em branco faz parte do alfabeto da fita; o alfabeto de entrada é um subconjunto disso. E, com certeza, você pode configurar convenções sobre como a entrada pode conter espaços em branco em determinadas circunstâncias (como você fez), mas isso apenas torna as definições mais complexas. Definições mais complexas significam que é mais difícil provar coisas sobre as máquinas de Turing. E, como as máquinas Turing são realmente usadas apenas para provar coisas (se você deseja projetar um computador real, não será uma TM), isso não é uma boa opção.

David Richerby

Você pode definir o símbolo em branco para fazer parte do alfabeto. O problema é que, se uma máquina de Turing com a entrada b010010b (em que b significa em branco ) nunca passa do segundo b, a máquina se comportará exatamente da mesma maneira em todas as entradas que começam com b010010b.

Essas máquinas de Turing são chamadas de máquinas de Turing com prefixo e são muito úteis para provar alguns teoremas sobre a complexidade de Kolmogorov.

Peter Shor
fonte

Resposta muito curta: o alfabeto da fita é o conjunto de símbolos que podem aparecer na fita e inclui o símbolo em branco. O alfabeto de entrada é o conjunto de símbolos que podem aparecer na entrada inicial e não inclui o símbolo em branco. O alfabeto principal com o qual a máquina se importa é o alfabeto da fita: ele ainda precisa de regras para o que fazer quando vê um espaço em branco, por exemplo.

Essa distinção é importante, como já foi dito, para que a máquina possa saber onde termina sua entrada. É o mesmo motivo pelo qual você não pode (útil) colocar um caractere zero no meio de uma string em C: o caractere zero é reservado para significar "o último caractere diferente de zero antes que este seja o final dos dados, então quando você vê isso, está pronto ". Se você precisar esperar zero caracteres no meio da string, a escrita strlenfica muito mais difícil.

Draconis
fonte