Клас функцій, вычислимых по Тьюрингу

Словникові примітивно рекурсивні функції

Вихідні функції для алфавіту A:

Нуль-функція 0(x)= L;

Додавання символу z: P_z(x) = xz, де z Î A;

Функція, що проектує, Uij(x) = xi, де j - кількість букв у слові x, xi - i-я буква слова x.

Схема примітивної рекурсії для алфавіту A = { a, b).

Нехай g(x₁, …, x_n), h₁(x₁, …, x_n+2), h₂(x₁, …, x_n+2), – вихідні або примітивно рекурсивні функції. Тоді f(x₁, …, x_n+1) – нова примітивно рекурсивна функція, якщо

f(x₁, …, L) = g(x₁, …, x_n),

f(x₁, …, a) = h₁(x₁, …, x_n, a, f(x₁, …, x_n+1)),

f(x₁, …, b) = h₁(x₁, …, x_n, b, f(x₁, …, x_n+1))...

Позначимо операцію конкатенації con(x₁, x₂), x₁, x₂ Î A^*, A={a, b} і покажемо, що вона є примітивно рекурсивною.

con(x₁, L) = x₁ = U₁²(x) = x₁;

con(x₁, x₂, a) = x₁x₂a = P_a(con(x₁x₂));

con(x₁, x₂, b) = x₁x₂b = P_b(con(x₁x₂)).

У загальному випадку

con(x₁, x₂, x) = x₁x₂x = P_x(con(x₁x₂)).

Функція f (x ₁, x ₂, …, x_n) називається ефективно вычислимой, якщо для кожного набору аргументів а₁, а₂, …, а_n з її області визначення може бути обчислене значення функції f (а₁, а₂, …, а_n). Якщо функція ефективно вычислима, то говорять, що існує алгоритм її обчислення.

Теорема. Функція F (х₁, х₂,…х_n) рекурсивна (частково рекурсивна) тоді і тільки тоді, коли вона вычислима по Тьюрингу.

Доказ.

2. Усяка рекурсивна функція вычислима по Тьюрингу.

· Z(x) = L – нуль-функція вычислима на машині Тьюринга, що знищує будь-яке слово на стрічці.

· N (x) = x +1 – вычислима на машині Тьюринга, що до будь-якого слова W на стрічці дописує заданий символ a: W a.

· U_jⁿ (x) = x_{i –} функція проекції вычислима на машині Тьюринга, що у слові W виділяє символ x_i.

· j(x ₁, x ₂) = g (F ₁(x ₁, x ₂), F ₂(x ₁, x ₂)) – суперпозиція функцій, реалізується за допомогою композиції машин Тьюринга:

M_j = (x ₁* x ₂)°(MF ₁|| MF ₂)° зам * _|| ° Мg.

Машина спочатку копіює вихідне слово:

C o p y2(x 1* x ₂) Þ x ₁* x ₂ || x ₁* x ₂.

Потім воно переробляється рівнобіжною композицією машин М _{F 1}|| М _{F 2} у слово F ₁(x ₁* x ₂) || F ₂(x ₁* x ₂)), потім алгоритм зам * _|| заміняє допоміжний поділяючий символ || на *, і далі працює машина, що обчислює функцію g (F ₁(x ₁, x ₂), F ₂(x ₁, x ₂)): M _g(F ₁(x ₁* x ₂)* F ₂(x ₁* x ₂)). Результатом її роботи є функція j(x ₁, x ₂).

· Схема примітивної рекурсії також обчислюється за допомогою композиції машин Тьюринга. Наприклад, найпростіша схема примітивної рекурсії: j(0) = c, j(x +1) = F (j(x)) вычислима як композиція, що реалізує ітерацію. Для цього будуються машини:

M_D переробляє трійку чисел x # m #z у трійку x # m +1# F (z)$

M_C переробляє число x у трійку x #0# c;

Ф розпізнає властивість m<z у трійці чисел x # m #z.

Композиція M_C ° поки Ф повторити M_D задає алгоритм, що, виходячи зі слова x, виробляє трійку x #0# C, потім x #1#¦(c), потім x #2#¦(¦(c)), і т.д. доти, поки не буде отримана трійка x # x #j(x). Тоді виділяє алгоритм, застосований до цього слова, виділить крайній правий компонент слова, що є результатом обчислення функції j(x).

· Машина Тьюринга, що обчислює m - оператор, буде знаходити мінімальне слово в лексикографічному упорядочивании слів, що задовольняє даному предикатові.

Оскільки всі шість пунктів визначення рекурсивних функцій реалізовані у виді композиції машин Тьюринга, те всяка рекурсивна функція вычислима на машині Тьюринга.

Таким чином, було показано, що клас функцій, вычислимых на машині Тьюринга, є частково рекурсивним класом.

Крім цих алгоритмічних схем було знайдено і запропоноване багато інших, наприклад, машина фон Неймана, машина Посади, блок-схеми Посади, формальне вирахування рекурсивних функцій Эрбрана - Геделя й інші. Виявилося, що усі вони еквівалентні між собою, і, отже, усі вони обчислюють рекурсивні або частково рекурсивні функції. Ця обставина послужила причиною тому, що ряд учених (Черч, Тьюринг, Марков) практично одночасно висловили гіпотезу, що відома як теза Черча.

Дата добавления: 2014-01-07