Los puntos clave y la importancia de Decidibilidad

Question

Una lengua es decidible Si un TM reconoce el idioma y entra en un estado de aceptar o rechazar. Como prog. Creo que esto es importante ya que significaría que podríamos determinar si un programa contiene búfer desbordamientos o callejones sin salida. Además, los siguientes problemas son Un-decidible:

• ¿Tiene un programa cada vez acceder a una variable no inicializada.
• Haz dos de contexto gramáticas libres describen el mismo langauge.
• ¿Hay alguna diferencia si los parámetros a una subrutina se pasan por referencia o por copia resultado

En términos de Decidibilidad ¿Cuál diría que son los puntos clave para Decidibilidad y por qué es importante Decidibilidad (particularmente a un desarrollador).

Nota: Las viñetas están muy bien en las respuestas - Puedo mirar hacia arriba los temas a mí mismo. Sólo quiero saber cuáles son los puntos principales.

Answer 1

Tal vez esto pertenece a la intercambio cstheory, pero voy a tener un ir en él de todos modos.

El punto clave es: algunos problemas son undecidable, es decir, no resoluble por un algoritmo, por lo que deben ser abordados por otros métodos. Entre estos problemas son muchos "meta-problemas" en relación con los lenguajes de programación, por ejemplo, el problema de la detección de un virus .

Después de haber decidido que un problema es indecidible, hay varios cursos de acción posibles:

1. Algunos problemas pueden ser semi-decidible, es decir, hay un -algorithm que soluciona algunos casos, pero los bucles para siempre en los demás casos. Cuando se implementa un semi-algoritmo, poner un contador de tiempo sobre él y no answer retorno cuando se acabe el tiempo.
2. Resolver sólo unas pocas partes, es de esperar cruciales del problema mediante la simplificación de la misma.
3. 2 + pedir al usuario para la entrada cuando el problema se vuelve demasiado complejo.
4. Usar una heurística que obtiene la respuesta correcta más del tiempo.
5. Usar un lenguaje diferente, tal vez una completa no-Turing.

1 a 3 son populares para disfrutar de herramientas razonamiento automatizado, incluyendo los verificadores del programa. 4 es lo que hacen los programas antivirus. 5 es un buena opción al permitir a los usuarios a escribir guiones para automatizar un sistema más grande ; en lugar de darles plena JavaScript / Esquema / Lua / lo que sea, les dan un subconjunto restringido que no permite recursividad / bucles no limitados.

Answer 2

Supongamos que usted tiene que escribir algún software que satisface la condición:. "En tiempo de ejecución sin función serán siempre terminan llamando a sí directa o indirectamente"

Esta condición sería indecidible, sino una condición más restrictiva puede ser decidible, por ejemplo, algo como:. "No hay punteros a funciones se utilizarán y ninguna función harán llamadas a sí directa o indirectamente"

Este es poner de relieve que a veces es posible flexibilidad comercial para decidibilidad, de modo que ciertas propiedades requeridas del sistema pueden llegar a ser ejecutable.

Si un lenguaje de programación es decidible, entonces siempre será posible decidir si un programa es un programa válido para ese idioma o no.

Pero incluso si un programa es un programa válido para ese idioma, sigue siendo indecidible si ese programa puede incurrir en un desbordamiento de memoria o un callejón sin salida.