<aside> 📌 Определение частичной функции.
Частичная функция $f: X \rarr Y$ - это функция $f$ из некоторого подмножества $S \subseteq X$ в $Y$ $($возможен случай, когда $S=X).$ Обозначение$: \ \not \rarr.$
</aside>
<aside> 📌 Определение машины Тьюринга (неформально).
Машина Тьюринга (МТ, TM) - это математическая модель вычислений, предложенная английским математиком Аланом Тьюрингом в 1936 году. Она представляет собой абстрактное вычислительное устройство, способное выполнять различные вычислительные задачи. Является расширением конечного автомата и формализацией понятия алгоритма. Машина Тьюринга состоит из: $1.\$ Бесконечной в обе стороны ленты, разделенной на ячейки, каждая из которых может содержать символ из некоторого конечного алфавита. $2. \$ Управляющего устройства(головка/каретка чтения/записи), которое может перемещаться по ленте влево/вправо и записывать/читать символы в текущей ячейке. Также может не перемещаться и оставаться на месте. Работа управляющего устройства зависит от таблицы переходов(программы), описанной далее. $3. \$ Существует $\epsilon$-символ, который заполняет все пустые клетки ленты. Его ещё часто обозначают как $\#$ и называют пустым символом. $4. \$ Состояния - МТ имеет конечное количество состояний (подробнее ниже). Некоторые состояния часто помечают как начальные - из которых программа начинает работать и конечные - на которых машина Тьюринга останавливается. Конечных состояний может быть несколько. $5. \$ Таблица переходов (программа) - правило, которое для каждого состояния и символа, который головка видит на ленте, определяет, какой символ записать, каким образом переместить головку и в какое состояние перейти.
</aside>
<aside> 📌 Определение машины Тьюринга (формально).
Машина Тьюринга представляет собой некоторую “комбинацию” семи элементов: $M = \{Q, G, \epsilon, \sum, \delta, q_o, F\},$ где: $M \ - \$ сама машина Тьюринга; $Q \ - \$ непустое, конечное множество состояний; $G \ - \$ непустой, конечный набор символов ленточного алфавита; $\epsilon \ - \$ пустой символ, которым по умолчанию заполнены ячейки ленты; $\sum = G \setminus \{\epsilon\} \ - \$ набор входных символов; $\delta:(Q \setminus F) \times G \not\rarr Q \times G \times \{L,R\} \ - \$ функция перехода; $q_0 \ - \$ начальное состояние; $F \sub Q \ - \$ набор конечных состояний.
</aside>
<aside> 📌 Определение детерминированной и недетерминированной машины Тьюринга.
Машина Тьюринга называется детерминированной, если каждой паре состояний и ленточного символа соответствует не более одного правила. В ином случае, машина называется недетерминированной.
</aside>
<aside> 📌 Определение вычислимой функции.
Вычислимые функции $-$ это множество функций вида, $f: N \rarr N,$ которые могут быть реализованы на машине Тьюринга.
В качестве множества $N$ часто рассматривается множество $B^* = \{0,1,00,01,10,11,...\}$ — множество слов в двоичном алфавите $B = \{0,1\},$ с оговоркой$,$ что результатом вычисления может быть не только слово из $B^$, но и специальное значение «неопределённость», соответствующее случаю, когда ал- горитм «зависает». Таким образом, можно дать следующее определение $N : B^ \cup \ \{undef\}.$
</aside>
<aside> 📌 Что значит, что машина Тьюринга $M$ вычисляет функцию $f?$ Это означает, что для любого слова нашего алфавита $x \in \sum,$ если это слово принадлежит области определения функции $f,$ то значит за несколько шагов машина остановится и выдаст результат, который является значением функции $f.$
</aside>
<aside> 📌 Тезис Черча-Тьюринга.
Класс алгоритмически вычислимых частичных функций совпадает с классом всех функций, вычислимых на машине Тьюринга.
</aside>