Casi todos los lenguajes de programación utilizados sonTuring completo, y si bien esto ofrece el lenguaje para representar cualquiercalculable algoritmo, también viene con su propio conjunto deproblemas. Dado que todos los algoritmos que escribo están destinados a detenerse, me gustaría poder representarlos en un lenguaje que garantice que se detendrán.

Expresiones regulares utilizado para unir cadenas ymáquinas de estados finitos se usan cuandolexing, pero me pregunto si hay un lenguaje más general que, en general, no sea completo para Turing.

editar: Debo aclarar que, por "propósito general", no necesariamente quiero poder escribir todos los algoritmos de detención en el idioma (no creo que exista tal lenguaje), pero sospecho que hay hilos comunes en las pruebas de detención. eso se puede generalizar para producir un lenguaje en el que se garantice que todos los algoritmos se detengan.

También hay otra forma de abordar este problema: eliminar la necesidad de memoria teóricamente infinita. Una vez que limite la cantidad de memoria que permite la máquina, el número de estados en los que se encuentra la máquina es finito y contable, y por lo tanto puede determinar si el algoritmo se detendrá (al no permitir que la máquina se mueva a un estado en el que estaba antes) )