Основные понятия и определения дисциплины

Гипотеза Черча.

Гипотеза Черча: понятием рекурсивной функции исчерпывается полностью понятие вычислимой функции.
На основе этой гипотезы российские ученые Колмогоров и Успенский сделали обобщение: если существует некоторая рекурсивная функция, то для нее всегда можно построить алгоритм. И наоборот, любой существующий алгоритм может быть выражен в понятиях рекурсивной функции.
Невозможность создания рекурсивной функции для решаемой задачи означает невозможность реализации алгоритма ее решения.
Гипотеза Черча и ее обобщение не имеет доказательства, потому что она оперирует нематематическими понятиями алгоритма в интуитивном смысле.

14. 
    Машина Тьюринга.
    

В 1936 г. Тьюринг предложил модель абстрактной вычислительной машины, которая уточняла понятие алгоритма и оперировала с неограниченными ресурсами.
При желании можно создать реальную модель машины Тьюринга, но ресурсы такой машины становятся ограниченными.
Машина Тьюринга преобразует какие-либо объекты (например, строку символов, принадлежащих некоторому алфавиту) в некоторый искомый результат. При этом, хотя слова алгоритма машины Тьюринга могут иметь некоторый смысл, для теории алгоритмов это несущественно.
Для записи слов в машине Тьюринга используется бесконечная лента с последовательным доступом.

А – внешний алфавит машины Тьюринга.

Некоторый алфавит Р=р₁, р₂, …р_n, характеризующий состояние машины в конкретный момент времени, называют внутренним алфавитом.
Состояние движения ленты описывается множеством возможных состояний -, …, d_j, …, d₀, d₁, …, +.
Опишем принцип работы машины Тьюринга.
1) Чтение a_i из ячейки d₀, на которой позиционируется головка чтения/записи (R/W Head). Состояние машины в этот момент определяется p_j.
Начальный кортеж: {a_i, d₀, p₀}
2) В зависимости от значений a_i и p_j изменяется поведение машины:
{a_x, d_y, p_z}
Данный кортеж означает: записать вместо a_i символ a_х, переместить головку чтения/записи в позицию d_y, блоку управления перейти в состояние p_z.
3) Если после второго шага состояние машины Тьюринга описывается исходным кортежем, то машина останавливается. Иначе – повтор пункта 2.
Компактная запись работы машины Тьюринга задается функциональной таблицей, определяющей конкретный процесс преобразования исходных данных.