Тезис черча

а) если значение функции определено, то в конце концов остановится, обозревая самый левый символ строки , при этом часть, находящаяся справа от этой строки, пустая;

б) если значение не определено, то никогда не останавливается.

ЗАМЕАНИЕ 1: Существует бесконечное число машин Тьюринга, для каждой из которых соответствует своя вычислимая функция.

ЗАМЕАНИЕ 2: Для любой вычислимой функции имеется бесконечное число машин Тьюринга.

ПРИМЕР: построим машину Тьюринга для «». Зададим функцию :

; ; ; ;

; ; ; .

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

(35) ДРУГИЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ ПОНЯТИЯ АЛГОРИТМА. ТЕЗИС ЧЕРЧА

а) Гедель-Эбран-Клини: общерекурсивные функции, определенные с помощью исчисления «рекурсивных уравнений». Книга: Мендельсон. Введение в матем. Логику.- М.: Наука, 1976.-320 с.

б) Пост: Функции, определенные каноническими дедуктивными системами. Книга: Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.-М.: Мир, 1983.-256 с.

в) Марков: Функции, задаваемыми «нормальными алгоритмами» над конечным алфавитом. Книга: Мендельсон. Введение в матем. Логику.- М.: Наука, 1976.-320 с.

г) Шепердсон-Стерджис: МНР-вычислимые функции (Катленд……..)

ТЕЗИС ЧЕРЧА: Интуитивно и неформально определенный класс эффективно вычислимых функций совпадает с классом определимых функций.

Вера в тезис подкрепляется аргументами:

1)  многие независимые варианты уточнения интуитивного понятия вычислимости привели к одному и тому же классу;

2)  обширное семейство эффективно вычислимых функций принадлежат этому классу;

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

(36)АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ (АНП)

Определение 1: Предикат называется «разрешимым», если его характеристическая функция, задаваемая формулой : , если – истинно; , если – ложно, вычислима.

Определение 2: Предикат называется «неразрешимым», если он не является разрешимым.

Алгоритмически Неразрешимые Проблемы:

1.  Теорема Черча «о неразрешимости логики предикатов»: Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

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

3.  Не существует алгоритма установить, что две программы вычисляют одну и ту же одноместную функцию, т. е. универсальное тестирование не возможно.

4.  Диофантово полиномиальное уравнение имеет или не имеет целочисленного решения? Не существует общего алгоритма, который может установить конкретный ответ (Матиясевич доказал эту теорему).

(37) Определение: Однородный класс вычислительных задач будем называть «проблемой (массовой задачей)» и обозначать через Т, а алгоритм, ее решающий, через А. Частный случай Т обозначим через . А выполняет последовательность вычислений . Длина характеризует время вычислений. Глубина — число уровней параллельных шагов – время параллельных вычислений.

1) сложность вычислений «в наихудшем случае», где мера вычисления может быть выбрана как: а) число элементов или б) глубина или в) число модулей (уровень технологии); – размер.

2) сложность «поведения в среднем», где — вероятность появления I среди возможных частных случаев .