Por que o problema da parada é decidível para o LBA?

Eu li na Wikipedia e alguns outros textos que

O problema de parada é [...] decidível para máquinas determinísticas de autômatos limitados lineares (LBAs) [e] com memória finita.

Mas, anteriormente, está escrito que o problema de parada é um problema indecidível e, portanto, a TM não pode resolvê-lo! Como o LBA é definido como um tipo de TM, o mesmo não deve valer para eles?

O problema da parada é solucionável para qualquer máquina de Turing que utilize uma quantidade limitada de espaço conhecida, por uma generalização do argumento dado por Yonatan N. Se a quantidade de espaço for , o tamanho do alfabeto será A e o número de estados será Q , em seguida, o número de configurações possíveis é Q S a S . Se a máquina parar, ela deverá parar dentro das etapas Q S A S , pois, caso contrário, pelo princípio do buraco de pombo, ela terá uma configuração repetida e ficará presa em um loop infinito. Portanto, para determinar se a máquina para, basta executá-la por Q S A $S$$A$$Q$$QSA^S$$QSA^S$$QSA^S$ etapas e veja se ele pára dentro desse prazo.

Você parece preso com um problema lógico.

Pelo fato de existirem livros que você não pode ler, você não pode deduzir que não pode ler nenhum livro.

Dizer que o problema da parada é indecidível para a Turing Machines (TM) significa apenas que existem máquinas para as quais não há como determinar se elas são interrompidas ou não por algum procedimento uniforme que sempre será interrompido.

No entanto, existem máquinas de Turing que param. Agora, pegue um subconjunto de Máquinas de Turing, chamado Nice Turing Machines (NTM), de forma que contenha apenas Máquinas de Turing que parem se e somente se a fita contiver um número par de símbolos. Se uma máquina M é conhecida desse conjunto, você tem uma maneira simples de decidir se M será interrompido: você verifica se o número de símbolos da fita é par (isso requer apenas dois dedos).

Mas esse procedimento não funcionará para a TM que não está no conjunto NTM. (que pena!)

Portanto, o problema da parada é decidível para o NTM, mas não para o TM em geral, mesmo que o conjunto NTM esteja incluído no conjunto.

Isso é realmente crítico, e algumas vezes esquecido, ao interpretar o resultado da indecidibilidade.

Pode ser que se prove que uma propriedade importante é indecidível para uma família muito grande de objetos matemáticos ou computacionais.

Isso não significa que você deve parar de procurar uma solução, mas apenas que não encontrará uma para toda a família.

O que você pode fazer é identificar subfamílias relevantes para as quais a solução do problema permanece importante e tentar fornecer algoritmos para decidir se a propriedade vale para os membros dessa família menor.

Normalmente, a interrupção é indecidível para a MT em geral, mas é decidível, muitas vezes de maneira muito simples, para famílias grandes e úteis de autômatos, que podem ser vistos como casos especiais de MT.

Em resumo, um LBA possui um número finito de configurações, digamos D. Portanto, podemos executar as etapas D e concluir o resultado. Se for executado em mais de D etapas, pelo princípio do buraco de pombo, podemos dizer que está preso em um loop infinito.