Лекции по математической логике и теории алгоритмов (стр. 9 из 10)
1) последовательностьюa i ( 1 ) , a i ( 2 ) ,..., a i ( s ) символов из внешнего алфавита А, записанных в ячейках ленты, где ai(1).- символ записанный в первой ячейке слева и т.д. (любая такая последовательность называется словом), 2) состоянием внутренней памяти qr;
3) номером k воспринимаемой ячейки.
Конфигурацию машины будем записывать так:
a ,a ,..., a a i(r) a ,a ,..., ai(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s)
здесь r-воспринимаемая ячейка, выделяется в виде дроби.
Если машина, находясь во внутреннем состоянии qi , воспринимает ячейку с символом au , записывает к следующему моменту времени в эту ячейку символ ar , переходит во внутреннее состояние qs и сдвигается по ленте, то говорят, что машина выполняет команду qiauÆqsarS , где символ S может принять одно из значений: -1 – сдвиг головки влево; +1 - сдвиг головки вправо; 0 – головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении
строки au и столбца qi будет стоять qsarS ( см. таб.6.2.1)
Таб.6.2.1.
| q0 | … | qi | … | qm |
| … | ||||
| au | qsarS | |||
| … | ||||
Если в программе машины для пары (q i ,a u ) пятерка отсутствует, то в таблице на пересечении строки a u , и столбца q i ставится прочерк.
Итак, машина Тьюринга есть, по определению, набор М=(А,Q,П), где А ― внешний алфавит, Q ― алфавит внутренних состояний, П ― программа.
Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.
Пример 6.2.1. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=|||||.).
Решение. Рассмотрим алфавит А = {|, +, ⁄}.
Машина определяется следующей программой:
Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+|||, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.
Пример 6.2.2. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.
Решение. Искомую машину построим в алфавите A={|, α, ⁄}. Программа такой машины может выглядеть так:
Применим полученную машину к слову||.
Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q1обеспечивает замену | на α, состояние q2 обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена α на |.
§6.3. Рекурсивные функции
Договоримся, что в этом параграфе
1. множество N натуральных чисел содержит 0 (нуль), т.е. N={0,1,2,3,...};
2. рассматриваемые функции f=f(x1,x2,…,xn) определены только тогда, когда переменные принимают значения из N, т.е. xiœN;
3. область значений функций DŒN;
4. рассматриваемые функции f=f(x1,x2,…,xn) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.
Введём в рассмотрениепростейшие функции
о(x)=0, s(x)=x+1, Imn (x1,..., xn ) = xm
Эти функции могут быть вычислены с помощью соответствующего механического устройства (например, на машине Тьюринга). Определим операторы, которые по одной или нескольким заданным функциям строят новые функции.
Оператор суперпозиции. Пусть даны функция f(x1,x2,…,xk) от k переменных и k функций f1(x1,x2,…,xn),…,fk(x1,x2,…,xn) от n переменных. Суперпозицией функций f,f1,…,fk называется функция j(x1,x2,…,xn)= f(f1(x1,x2,…,xn),…,fk(x1,x2,…,xn))
Мы говорим, что функция j получается применением оператора суперпозиции Sк+1 к функциям f,f1,…,fk, и пишем j=Sк+1(f,f1,…,fk) Например, S2(s,o)=s(o(x)), т.е. функция, тождественно равная 1, а S2(s,s)=s(s(x)) - это функция у(x)=x+2.
Оператор примитивной рекурсии. Пусть даны функции g(x1,x2,…,xn) и h(x1,x2,…,xn+2). Построим функцию f(x1,x2,…,xn+1) Пусть зафиксированы значения x1,x2,…,xn . Тогда полагаем: f(x1,x2,…,xn ,0)= g(x1,x2,…,xn)
f1(x1,x2,…,xn ,y+1)= h(x1,x2,…,xn ,y, f(x1,x2,…,xn,y))
Эти равенства определяют функцию f(x1,x2,…,xn+1) однозначно. Функция f называется функцией, полученной с помощью оператора R примитивной рекурсии. Используется запись f=R(g,h).
Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются 1) степень с натуральным показателем: a0=1, an+1=anÿa;
2) факториал: 0!=1, (n+1)!= n!ÿ(n+1) и т.д.
Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, I mn ( x 1 ,..., x n ) = x m применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.
Проверим, что функция u(x,y)=x+y является примитивно рекурсивной. Действительно, мы имеем: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Это есть схема примитивной рекурсии, так как x= I11(x), а u(x,y)+1=s(u(x,y))=S2(s,u). Здесь g(x)= I11(x), а h(x,y,u)=s(u)=S2(s, I33).
Аналогично доказывается, что функции m(x,y)=xÿy, d(x,y)=xy (считаем по определению 00=1), fact(x)=x! и многие другие являются примитивно рекурсивными.
Отметим; что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o, s, Imn являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции. Значит, такая функция, как
= x − y, если x ≥ y < y
f(x,y) не существует, если x
примитивно рекурсивной быть не может. Рассматривать функцию f(x,y)=x-y здесь мы не имеем права, так как значения функций должны быть натуральными числами (поэтому не отрицательными). Однако, можно рассмотреть функцию
x
÷ y = 0x − y еслиесли x x<≥y.y
Проверим, что она примитивно рекурсивна. Докажем вначале, что функция j(x)=xπ1 примитивно рекурсивна. Действительно, j(0)=0. j(y+1)=(y+1)π1=y, что служит схемой примитивной рекурсии для функции xπ1. Наконец, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) - схема примитивной рекурсии для xπy.
Существенно более широким классом функций, чем примитивно рекурсивные функции, является классрекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.
Оператор минимизации. Пусть дана функция f(x1,x2,… ,xn,xn+1). Зафиксируем какие-либо значения x1,x2,… ,xn первых n переменных и будем вычислять f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1), f(x1,x2,… ,xn,2) и т.д. Если y- наименьшее натуральное число, для которого f(x1,x2,…
,xn,y)=xn+1 (т.е. значения f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1),…,f(x1,x2,…
,xn,y-1) все существуют и не равны xn+1), то полагаем g(x1,x2,…
,xn,xn+1)=y. Таким образом, g(x1,x2,… ,xn,xn+1)=min(y|f(x1,x2,…,xn,y)=xn+1).
Если такого y нет, то считаем, что f(x1,x2,… ,xn,xn+1) не определено. Итак, возможны три случая:
1. f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1),…,f(x1,x2,… ,xn,y-1) существуют и не равны xn+1 , а f(x1,x2,…,xn,y)=xn+1;
2. f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1),…,f(x1,x2,… ,xn,y-1) существуют и не равны xn+1, а f(x1,x2,…,xn,y) не существует;
3. f(x1,x2,… ,xn,i) существуют при всех iœN и отличны от xn+1.
Если имеет место 1-й случай, то g(x1,x2,… ,xn,xn+1)=y, а если 2й или 3-й, то g(x1,x2,… ,xn,xn+1) не определено. Про функцию g полученную таким образом, говорят, что она получена из f применением оператора минимизации М. Мы пишем g= Мf.