Основные выводы и результаты. · Вместо понятия правильности программы следует использовать понятие надежности программы.

· Вместо понятия правильности программы следует использовать понятие надежности программы.

· Тезис Тьюринга: каждая функция, для которой существует алгоритм нахождения ее значений, представима некоторой машиной Тьюринга, т. е. является вычислимой. Теорема Тьюринга: Проблема остановки машины Тьюринга неразрешима. Из приведенных утверждений следует, что существуют вычислимые и невычислимые функции.

· ССП позволяет исследовать только структурные свойства программ, интерпретация ССП определяет семантику вычислений.

· Протокол выполнения программы – ценное средство отладки программ. Программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном случае программа зацикливаетсяи результат ее выполнения не определен.

· Теорема Лакхэма – Парка – Паттерсона: Стандартные схемы S₁ и S₂ в базисе В функционально эквивалентны тогда и только тогда, когда они функционально эквивалентны на множестве всех свободных интерпретаций базиса В.

· Из логико-терминальной эквивалентности следует функциональная эквивалентность. Обратное утверждение не верно.

· Для одноленточного конечного автомата доказано, что проблемы пустоты и эквивалентности разрешимы. Для двухголовочнного конечного автомата проблемы пустоты и эквивалентности не являются частично разрешимыми.

· По заданному двоичному двухголовочному конечному автомату возможно построить ССП и наоборот, что позволяет решить задачу разрешимости (не разрешимости) свойств ССП.

· Теоремы Лакхэма - Парка – Паттерсона: Проблема пустоты, свободы, функциональной эквивалентности стандартных схем не является частично разрешимой. Проблема тотальности стандартных схем частично разрешима.

· Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов, но может и продолжаться бесконечно.

· Классы ССП транслируемы друг в друга. Теорема Ашкрофта – Манна: Класс стандартных схем транслируем в класс схем с логическими операциями.