Los idiomas que no están completos en Turing son bastante limitados. El lenguaje completo no Turing más utilizado son las expresiones regulares. Son bastante útiles, pero claramente extremadamente limitados. Ni siquiera son capaces de realizar operaciones aritméticas básicas.
SQL tampoco es Turing completo.
La programación de uso general siempre requerirá un lenguaje completo de Turing. Es capaz de expresar cualquier cosa que una computadora pueda hacer. Hacer un lenguaje completo de Turing no es difícil; Por lo general, solo requiere agregar algún tipo de memoria de acceso arbitrario y una pila (a través de la recursión u otra estructura de bucle indefinido).
- Dada una matriz sin clasificar que contiene un número impar de ocurrencias para todos los números, excepto un número, ¿cómo se puede encontrar ese número?
- En el siguiente problema, ¿cuántas combinaciones posibles de sombreros hay para que nadie use el mismo color de sombrero?
- ¿Cuál es la mejor manera de resolver una matriz de 5 × 5?
- Alguien me dijo que me especializara en un dominio CS para evitar quedar desempleado cuando envejeciera, ¿es cierto?
- ¿Qué piensan los informáticos teóricos de la hipótesis del universo matemático de Max Tegmark?
Los sub-idiomas como REs o SQL tendrán un nicho dentro de esos idiomas, permitiendo que ciertas operaciones se expresen fácilmente, con la propiedad conveniente de terminación garantizada. Pero no se pueden expresar grandes clases de problemas importantes, por lo que deben integrarse en idiomas más grandes.
Hay lenguajes de programación funcionales totales que intentan dividir la diferencia; Con la adición de primitivas para hacer el trabajo como la aritmética, puede llegar bastante lejos sin encontrar problemas. Sin embargo, ninguno de estos ha despegado particularmente.
