Quase todas as linguagens de programação usadas sãoTuring Completee, embora isso permita que o idioma represente qualquercomputável algoritmo, ele também vem com seu próprio conjunto deproblemas. Como todos os algoritmos que escrevo têm a intenção de interromper, gostaria de representá-los em uma linguagem que garanta que eles serão interrompidos.

Expressões regulares usado para combinar cordas emáquinas de estado finito são usados quandolexing, mas gostaria de saber se existe uma linguagem mais geral e abrangente que não seja completa para Turing.

editar: Devo esclarecer que, por "objetivo geral", não quero necessariamente ser capaz de escrever todos os algoritmos de parada na linguagem (não acho que exista essa linguagem), mas suspeito que haja threads comuns nas provas de interrupção que pode ser generalizado para produzir uma linguagem na qual todos os algoritmos são garantidos para parar.

Há também outra maneira de resolver esse problema - eliminar a necessidade de memória teoricamente infinita. Depois de limitar a quantidade de memória permitida pela máquina, o número de estados em que a máquina se encontra é finito e contável e, portanto, é possível determinar se o algoritmo será interrompido (não permitindo que a máquina se mova para um estado em que se encontrava antes )