73. Примитивно рекурсивные предикаты. Свойства.

Предикат Р(х₁,…,х_n) называется примитивно рекурсивным если его характеристическая функция является примитивно рекурсивной.

Характеристическая функция X_p (х₁,…,х_n )=0 или 1, 0 если Р(х₁,…,х_n)-ложно; 1 если Р(х₁,…,х_n) – истина

Функция X рассматривается как функция натуральных элементов.

Свойства:

Опр.1 Если P,Q – примитивно рекурсивные предикаты, то ^---P, P&Q, PQ, PQ, P*Q , PQ также примитивно рекурсивные предикаты

Опр.2 Пусть P₁(х₁,…,х_n) , … , P_k(х₁,…,х_n) примитивно рекурсивные предикаты, причем P_i&Q _j =0, для всех ij, а P₁ P₂…. P_k 1 т.е при любом наборе переменной (х₁,…,х_n) только один из предикатов P_i i=1,k равен 1 и пусть функция g₁(х₁,…,х_n)…. g_k(х₁,…,х_n) примитивно рекурсивные предикаты P_i&Q _j =0 функция f(х₁,…,х_n) = g₁(х₁,…,х_n), P₁1

g_k(х₁,…,х_n), P_k 1,тогда функция также является примитивно рекурсивной

опр.3 Если функция f(х₁,…,х_n,y) примитивно рекурсивная функция, то ограниченная сумма:

g(x₁,...,x_n,a) = (х₁,…,х_n,y) и если f(х₁,…,х_n,0)=0 также является примитивно рекурсивной функция.

опр.4 Если функция f(х₁,…,х_n,y) примитивно рекурсивная функция, то ограниченное произведение g(x₁,...,x_n,a) = (х₁,…,х_n,y) при условии, что f(х₁,…,х_n,0)=1 также является примитивно рекурсивной функцией.

опр.5 Если P(х₁,…,х_n,y) примитивно рекурсивный предикат, то огранич кванторы Q₁(х₁,…,х_n,a) = y P(х₁,…,х_n,y) в случае если P(х₁,…,х_n,0)=1 а также Q₂(х₁,…,х_n,a) = y P(х₁,…,х_n,y).

Если P(х₁,…,х_n,0)=0 также, является примитивно рекурсивными предикатами.

74. Классы рекурсивных функций. (п.Р., о.Р., ч.Р.). Тезис Черча.

Функция f(х₁,…,х_n,z) называется результатом примитивно ограниченный оператор минимизации (-оператор) к предикату P(х₁,…,х_n,y), если функция f равна такому значению у = {0,1…z} при котором значение предиката Р(х₁,…,х_n,y) = 1 а для ty значение предиката Р(х₁,…,х_n,y)=0

В этом случае записывают: f(х₁,…,х_n,z)=yP(х₁,…,х_n,y)

Теорема: Если Р(х₁,…,х_n,y) примитивно рекурсивный предикат, то функция yP(х₁,…,х_n,y) является примитивно рекурсивной

Результатом применения неограниченного оператора минимизации к предикату Р называется функция f=1 равную значению y=N{0}. А для ty равно P=0. Если такое значение у не существует, то функция f является неопределенной.

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

Тезис Черча : всякая эффективно вычислимая функция является частично рекурсивной

75. Машины Тьюринга. Принципы работы. Протокол работы.

Машиной Тьюринга Т называется тройка множеств T=<A, Q, P>, где: A=A(T)={a₀, a₁,…, a_m} – внешний алфавит машины Т (обычно a₀=0, a₁=1), Q=Q(T)={q₀, q₁,…,q_m} – алфавит внутренних состояний или внутренний алфавит машины Т.

Р = РТ = {T(i,j) | i=1,…,n; j=0,1,…,m} – программа машины Т; где Т(i,j) – команды этой программы, причем, для каждой пары (i,j) существует одна единственная команда Т(i,j), которая имеет один из видов: q_ia_j q_ka_l q_ia_j q_kR

q_ia_j q_kL

Принцип работы. МТ представляет собой бесконечную в обе стороны ленту разбитую на ячейки причем имеется конечное число упорядоченных ненулевых символов.

В начальный момент времени в ячейке вписаны символы из алфавита А, в остальные ячейки вписаны пустые символы, которые обычно обозначаются 0.

МТ имеет считывающе-пишущую головку, которая в любой момент времени обозревает заданную ячейку и воспринимает в этой ячейке символ.

В момент времени к головка находится в левой части.

Если МТ находится в состоянии символов q_i а в обозрев ячейке находится а_j , то выполняется команда q_ka_jS.

Для МТ начальным символом, является состояние q₁ q₀ считается конечным символом или заключительным состоянием машины Тьюринга.

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

Конфигурацией МТ будем называть слово К вида Uq_iV , гдеU-слово на ленте левее голов, а V- слово на ленте правее.

Если при выполнении команды получается что из конфигурация k_i получаем кофигурацию k_j то записывают: T: K_i K_j

Если Т: К₁К₂К₃…К_n то Т: К₁=> К_n

Если К₁и К_n – начальные и конечные конфигурации, то записывают так: Т: К₁|- К_n

Детерминированная последовательность К₁ К₂К₃…К_n….. называют протоколом работы МТ

Говорят что МТ Т применяется к слову А, если Т начиная работу над словом А останавливается через конечное число шагов. Если в результате работы получается слово В, то записывают Т(А)=В.

Если МТ не останавливается, то говорят, что Т не применимо к слову А.