ТМВ-2020-Лекция-24.03.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Машина Тьюринга. Частично рекурсивные функции.

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

Пусть существует лента, состоящая из ячеек, бесконечная в обе стороны. На некоторых ячейках написано слово, на остальных - пустой символ \(\Lambda\). По ленте перемещается каретка (головка записи-чтения), которая может находиться в одном из состояний. Она способна считывать, записывать информацию, а также перемещаться влево и вправо.

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

Зададим модель машины Тьюринга:

\(A\) - алфавит

\(\lambda\) - пустой символ, \(\lambda \in A\)

\(S\) - множество состояний

\(S_0\) - начальное состояние

\(T\) - множество конечных (терминальных) состояний

\(P\) - функция переходов

\(P:S * A \rightarrow S * A * {L,R,H}\)

\(L,R,H\) - передвижение головки влево, вправо, отсутствие передвижения (Hold - стой на месте)

Машина Тьюринга: \(M = <A, \Lambda, S, S_0, T, P >\)

Задача про удвоение слова (унарная система счисления)

Пусть слово записано в унарной системе счисления (на ленте хранятся \(\lambda\) и единицы). Головка находится на самом левом символе входной строки. Аналогично с выходной строкой. Необходимо удвоить слово (в примере(см. ниже) изначально было число 4, необходимо получить 8)

Задача про удвоение слова.png
Пример

В алгоритме необходимо понимать, какие единицы мы приписали справа, а какие нам осталось приписать. Для машин Тьюринга функцию переходов пишут так:

\(S_0,1 \rightarrow S_1,A,R\)(есть состояние \(S_0\), в этом состоянии мы видим 1, переходим в новое состояние, записываем новый символ и двигаем головку вправо)

\(S_1,1 \rightarrow S_1,A,R\)

\(S_1,\Lambda \rightarrow S_2,B,L\) (переходим в состояние \(S_2\), так как нужно будет идти налево)

\(S_2,1 \rightarrow S_2,1,L\)

\(S_2,A \rightarrow S_0,A,R\)

\(S_1,\Lambda \rightarrow S_t,\Lambda,H\) (corner case, пустая строка)

\(S_0, A \rightarrow \) (так не бывает!!!)

\(S_0, B \rightarrow S_3,B,H\)

\(S_3, B \rightarrow S_3,B,R\)

\(S_3, \Lambda \rightarrow S_4,\Lambda,L\)

\(S_4, B \rightarrow S_4,1,L\)

\(S_4, A \rightarrow S_4,1,L\)

\(S_4, \Lambda \rightarrow S_t,\Lambda,R\)

\(S_1,B \rightarrow S_1,B,R\) (corner case)

\(S_1,A \rightarrow \)(так не бывает!!!)

\(S_2,B \rightarrow S_2,B,L\) (corner case)

\(S_2,\Lambda \rightarrow \) (так не бывает!!!)

Алгоритм прибавления единицы

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

Пример. Алгоритм прибавления единицы.png

\(S_0,\Lambda \rightarrow S_t,1,H\)

\(S_0,1 \rightarrow S_1,1,H\)

\(S_0,0 \rightarrow S_1,0,H\)

\(S_1,0 \rightarrow S_1,0,R\)

\(S_1,1 \rightarrow S_1,1,R\)

\(S_1,\Lambda \rightarrow S_2,\Lambda,L\)

\(S_2,1 \rightarrow S_2,0,L\)

\(S_2,0 \rightarrow S_3,1,H\)

\(S_2,\Lambda \rightarrow S_3,1,H\)

\(S_3,0 \rightarrow S_3,0,L\)

\(S_3,1 \rightarrow S_3,1,L\)

\(S_3,\Lambda \rightarrow S_t,\Lambda, R\)

Домашнее задание:

1) Перевернуть бинарное слово (пример: 10011 -> 11001)

2) Сложение в унарной системе

Частично-рекурсивные функции

Частично-рекурсивные функции - формализация, которая возникла до машины Тьюринга. Её автор - Черч. Современные вычислительные системы основаны на тезисе Тьюринга-Черча, который гласит, что любая функция, вычислимая в интуитивном смысле, вычислима машиной Тьюринга или в виде частично-рекурсивной функции. Частично-рекурсивные функции строятся, как исчисления.

\(f:N_{0}^k \rightarrow N_0\)

Базисные функции:

1) \(O(x) = 0\)

2) \(s(x) = x + 1\)

3) \(P_{K}^i(x_1, ..., x_k) = x_i\)(функция проекции)

Операторы (операции над функциями):

1) Композиция

\(F(x_1, ..., x_n) = f(g_1(x_1, ..., x_n), ..., g_k(x1, ..., x_n))\)

2) Примитивная рекурсия

\(F(x_1, ..., x_n, 0) = f(x_1, ..., x_n)\)

\(F(x_1, ..., x_n, y+1) = g(x_1, ..., x_n, y, F(x_1, ..., x_n, y))\)

3) Оператор минимизации

\(F(x_1, ..., x_n) = min_{y \in N_0}f(x_1,...,x_n,y) = 0\) (не для любой функции определён)

Функции, составленные из базисных только лишь операциями композициями и примитивными рекурсиями - примитивно - рекурсивные функции.

Пример 1 (сложение 2 чисел)

Опишем функцию сложения 2 чисел.

\(Sum(x,y)\)

\(F(x,y) = x+y\)

\(F(x,0) = x = P_{1}^1\)

\(F(x,y+1) = F(x,y) + 1 = s(F(x,y)) = s(x,y,F(x,y)) = s(P_{3}^3(x,y,F(x,y)))\)

\(F(x,y+1) = s(P_{3}^3(x,y,F(x,y)))\)

Пример 2 (умножение 2 чисел)

\(F(x,y) = xy = Prod(x,y)\)

\(F(x,0) = o(x)\)

\(F(x,y+1) = sum(x,F(x,y)) = s(x,y, F(x,y)) = sum(P_{3}^1(x,y,F(x,y)), P_{3}^3(x,y,F(x,y)))\)

\(F(x,o) = o(x)\)

\(F(x,y+1) = sum(P_{3}^1(x,y,F(x,y)), P_{3}^3(x,y,F(x,y)))\)

Домашнее задание

\(F(x,y) = x^y\) (подсказка: используй функцию prod)

\(F(x) = x!\)

\(F(x) = x^x\)