A entrada para uma máquina de Turing pode ter um comprimento infinito?

26

Considerando apenas o alfabeto , as cadeias que podem ser fornecidas como entrada para as máquinas de Turing são do conjunto . Mas faz sentido que a entrada seja uma sequência binária infinita? Por exemplo, se uma máquina de Turing aceita todas as cadeias que começam com 0, uma cadeia binária de zeros infinitos também pertence ao idioma aceito pela máquina de Turing?Σ={0,1}Σ

sashas
fonte

Respostas:

21

Não há problema em executar uma máquina de Turing em uma fita inicializada com uma sequência infinita, embora isso geralmente não seja considerado. No entanto, ainda precisamos que a máquina termine em tempo finito. Também existem noções de computação em tempo infinito, que podem ser apropriadas aqui.

Yuval Filmus
fonte
4
Terminar os cálculos em tempo finito enquanto a entrada é infinita parece um desafio difícil.
Mastro
5
@ Mas não necessariamente. Você simplesmente não pode ler toda a entrada.
Yuval Filmus
11
@JulesMazur A palavra-chave é hipercomputação .
Yuval Filmus
3
@JulesMazur Você não precisa necessariamente de hipercomputação. O programa pode continuar gravando em uma fita de saída e o resultado converge para uma sequência infinita, como em uma Máquina de Turing Tipo II.
Jkabrg 18/10
11
Eu acho que você terá dificuldade se permitir seqüências de caracteres inteiras como entrada. Em particular, o conjunto de entradas não é mais contável, o que quebra várias provas.
Taemyr 19/10/2015
17

Essa é uma das características das máquinas de Turing tipo 2 . Eles são usados, entre outras coisas, para analisar a computabilidade das funções entre números reais. Ainda mais interessante, eles são usados ​​para analisar a computabilidade de operadores como a integração.

Fato interessante: a integração numérica exata é computável.

jkabrg
fonte
5

Para responder à pergunta "faz sentido", isso pode até ser útil se você considerar as máquinas de Turing que são executadas em tempo finito.

Especificamente, essa é uma maneira muito útil de pensar em máquinas de Turing sem prefixo . São máquinas cujo conjunto de entradas interrompidas é livre de prefixo; isto é, nenhuma entrada que faça com que a máquina pare é o prefixo de outra. Eles são equivalentes em potência às máquinas de Turing comuns, mas somente se permitirmos que a máquina de Turing decida suas próprias entradas de parada: ie. o usuário não tem idéia em quais entradas a máquina interromperá (e essa é uma propriedade indecidível).

Uma maneira de ver isso é como uma máquina de Turing comum com uma fita de entrada infinita unidirecional com uma cabeça de fita que não pode voltar atrás. O usuário enche a fita com bits e executa a máquina. Esta é, por definição, uma máquina de Turing sem prefixo. Se a máquina parar, ela deve ter lido apenas um número finito de bits e nenhum prefixo dessa parte da fita pode ser um programa, ou a máquina teria parado lá.

Essa é uma boa maneira de falar sobre distribuições de probabilidade computáveis: o usuário preenche a fita com bits aleatórios (a fonte de aleatoriedade da máquina) e a máquina cospe uma sequência de bits aleatória. O conjunto de todas essas máquinas de Turing corresponde ao conjunto de distribuições computáveis ​​(especificamente as semimensas semicomputáveis ​​inferiores).

A vantagem da entrada infinita é que não precisamos especificar o que a máquina faz se lhe dermos o prefixo de um programa de parada, ou seja. a máquina tenta ler além do final da entrada que fornecemos.

Pedro
fonte
2

Mesmo se você não tiver essa fita, poderá empregar outra máquina de Turing para produzi-la.

Uma máquina de Turing tem acesso à fita de dados vazia, mas infinita (ou algumas fontes dizem "a máquina possui apenas uma pequena fábrica de fitas"). Portanto, ele pode inicializá-lo com algum padrão de dados programável e, em seguida, a fita pode ser consumida como entrada de outra máquina de Turing.

Obviamente, se seu conteúdo é tal que nenhum algoritmo pode ser definido como produzi-lo, esse conteúdo não pode ser criado pela máquina de Turing.

h22
fonte
6
Não tenho certeza de como isso responde à pergunta. De qualquer forma, nem todas as seqüências infinitas podem ser geradas pelas máquinas de Turing, pois existem inúmeras seqüências infinitas sobre qualquer alfabeto com pelo menos dois símbolos, enquanto que existem apenas muitas máquinas de Turing e muitas entradas finitas para semear.
David Richerby
2

Existem alguns casos em que entradas infinitas podem ser consideradas e reduzidas à ação de uma máquina de Turing "padrão". Por exemplo, considere um padrão finito de repetição infinita especificado na entrada. Pode-se criar uma máquina de Turing que monitora quanto desse padrão infinito foi modificado pelas ações atuais da cabeça da fita, usando uma quantidade finita de memória / armazenamento em fita. Em outras palavras, "simula equivalentemente" um padrão de tamanho infinito na fita.

Outro caso em que "entrada infinita" foi considerada é a análise da equivalência / completude de Turing dos autômatos celulares. em uma prova complexa, Cook introduziu um conceito agora referido por alguns como "equivalência fraca de Turing" na conversão de operações de regra CA 110 em operações de máquina de Turing que iniciam em uma fita inicial especificada infinitamente, mas com padrões de tamanho finito (repetitivos).

vzn
fonte
11
Os termos "entrada infinita" e "codificação finita de um objeto infinito" são claramente distintos e elementares (toda linguagem regular infinita com seu mínimo DFA é um exemplo). Eles não devem ser confundidos aqui.
Raphael
2
sim DFAs podem ser usados ​​para a codificação descrita. como esboçado uma fita com uma codificação finita de uma cadeia de comprimento infinito (por meio de padrões finitos repetidos) é diferente / semelhante em capacidade a uma fita com apenas cadeias finitas.
vzn
1

Nas linguagens formais, uma string é, por definição, uma sequência finita de símbolos. Uma máquina de Turing clássica possui uma fita infinita com uma sequência de entrada finita. Como tal, embora não haja limite para a duração da entrada, ela não pode ser infinita.

Dito isto, existem muitas máquinas alternativas que funcionam de maneira semelhante a uma TM, mas com sequências de entrada infinitas.

Se faz sentido ter uma entrada de tamanho infinito depende do objetivo. Estritamente no contexto das Máquinas de Turing, não faz sentido (já que não é possível), mas no contexto das Máquinas do tipo Turing, faz sentido e tem muitas aplicações.

todo mundo
fonte
4
É perfeitamente possível ter seqüências infinitas. De fato, existe um ramo inteiro da teoria dos autômatos que lida com essa situação exata. E, considerando que a única alteração necessária à definição de máquinas de Turing para permitir que elas lidem com entradas infinitas é excluir a condição que diz que a entrada deve ser finita, discordo que "não faz sentido" falar sobre máquinas de Turing e cordas infinitas.
David Richerby
11
@ DavidRicherby: parece que estamos de acordo. Sinta-se à vontade para me informar como posso reformular o último parágrafo para deixar mais claro que ele é estritamente apenas no contexto das Máquinas de Turing originais, clássicas e não adulteradas (onde as entradas são por definição finitas), que não faz sentido falar sobre entrada de comprimento infinito. Assim que excluímos a condição, ela não é mais estritamente uma TM, mas (o que eu chamei) de uma máquina do tipo Turing.
todo mundo
11
Discordo que o dispositivo deixa de ser uma máquina de Turing apenas porque você o inicia com infinitas coisas na fita. A máquina ainda é a mesma máquina; você acabou de alterar as condições iniciais. As definições de como as máquinas de Turing se relacionam com os idiomas de seqüências finitas (por exemplo, idiomas decidíveis ou semi-decidíveis) são em termos de entradas finitas, mas isso não significa que a máquina o exija. Da mesma forma, seu computador não deixaria de ser um computador se você colocasse uma pilha infinita de CDROMs ao lado.
David Richerby
11
@DavidRicherby Bem, tecnicamente, uma máquina de Turing é uma máquina que recebe entrada finita. Se você alterar essa restrição na definição, define outra coisa. A idéia por trás da computação ainda é a mesma, em certo sentido, mas como você expressa a complexidade agora? Questões muito diferentes.
Raphael