Мат. логика

При вычислении частичной функции f(P) на машине Тьюринга будем считать, что если значение f(P) определено, то машина переводит за конечное число шагов конфигурацию q1P в конфигурацию q0f(P). В противном случае машина работает бесконечно.

Пример. Пусть требуется перевести унарную запись числа n ≥ 1 (изображается в виде n палочек) в двоичную запись. Другими словами, нужно построить машину Тьюринга М, которая конфигурацию q1 ||…| при любом n (число палочек) ≥ 1 преобразовывала бы в конфигурацию q0σ1σ2…σp, где σ1σ2…σp – двоичная запись числа n, начинающаяся с 1.

Вкачестве внешнего алфавита машины М возьмем {λ, |, 0,1}. Работа машины осуществляется циклами. К началу цикла r (1 ≤ r ≤ n-1) машина находится в конфигурации

q2 10…11 (двоичная запись r) 11…1 (n - r)

Втечение цикла r стирается одна палочка и к числу r в двоичной записи прибавляется 1. Цикл r осуществляется в несколько этапов:

1)головка проходит направо до конца записи, используя команды:

q21 → q21П q20 → q20П q21 → q21П

2)определяет правый конец записи и оказывается у последней палочки в состоянии q3: q2λ → q3λЛ

3)стирает последнюю палочку и запоминает состоянием q4 необходимость прибавления единицы

q3 | → q4λЛ

4)проходит сквозь палочки налево вплоть до цифр 0 и 1 q4 | → q4 | Л

5)прибавляет 1, для чего в соответствии с алгоритмом двоичного сложения:

а) перемещаясь в состоянии q4 справа налево, головка заменяет все символы 1, расположенные в конце двоичной записи (до первого 0), символом 0:

q41 → q40Л

б) первый из встреченных нулей (если они есть) заменяется на 1, и головка изменяет состояние

на q5:

q40 → q51Л

в) в состоянии q5 головка проходит налево сквозь все цифры q50 → q50Л

q41 → q51Л

г) встретив пустой символ, головка перемещается в состоянии q2 к первой цифре q5λ → q2λП

д) если двоичная запись сплошь состоит из единиц, то после осуществления пункта а) головка встречает пустой символ, заменяет его на 1 и останавливается в состоянии q2:

q4λ → q21H

Цикл завершен.

Осталось назначить команды для входа в цикл и выхода из цикла. Переход к циклу осуществляется по единственной команде:

q11 → q21H

Выход из цикла строится так.

Если после выполнения команды (1) головка в состоянии q3 считывает не палочку, а цифру (все палочки стерты), то она проходит налево сквозь цифры

q30 → q30Л q31 → q31Л

и останавливается у первого непустого символа q3λ → q0λП.

Условимся при вычислении на машине числовых функций запись числа n (n = 0,1,2,…) представлять в виде n+1 палочек (чтобы запись нуля была непустой).

Будем говорить, что машина Тьюринга вычисляет функцию f(x1,…,хn), если конфигурацию

q1 || … | * … * || … |

х1+1 хn+1

она переводит в заключительную конфигурацию

q0 || … | f(x1,…,хn)+1

в случае, когда f(x1,…,хn) определена, и работает бесконечно в противном случае.

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

Некоторые приемы программирования на машинах Тьюринга

1. Суперпозиция программ Пусть имеются машины Тьюринга М1 и М2, которые соответственно вычисляют словарные

функции f1(P) и f2(P) в одном и том же алфавите.

Требуется построить машину М, вычисляющую суперпозицию f2(f1(P)).

Значение суперпозиции f2(f1(P)) считается определенным, когда определены f1(P) и f2 на слове

(f1(P).

Программа машины М может быть получена следующим образом:

1.Состояния машины М2 переобозначаются так, чтобы все они, за исключением начального, были отличны от состояний машины М1, а начальное совпадало с заключительным состоянием машины М1.

2.Программы приписываются друг к другу и начальным состоянием машины М объявляется

начальное состояние М1, а заключительным – заключительное состояние машины М2. Машину М будем называть суперпозицией машин М1 и М2 и обозначать М2 М1.

Вх. сиг.				Состояния
	q1	q2	q3		q4	q5	q0
λ	-	q3	q0		q2	q2	-
	-						-
		λ, Л	λ, П		1, Н	λ, П
|	q2	q2	q4		q4	-	-
	1, Н	| , П	λ, Л		1, Л	-	-
0	-	q2	q5		q5	q5	-
	-						-
		0, П	0, Л		1, Л	0, Л
1	-	q2	q3		q4	q5	-
	-						-
		1, П	1, Л		0, Л	1, Л

Пример. Пусть на ленте записаны два натуральных числа в унитарном коде. Числа разделены символом «+». Требуется разработать машину Тьюринга для сложения этих чисел.

q1 | → q2λН – стирание палочки

q2 | → q2 | П – проход вправо через палочки

q2+ → q3 | Н – замена + на |

q3 | → q3 | Л – проход влево через палочки

q3Л → q0 λ П – обнаружение пустой ячейки, остановка.

Вх. сиг.			Состояния
	q1	q2		q3	q0
|	q2	q2		q3	q0
	λ, Н	|, П		|, Л	|, Н
+	-	q3		-	-
	-	|, Н		-	-
λ	-	-		q0	-
	-	-		λ, П	-

Тезис Тьюринга

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

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

Это дало повод Тьюрингу высказать следующую гипотезу (её стали называть основной гипотезой теории алгоритмов или тезисом Тьюринга):

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

39. Частично-рекурсивные функции. Тезис Чёрча.

Основные операции.

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

1.Операция суперпозиции

Пусть заданы n-местная частичная функция g и частичные функции f1,f2,…,fn, зависящие от одних и тех же аргументов х1,…,хn

Суперпозицией функции g и f1,…,fn назовем частичную функцию

h(х1,…,хm) = g(f1(х1,…,хm),…,fn(х1,…,хm))

При этом значение функции определено, если определены значения z1=f1(х1,…,хm),…,zn(z1,…,zn). В противном случае величина h(х1,…,хm) считается неопределенной.

Пример. f1(x,y) = x – y, f2(x,z) = x2 + z, g(x,y) =

Тогда h(x,y,z) =

Будем рассматривать функции от натурального аргумента, принимающие натуральные значения. Поэтому значения функций определены лишь в случае, когда они целые и неотрицательные.

x	y	z	f1 = x – y	f2 = x2 + z	H =
1	2	5	-	6	-
4	1	0	3	16	-
2	2	1	0	5	0

2. Операция рекурсии (примитивная рекурсия) Пусть функция f(x) задана условиями:

Эти уравнения позволяют последовательно находить значения: f(0) = a, f(1) = h(0,f(0)), f(2) = h(1,f(1))…

Пример.

Для неё f(0) = 1, f(1) = 1*f(0) = 1, f(2) = 2*f(1) = 2, f(3) = 3*f(2) = 6 и т.д. Легко видеть, что f(x) = x!

Функция от двух аргументов может быть задана следующими условиями:

Здесь первый аргумент является параметром, а рекурсия ведется по второму аргументу. Пример. Определим функцию f(x,y) = xy:

Рассмотрим общий случай.

Пусть при n ≥ 0 имеются n-местная частичная функция g(x1,…,xn) и n+2 – местная частичная функция n(x1,…,xn, y.z).

Будем говорить, что функция f(x1,…,xn,y) возникает из g и h применением операции рекурсии, если для всех натуральных значений x1,…,xn,y имеет место

Величина f(x1,…,xn, y+1) определена, если определены f(x1,…,xn, y) и h(x1,…,xn, y,z) при

z = f(x1,…,xn, y)

Если значение f(x1,…,xn, y0) не определено, то неопределенными будет значения

f(x1,…,xn, y) при всех y ≥ y0.

Применение операции рекурсии к всюду определенным функциям g и h дает всюду определенную функцию f.

3.Операция минимизации

Пусть имеется n-местная частичная функция g(x1,…,xn, y)

Зафиксируем некоторый набор (x1,…,xn) и рассмотрим уравнение относительно y:

g(x1,…,xn-1, y) = xn

Будем решать это уравнение, последовательно вычисляя g(x1,…,xn-1, 1),…

Наименьшее y, для которого окажется, что g(x1,…,xn-1, y) = xn обозначим через My(g(x1,…,xn, y) = xn). Считается, что это значение неопределенно:

1)Если в процессе последовательного вычисления встретилось некоторое y0, при котором g(x1,…,xn-1, y0) не определено (в частности, это может случиться уже при y0 = 0), а при всех меньших у уравнение не выполнялось

2)Если g(x1,…,xn-1, y) определено при всех у, но отлично от xn

Значение My(g(x1,…,xn-1, y) = xn) является функцией переменных x1,…,xn. Будем говорить, что функция f(x1,…,xn) = My(g(x1,…,xn-1, y) = xn) получена из g операцией минимизации.

Типичной ситуацией применения операции минимизации является построение обратных функций. Используя, например, функции x+y, xy, x2 можно получить обратные им функции:

x – y = Mz (y + z = x) = Mz (y*z = x)

= My(y2 = x)

Функции x-y, , являются частичными. Следовательно, операция минимизации даже в применении к всюду определенным функциям может давать частичные функции.

Определение частично – рекурсивных функций.

С помощью описанных операций будем из исходных функций строить более сложные функции.

Вкачестве исходных возьмем 3 функции:

1)Для нуля 0(х).

2)Функция следования S(x) = x+1, которая указывает по x следующее за ним число.

3)Функция выбора аргумента.

Функция выбора по набору длины n выдает число, стоящее на m-м месте.

Функция f (х1, х2, …, хn) называется частично – рекурсивной, если она может быть получена из исходных функций 0(х), S(x), применением конечного числа операций суперпозиции, рекурсии и минимизации.

Примеры рекурсивных функций.

Всюду определенные частично-рекурсивные функции называются рекурсивными или общерекурсивными.

1)Константы.

Все константы являются рекурсивными функциями. 0 = 0(х), 1 = S(0(х)), 2 = S(S(0(x)))

2)Сложение.

х+ у

Сложение является рекурсивной функцией и задается следующей схемой:

3)Умножение.

Является рекурсивной функцией, задается:

4)Показательно-степенная функция ху.

=

5) Функции sg и .

Обе функции рекурсивны, так как их можно задать следующими системами:

6)Усеченная разность.

х y – рекурсивная функция

x	y =
x	1 - рекурсивна
0	1=0
(x + y)		1= x
х	0= x
х	(у +1)=(х		у)	1
Доказательство:
Действительно,
А) если			, тогда
х	(у +1)= х		у		1
(х	у)	1= х		у	1
Б) если			, то
х	(у +1)=0
(x	y)		1= 0

7)Модуль разности. |x - y|

|x - y| = (xy) +(yx)

8)Целая часть от деления

a)y0 - целая часть от

b)y = 0 = x (по определению)

= Mz((xz)((x+1) y(Z+1)) = 0) (1)

При у0 равна наименьшему z, при котором .

Это означает, что и следовательно, (х + 1) у(z+1) =0.

При у0 = Mz((x+1) y(Z+1) = 0)

Чтобы учесть значение у = 0 и учесть = x вводится дополнительный сомножитель вида xz

9)Остаток от деления - ост(х, у)

1.Если у0, то ост(х, у) определим обычным образом.

2.Если у = 0, то определим ост(х, у) = х

ост(х, у) = х у

10) Функция делимости – дел (х, у).

дел(х, у) = (ост(х, у)) 11) Двоичная степень х.

СТ2(х)

-S

-2S

-2S + 1

x= 2t(2S +1)

Пусть СТ2(х) равна максимальному показателю, с которым входит 2.

СТ2(х) = t

СТ2(х) = My(дел(х, 2у+1)=0)

12)Функция, отличная от 0 в конечном числе точек. Эта функция является рекурсивной. Если f(x)0 в точках х1, х2, …, хк и принимает в этих точках значение у1, у2, …, ук, то она может быть представлена в виде

F(x) = y1(|x - x1|) + … + yk(|x – xk|)

13)Нумерация наборов.

Втеории алгоритмов часто используется прием, сводящий функции от нескольких аргументов к функции от одного аргумента.

Пусть имеется некоторая взаимно-однозначная нумерация пар. Пусть номер пары (х, у) задается функцией Р(х, у), а левый и правый элементы пары с номером n определим функциями l(n), r(n).

Функции P(х, у), l(n), r(n) называют нумерационными. Они удовлетворяют следующим соотношениям:

На основе нумерации пар легко получить нумерацию троек, четверок.

P3(x, y, z) = P (P (x, y), z) z = r(n)

P(x, y) = l(n) x = l (l (n))

y = r (l (n))

Если P, l, r – рекурсивные, то и построенные на их основе нумерационные функции тоже будут рекурсивными.

Следующая задача сводится к нумерации пар.

Опишем одну из возможных нумераций Р(х, у) = 2х(2у + 1) – 1 эта функция рекурсивна, так как при любом х и у

2х(2у + 1)

Р(х, у) может быть записана в следующем виде:

2х(2у + 1) = 1

По номеру n = 2х(2у + 1) – 1пары (х, у) левый элемент х мы найдем в соответствии со следующим равенством:

х = СТ2(n+1) (1)

Возьмем следующее соотношение:

(2)

Правые части выражений (1) и (2) представляют собой функции l(n) и r(n). Эти функции рекурсивны, так как являются суперпозициями рекурсивных функций. Таким образом, построенная нумерация пар обладает нужными свойствами.

14)Совместная рекурсия.

Всхеме совместной рекурсии одновременно участвуют несколько функций. В случае 2х функций

f1 (х1, х2, …, хn, y) f2(х1, х2, …, хn, y)

Схема совместной рекурсии имеет следующий вид: = (х1, х2, …, хn)

Попытаемся доказать, что если функции g1, g2, h1,h2 частично рекурсивны, то такими же будут и

функции f1 и f2.

Для доказательства введем следующую функцию

,где Р – нумерационная функция, тогда

,поэтому

, таким образом,

получим по схеме обычной рекурсии из частично рекурсивных функций.

u – частично рекурсивна

f1 – частично рекурсивна

f2 – частично рекурсивна

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

Подобно тезису Тьюринга, в теории рекурсивных функций выдвигается соответствующая гипотеза, носящая название тезиса Черча:

Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна.

40. Нормальные алгоритмы Маркова. Тезис Маркова.

Марковские подстановки.

Пусть А – алфавит (любое непустое множество символов(букв). Слово – это любая последовательность букв данного алфавита. λ – пустое слово.

Если А и В – два алфавита, причем А B, то алфавит В называется расширением алфавита А. Пусть Р,Q,R,P1,P2,… - обозначения слов.

Если А – алфавит русских букв, а Р1 = параграф, Р2 = граф, Р3 = pa, то будем говориться, что слово Р2 является подсловом слова Р1 или вхождением в слово Р1, Р2 – подсловом Р1 и Р2, причем в Р1 оно входит дважды.

Марковской подстановкой называется операция (P,Q) над заданным словом R, означающая замену первого вхождения (если оно есть) слова Р в слова R на слово Q. Если вхождения Р в слово R нет, то подстановка (Р,Q) неприменима к слову R.

R	(P,Q)	Результат
1 3 5 6 2	(365,0)	102
тарарам	(ара, λ)	трам
шрам	(ра,ар)	шарм
функция	(λ, ξ -)	ξ - функция
книга	(λ, λ)	книга
поляна	(пор, Т)	неприменима

Формула подстановки (P,Q) – это запись вида P →Q.

Подстановка (P,Q), после которой работа алгоритма останавливается, называется заключительной, обозначается как P →Q; Р – левая часть, Q – правая часть в формуле подстановки.

Нормальные алгоритмы и их применение к словам.

Упорядоченный конечный список формул подстановок

в алфавите А называется схемой (или записью) нормального алгоритма в А. Точка в скобках означает, что она может стоять в этом месте, а может отсутствовать.

Нормальный алгоритм Маркова в алфавите А

V0 = V → V1 → V2 → … → Vm-1 → Vm = W

определяется следующей блок схемой:

- в этом направлении двигается слово, если подстановка неприменима ко входному слову.

Если процесс построения последовательности V,V1,V2,…,W обрывается, то говорят, что нормальный алгоритм применим к слову V, а W – результат применения нормального алгоритма к V.

Если алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над А.

Пример. Дана функция

φ(11…1) =

n – число единиц в слове 11…1

Нормальный алгоритм в алфавите А={1}, реализующий данную функцию, имеет вид:

1111111 → 1111 → 1 → ;

111111 → 111 → → 1.

Пример. Построим нормальный алгоритм для вычисления функции f(x) = x+1 в десятичной системе счисления (А = {0,1,2,3,4,5,6,7,8,9}). Для этого нам понадобится расширение В = А U {a,b}. Схема нормального алгоритма имеет вид:

0b	→	a0 → 0a
1b →		a1 → 1a 1a → 1b
2b	→	a2	→ 2a	2a → 2b
…		…		…
8b	→	a9	→ 9a	9a → 9b
9b	→ b0	0a	→ 0b	→ a

b →

→ a → aa → aaa → …

К пустому слову данный алгоритм не применим

499 → а499 →4а499 → 49а9 → 499а → 499b → 49b0 → 4b00 → 500

Определение. Функция f, заданная на множестве слов алфавита А, называется нормально

вычислимой, если найдется такое расширение В данного алфавита (АВ) и такой нормальный алгоритм в В, что каждое слово V (в алфавите А) из области определения функции f этот алгоритм перерабатывает в слово f(V).

Тезис Маркова.

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