Основные выводы и результаты
· Вместо понятия правильности программы следует использовать понятие надежности программы.
· Тезис Тьюринга: каждая функция, для которой существует алгоритм нахождения ее значений, представима некоторой машиной Тьюринга, т. е. является вычислимой. Теорема Тьюринга: Проблема остановки машины Тьюринга неразрешима. Из приведенных утверждений следует, что существуют вычислимые и невычислимые функции.
· ССП позволяет исследовать только структурные свойства программ, интерпретация ССП определяет семантику вычислений.
· Протокол выполнения программы – ценное средство отладки программ. Программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном случае программа зацикливаетсяи результат ее выполнения не определен.
· Теорема Лакхэма – Парка – Паттерсона: Стандартные схемы S1 и S2 в базисе В функционально эквивалентны тогда и только тогда, когда они функционально эквивалентны на множестве всех свободных интерпретаций базиса В.
· Из логико-терминальной эквивалентности следует функциональная эквивалентность. Обратное утверждение не верно.
· Для одноленточного конечного автомата доказано, что проблемы пустоты и эквивалентности разрешимы. Для двухголовочнного конечного автомата проблемы пустоты и эквивалентности не являются частично разрешимыми.
· По заданному двоичному двухголовочному конечному автомату возможно построить ССП и наоборот, что позволяет решить задачу разрешимости (не разрешимости) свойств ССП.
|
|
|
· Теоремы Лакхэма - Парка – Паттерсона: Проблема пустоты, свободы, функциональной эквивалентности стандартных схем не является частично разрешимой. Проблема тотальности стандартных схем частично разрешима.
· Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов, но может и продолжаться бесконечно.
· Классы ССП транслируемы друг в друга. Теорема Ашкрофта – Манна: Класс стандартных схем транслируем в класс схем с логическими операциями.
Дата добавления: 2015-12-20; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!