Travar em línguas não-Turing-completos

Question

O problema da parada não pode ser resolvido para Turing línguas completas e pode ser resolvido trivialmente para alguns idiomas não-TC como expressões regulares onde sempre paradas.

Eu queria saber se existem línguas que tem tanto a capacidade de parar e não parou, mas admite um algoritmo que pode determinar se ele pára.

Answer 1

Sim. Uma classe importante deste tipo são função recursiva primitiva . Esta classe inclui todas as coisas básicas que você espera ser capaz de fazer com os números (adição, multiplicação, etc.), bem como algumas classes complexas como @adrian mencionou (expressões regulares / finito autômatos, gramáticas livres de contexto / pushdown autómatos). Há, no entanto, existem funções que não são recursiva primitiva, tais como a função Ackermann .

É realmente muito fácil de entender função recursiva primitiva. Eles são as funções que você poderia entrar em uma linguagem de programação que não tinha verdadeiro recursão (para uma função f não pode chamar-se, seja diretamente ou por chamar outra função g que, em seguida, chama f, etc.) e tem laços Enquanto que-não, em vez de ter delimitada para-loops. A delimitada loop for é um como "para i de 1 a r" onde r é uma variável que já foi calculado no início do programa; Além disso, não pode ser modificada dentro do loop for. O ponto de tal linguagem de programação é que todas paradas do programa.

A maioria dos programas que escrevemos são recursiva realmente primitiva (quero dizer, pode ser traduzido em tal língua).

Answer 2

O parada problema não age sobre idiomas. Em vez disso, ele atua em máquinas (ou seja, programas): pergunta se um determinado paradas programa em um dado de entrada

.

Talvez você queria perguntar se ele pode ser resolvido por outros modelos de computação (como expressões regulares, que você mencionou, mas também como push-down autômatos ).

A interrupção pode, em geral, ser detectado em modelos com recursos finitos (como expressões regulares ou, equivalentemente, autômatos finitos, que têm um fixas número de estados e nenhum armazenamento externo). Isso é facilmente realizado por enumerando todas as configurações possíveis e verificar se a máquina entra a mesma configuração de duas vezes (indicando um ciclo infinito); com finita recursos, podemos colocar um limite superior na quantidade de tempo antes que nós deve ver uma configuração repetida se a máquina não parar.

Normalmente, os modelos com recursos infinitos (TMS e PDAs ilimitados, por exemplo), não pode ser verificada-parada, mas seria melhor para investigar os modelos e seus problemas abertos individualmente.

(Desculpe para todos os links da Wikipedia, mas na verdade é um recurso muito bom para esse tipo de pergunta.)

Answer 3

A resposta curta é sim, e essas línguas pode até mesmo ser extremamente útil.

Houve uma discussão sobre isso há alguns meses na LTU: http://lambda-the-ultimate.org/node/2846