Ключевые моменты и важность решимости

Question

Язык разрешаем, если ТМ распознает язык и переходит в состояние Принять или Отклонить.Как разработчикЯ думаю, что это важно, так как это означает, что мы можем определить, содержит ли программа переполнение буфера или взаимоблокировки.Кроме того, следующие проблемы являются неразрешимыми:

• Имеет ли программа когда-либо доступ к неинициализированной переменной.
• Две ли контекстно-свободные грамматики описывают один и тот же язык?
• Имеет ли значение, если параметры подпрограммы передаются по ссылке или по результату копирования

С точки зрения решимости, что бы вы назвали ключевыми моментами решимости и почемуважна решаемость (особенно для разработчика).

Примечание: пункты с пулей хороши в ответах - я могу посмотреть темы самостоятельно.Я просто хочу знать, каковы основные моменты.

Answer 1

Возможно, это относится к обмену историей , но я все равно попробую.

Ключевым моментом является то, что некоторые проблемы неразрешимы, то есть не решаемы алгоритмом, поэтому их следует решать другими методами. Среди этих проблем много «мета-проблем», касающихся компьютерных языков, например, проблема обнаружения вируса .

Определив, что проблема неразрешима, существует несколько возможных направлений действий:

1. Некоторые проблемы могут быть полуразрешимыми, т. Е. Существует полу -алгоритм, который решает некоторые случаи, но в других случаях зацикливается навсегда. При реализации полуалгоритма установите таймер и верните no answer, когда время истечет.
2. Решите только несколько, надеюсь, критически важных частей проблемы, упростив ее.
3. 2 + запрашивать ввод у пользователя, когда проблема становится слишком сложной.
4. Используйте эвристику, которая получает правильный ответ в большинстве случаев.
5. Используйте другой язык, возможно, не полный по Тьюрингу.

от 1 до 3 популярны для автоматизированных инструментов рассуждений, включая верификаторы программ. 4 - это то, что делают антивирусные сканеры. 5 - хороший выбор , когда пользователи могут писать сценарии для автоматизации большей системы; вместо того, чтобы давать им полный JavaScript / Scheme / Lua / что угодно, дайте им ограниченное подмножество, которое не допускает неограниченную рекурсию / циклы.

Answer 2

Предположим, вам нужно написать какое-то программное обеспечение, которое удовлетворяет условию: "во время выполнения ни одна функция не должна в конечном итоге вызывать себя прямо или косвенно".

Это условие будет неразрешимым, но может быть более ограничительное условиеdecidable, например что-то вроде: «указатели на функции не должны использоваться, и никакая функция не должна содержать вызовов к себе прямо или косвенно».

Это подчеркивает, что иногда можно обменять гибкость на разрешимость, так чтонекоторые обязательные свойства системы могут стать обязательными для исполнения.

Если язык программирования является разрешимым, то всегда можно будет решить, является ли программа действительной программой для этого языка.

Но даже если программа является допустимой программой для этого языка, остается нерешенным, может ли эта программа вызвать переполнение буфера или тупик.