Entonces, lo que cada máquina de Turing puede calcular se llama lenguajes recursivamente enumerables. Significa que podemos enumerar todas las cadenas en un idioma una por una. Suponga que necesita verificar si una cadena en particular es parte de un idioma, entonces inicia el enumerador y espera arbitrariamente mucho tiempo si ve la cadena, entonces es parte del idioma.
Ahora, es posible que desee responder en una cantidad arbitraria de tiempo que una cadena no es parte de un idioma, luego debe generar las cadenas en el idioma en un orden particular, para que pueda afirmar que una cadena determinada no es parte de un idioma. idioma después de ver una cadena que es mayor que esa cadena en la enumeración pero no la cadena original.
Desafortunadamente, no todos los idiomas que son recursivamente enumerables se pueden enumerar en un orden fijo conocido de antemano. Los idiomas que se pueden enumerar de esa manera son idiomas recursivos o decidibles.
- ¿Qué tan bien un título en matemáticas aplicadas prepararía a alguien para la ciencia de datos?
- ¿Cuál es el nivel más alto de matemáticas requerido para el desarrollo del juego?
- ¿Qué temas o campos en el aprendizaje automático o la minería de datos requieren matemáticas de alto nivel?
- Cómo diseñar un algoritmo eficiente cuando me enfrento a un problema
- ¿De qué se trata más la computación cuántica: Computadoras o Física y Matemáticas?
El problema de detención es recursivamente enumerable pero no recursivo. Entonces, si espera infinitamente, puede decir que un programa arbitrario no se detiene. Pero, ¿cuál es el fin del infinito? Si hay un final, no es infinito de todos modos.
