Т. А. Сливина математическая логика и теория алгоритмов

Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.
Этот тезис нельзя доказать, т.к. он связывает нестрогое математическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции.
Но этот тезис может быть опровергнут, если построить пример функции интуитивно вычислимой, но не являющейся частично рекурсивной.

§ 5. Машины Тьюринга

Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма. Автоматизм, необходимый при реализации алгоритма естественно приводит к мысли о передаче функции человека, реализующего алгоритм, машине. Идею такой машины предложили в тридцатые годы американский математик Э. Пост и английский математик А. Тьюринг.
Рассмотрим один из вариантов указанной машины, которая носит название машины Тьюринга.
Устройство машины Тьюринга включает в себя:
1. Внешний алфавит, то есть конечное множество символов А = {a₀,a₁,a₂,...,a_n}. В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово.
2. Внутренний алфавит машины, состоящий из символов q₀, q₁, q₂, ..., q_m, п, л, н. Символы q₀, q₁, q₂, ..., q_m выражают конечное число состояний машины. Для любой машины число состояний фиксировано. Два состояния имеют особое назначение: q₁ – начальное состояние машины, q_Q – заключительное состояние (стоп-состояние). Символы п, л, н – это символы сдвига (вправо, влево, на месте).