Материал: Методичка Дзержинский

этих переменных, которое для каждого набора значений переменных либо не определено, либо истинно, либо ложно.

Определение: областью определения предиката Р (х1, …,хn) называется совокупность всех наборов х1 ...хn, для которых предикат Р (х1…,хn) либо И, либо Л.

Область истинности – множество всех наборов х1 …..хn для которых Р (х1,

….,хn) = И.

Характеристической функцией предиката Р называется функция

1, если Р (х1, ….,хn) =И

Хр(х1, …..,хn)

0, если Р (х1, ….,хn) =Л

Р(х1,х2) = х1 ≥х2

Определение: Предикат называется вычислимым по Тьюрингу если его характеристическая функция вычислима. Иногда предикат будем считать вычислимым если существует М. Тьюринга приводящая к конфигурации И x1*x2*…*xn,то есть перед первым аргументом стоит символ И. если Р (х1, ….,хn)

= И. .

Теорема: Если функция f1(x1,…,xn),f2(x1,…,xn) и предикат P(x1,…,xn) вычисляется по Тьюрингу, то и функция

f1(x1,…,xn) если Р (х1, ….,хn) =И

f(x1,…,xn)=

f2(x1,…,xn) если Р (х1, ….,хn) =/\

также вычислима по Тьюрингу.

Вычисление функции f(x1,…,xn) приводит к разветвлению вычисления.

Нужно доказать, что существует машина Тьюринга вычисляющая это разветвление. Будем считать что алфавиты состояний исходных машин не пересекаются. Программу искомой машины составим из программ исходных машин внеся изменения только в программу для Машины Тьюринга вычисляющей предикат. Те команды где есть конечное состояние Иqzph заменяем на /\q01R (то есть машина переходит к программе для f1),а команды Лqzph заменяем на /\q02R (то есть машина стирает значение «ложь», записывает

16

пустой символ и переходит к программе для f2.

Гёделевская нумерация

Это прием позволяющий любой алгоритм превратить в численный алгоритм, работающий с натуральными числами, объекты любой природы можно закодировать натуральными числами. Пусть существует некоторый алфавит А. Рассмотрим все слова языка А*=множество всех слов в алфавите А. Мы хотим все слова αєА* перенумеровать так чтобы соответствие между словом α и его номером N(α) было взаимно-однозначным. Если α=аi1ai2…ais то номер слова это N(α)=2i1*3i2*…*piss где ps-простые числа. Получим некоторое натуральное число, которое называется его геделевским номером. Это сопоставление каждому слову натуральное число называется первичной нумерацией по Гёделю.

Вторичная нумерация это если есть последовательность слов Π=α1α2…αn

тогда этой фразе взаимно-однозначно можно составить одно натуральное число

N(П)=2N(α1)*3N(α2)…PkN(αk)

С помощью третичной нумерации можно занумеровать любой текст.

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

По Гёделевскому номеру однозначно восстанавливается закодированный объект. Это следует из арифметики: всякое натуральное число однозначно разложимо в произведение степеней простых чисел.

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

ЧАСТИЧНО-РЕКУРСИВНЫЕ ФУНКЦИИ

Будем рассматривать функции аргументы и значения которых будут целыми неотрицательными числами.

Функция f(x1,…,xn) называется частичной, если, по крайней мере, на одном наборе значений аргументов она определена.

17

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

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

Пусть h(x1,…,xn),g1(x1,…,xm),…,gn(x1,…,xm) - частичная функция. Тогда про функцию f(x1,…,xm)=h(g1(x1,…,xm),…,gn(x1,…,xm)) будем говорить, что она получена из функций h;g1,…,gn при помощи операции суперпозиции.

II.Операция рекурсии (примитивная).

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

f(x1,…,xn,y+1)=h(x1,…,xn,y,f(x1,…,xn,y))

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

Пусть g(x1,…,xn-1,y) – частичная функция, зафиксируем набор

минимизации.

С помощью операции минимизации из функции сложение получается функция вычитание µn=(x+y=z)=z-x;

Среди частичных функций выделим так называемые базисные функции (элементарные).

1)Нуль-функция O(x)=0 при любом x=0,1,2,...

2)функция следования S(x)=x+1 при любом x=0,1,2,...

3)функция выбора Imn(x1,…,xn)=xm , 1≤m≤n

Определение: функция называется примитивно-рекурсивной, если она

18

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

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

Если частично-рекурсивная функция всюду определена, то она называется рекурсивной.

Примеры: 1) сложение f(x,y)=x+y рекурсивно: берем g(x)=I12(x,y)=x

;h(x,y,z)=S(z): тогда

2)Умножение x*y рекурсивно, так как если g(x)=O(x); h(x,y,z)=x

3)f(x,y)=xy рекурсивна так как,если g(x)=x0=1, h(x,y,z)=x*z

4) Усеченная разность x-y: сначала находим что f(y)=y-1 рекурсивно

g=0 h(y,z)=I12(y,z)=x:

Используя рекурсивные функции x 0 и x-1 строим функцию x-1 по схеме x-0=x : x-(y+1)=(x-y)-1

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

19

Задается алфавит А= -то есть любая конечная система различных символов. буквами называются символы составляющие алфавит. Словом в алфавите наз. любая конечная последовательность букв в этом алфавите.

Пустым словом называется слово, не содержащие ни одной буквы и обозначаемое символом /\. Два конкретных слова αi1… αin и bi1…bim в алфавите А равны если n=m и αik=bik . Все пустые слова считаются равными. Если αi1… αin-слово, состоящие из n букв то n-наз. длинной этого слова. Длинной пустого слова будет число 0.

Рассмотрим два слова: C и D в нек. алф. А. Если слово C является частью слова D,то говорят, что слово C входит в слово D. Процесс преобразования слов, позволяющий из заданного слова получить новые слова задается с помощью допустимых подстановок. Подстановка-это пара слов в рассматриваемом алфавите P→Ф. Эту подстановку можно применять к некоторому слову Р этого алфавита следующим способом : если в слове R имеется одно или несколько включений слова Р, то любое из этих включений может быть заменено словом Q.

Задается алфавит А и фиксируется схема подстановок. Алгоритм предписывает, исходя из произвольных слов R в алфавите А, просмотреть формулы подстановок в том порядке, в котором они заданы в схеме, разыскивая формулу с левой частью входящей в R. Если такой формулы не найдется, то процесс обрывается. В противном случае берется первая из таких формул и делается подстановка ее правой части вместо первого вхождения ее левой части в слово R, что дает новое слово R1 в алфавите А. После выполнения первого шага приступают ко второму шагу, отличающемуся от первого только тем, что роль R играет R1 Далее делают аналогичный третий шаг и так далее, до тех пор, пока не придется оборвать процесс. Оборваться же он может лишь двумя способами: во первых, когда мы получим такое слово Rn, что ни одна из левых частей формул схемы подстановок не будут в него входить;

Во вторых, когда при получении слова Rn нам придется применить “последнюю” формулу из подстановок “так называемую «заключительную»”.

20