Aquí hay una máquina explícita, con 4 estados {A, B, Aceptar, Rechazar}. La máquina se detiene en los estados Aceptar y Rechazar, por lo que solo necesitamos reglas de transición para los otros dos. En el estado A todavía no hemos visto ninguna “b”. En el estado B, hemos visto cero o más “a” seguidos de al menos una “b”. Comenzamos en el estado A.
- A, final -> Aceptar
- A, a -> A
- A, b -> B
- B, final -> Aceptar
- B, a -> Rechazar
- B, b -> B
Esto aceptará cualquier cadena finita de cero o más “a” s seguida de cero o más “b” s. Si hubiera un número infinito de “a” s, o un número finito de “a” s seguido de un número infinito de “b” s, la máquina no se detendría, pero se detendría en cualquier cadena infinita que tuviera un ” a ”después de una“ b ”, por lo que la función Rechazar funciona perfectamente incluso en cadenas infinitas. La función Aceptar debe continuar porque “todavía no está segura”.
Este tipo de media capacidad de decisión para casos infinitos es bastante común. Por ejemplo, en el Problema de detención, puede (eventualmente) identificar todos los programas que se detienen, pero no puede identificar todos los programas que no se detienen.
- ¿Qué son las matemáticas discretas?
- ¿Hay algún problema que requiera más tiempo exponencial de resolución (por ejemplo, doble exp.) Pero que pueda verificarse en tiempo polinómico determinista?
- ¿Cuál es la mejor manera de encontrar números amistosos hasta N?
- ¿Cuál es la función de un reóstato?
- ¿Cuáles son las mejores maneras de mejorar la habilidad de programación a través de las matemáticas?
