МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. Математическая логика
 Скачать 1.08 Mb.
|
Машина Тьюринга Т= |
лфавитом внутренних состояний Q=q0, q1… qn;
рограммой , то есть совокупностью выражений Т(i, j) (i=0,n; j=0,m), каждое из которых имеет вид следующей команды qj ai qk aL dt (k=0,n; L=0,m; dt dЛ, dп, dн.| A\Q | q0 | qz |
| a0 | dн qz | a0 dн qz |
| | dn q0 | dн qz |
>
или
Пусть:
а) х=0, тогда q0 a0…a0 qzdн;
б) х=2, тогда q0 a0 q0 dn q0 a0 dn qz dн
Основной тезис Тьюринга.
Утверждение: «Для любой вычислимой функции можно построить машину Тьюринга, реализующую ее» - является гипотезой, называемой тезисом Тьюринга. (Часто этот тезис формулируют так: «Всякая вычислимая функция вычислима по Тьюрингу.)
Напомним, что этот тезис нельзя доказать, так как он объединяет два понятия – расплывчатое, интуитивное понятие вычислимой функции и строгое понятие машины Тьюринга.
Нормальные алгорифмы (алгоритмы).
Нормальные алгорифмы U=
Всякий нормальный алгоритм, являясь алгоритмом в некотором алфавите А, порождает в нем детерминированный процесс переработки слов. Поэтому любой нормальный алгоритм в фиксированном алфавите А вполне определяется указанием его схемы - упорядоченного конечного списка формул подстановки в А. Каждая такая формула по существу представляет пару <Л, п> слов в А (то есть Л, пА*). Слово Л называется левой частью этой формулы, а п – ее правой частью. Среди формул данной схемы некоторые выделяются специально и объявляются заключительными. Обычно в схеме нормального алгоритма заключительная формула записывается в виде Л п (, а незаключительная в виде Л п. При этом допустимы формулы вида : Лп п; Л
Нормальный алгоритм U в алфавите А есть предписание строить, исходя из произвольного слова в А (А*), последовательность слов i.
Так, пусть задан алфавит А=1, + и схема подстановок (здесь - пустое слово, то есть А*, Слово этот алгоритм перерабатывает так:
Процесс оканчивается применением заключительной подстановки, которая перерабатывает слово само в себя. Очевидно, что рассматриваемый алгоритм осуществляет операцию сложения (эквивалентный ему алгоритм <А=1, +, ++, +, >).
Пусть теперь - некоторое слово в А, то есть А*. Говорят, что поддается формуле, если левая часть этой формулы входит просто в . Считается, что всякое слово начинается простым вхождением пустого слова в . Считается, что всякое слово начинается вхождением пустого слова . Поэтому всякое слово поддается формуле с пустой левой частью.
Применением нормального алгоритма U к слову называется процесс, определяемый следующим правилом (представляющим собой алгоритм выполнения нормального алгоритма):
Считать, что i=1. Перейти к пункту 2.
Проверить, поддается ли преобразуемое слово i-ой формуле. Если да, то перейти к пункту 3, если нет – к пункту 5.
Первое простое вхождение левой части i-ой формулы в преобразуемом слове заменить правой частью i-ой формулы. Результат считать в дальнейшем преобразуемым словом, перейти к пункту 4.
Если i-ой формула является заключительной подстановкой, то процесс прекратить. В противном случае перейти к пункту 1.
Проверить, имеет ли место равенство i=n. Если да, то процесс прекратить, в противном случае перейти к пункту 6.
Увеличить значение i на 1 и перейти к пункту 2.
Любое слово в алфавите А может служить исходными данными для нормального алгоритма в алфавите А. При этом возможны случаи:
Процесс выполнения нормального алгоритма для слова А* заканчивается формулой Л п после конечного числа шагов. При этом говорят, что нормальный алгоритм применим к слову , и полученное после его выполнение слово * называется результатом.
Процесс выполнения нормального алгоритма при исходном слове А* никогда не заканчивается или происходит безрезультативная остановка (то есть не на формуле Л п). В этом случае говорят, что нормальный алгоритм не применим к слову .
Пример:
Алгоритм U= «обращает» любое слово в А, то есть перерабатывает его в слово, записанное в обратном порядке (его можно записать как 100 с тем, чтобы использовать ).
Так, слово 100 этот нормальный алгоритм последовательно перерабатывает в слова 010, 001, 001, 001, 001, 001, 001, 001, 001, 001, 001, 001, 001.
Замечание:
Последний член этой последовательности считается результатом применения алгоритма U к слову =100 и обозначается символом U(). При этом считается, что U перерабатывает =100 в =001, и пишут U()= (в нашем примере U(100)=001).
Пример:
Алгоритм U=<a, b,
Так, взяв слово babaa в качестве исходного данного после первого перехода (то есть применив формулу ba aba ), получим baaaba (здесь =baa), а после второго (то есть применив снова формулу ba aba) имеем aabaaba (здесь =ааba). Применив формулу aa к слову aabaaba получим результат baaba (то есть U(babaa)=baaba).
Однако, взяв в качестве исходного данного слова =baaba, получим бесконечную последовательность abaaba, baabab, abababa, bababab, babababa, … в которой не будет слова aa. Это означает, что алгоритм U не будет применим к слову =baaba.
Если же исходным данным взять слово abaab, то получим конечную последовательность baabb, abbaba, bbabab, в которой к последнему слову нельзя применить допустимый переход, то есть это случай безрезультативной остановки (это означает также неприменимость заданного алгоритма U к слову abaab).
Считается, что для любого алгоритма В в алфавите А может быть построен нормальный алгоритм U над этим алфавитом, перерабатывающий произвольное слово А* в тот же самый результат, в который перерабатывает его исходный алгоритм В. Это соглашение известно в теории алгоритмов под названием принципа нормализации.
Уточнение понятия алгоритма, осуществленного на основании понятия нормального алгоритма, оказывается эквивалентным другим известным уточнениям (в частности, на основе абстрактной машины Тьюринга). Вследствие этого принцип нормализации оказывается равносильным тезису Черча, предлагающему считать понятие частично рекурсивной функции адекватным уточнением понятия вычислимой арифметической функции f:Nn0N0, N0=N0, nN (к ней путем метода арифметизации могут быть приведены числовые и нечисловые функции).
Рекурсивные функции.
Рекурсивная функция (частично рекурсивная функция) – функция, заданная с помощью последовательности частичных (определенных не обязательно для всех значений своих аргументов) функций таких, что каждая функция последовательности либо является (базисной) простейшей функцией, либо получена из предыдущих с помощью операторов суперпозиции (подстановки) Snm, примитивной рекурсии Rn и минимизации .
Все рекурсивные функции являются вычислимыми функциями, то есть для любой такой функции можно указать алгоритм вычисления ее значений. Очевидно, что всякий алгоритм однозначно ставит в соответствие исходным данным (в случае, если он определен на них) результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Однако, обратное, то есть: «для всякой функции существует вычисляющий ее алгоритм», неверно.
Согласно тезису Черча, любая функция, считающаяся вычислимой в интуитивном смысле, является рекурсивной функцией. Эта гипотеза (тезис) подтверждается тем, что все известные вычислимые функции являются рекурсивными. Тезис Черча позволяет придать интуитивному понятию вычислимой функции точный алгоритмический смысл.
Понятие рекурсивной функции эквивалентно понятию функции, вычислимой на машине Тьюринга.
В теории рекурсивных функций, рассматриваемой ниже, как и вообще в теории алгоритмов, принят конструктивный, финитный подход, основной чертой которого является то, что все множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов – базиса – с помощью простых операторов (операций), эффективная выполнимость которых достаточно очевидна.
Замечание:
Всюду определенные рекурсивные функции называются общерекурсивными функциями.
Примитивно-рекурсивные функции.
Def. Всюду определенная функция от натуральных аргументов с натуральными значениями, которую можно получить из простейших базисных всюду определимых функций
f(x)=x+1, z(x)=0, Jnm(x1,…, xn)=xm
Конечным числом операторов (операций) суперпозиции (подстановок) Snm, и примитивной рекурсии Rn называется примитивно-рекурсивной (ПРФ).
Базисную функцию f(x)=x+1 принято называть функцией следования (эту функцию иногда обозначают х` и называют функцией прибавления единицы), z(x)=0 – нуль функцией, Jnm(x1,…, xn)=xm – функцией тождества (или введения фиктивных переменных), где nm.
Def. Оператором суперпозиции Snmназывается операция подстановки в функцию от m переменных m функций от n переменных. (одних и тех же).
Пример. Функция f(x1,…, xn) возникает из функций h(x1,…, xm), g1(x1,…, xn), …gm(x1,…, xn) суперпозицией, если
f(x1,…, xn)= Snm(h, g1,…, gm) = h(g1(x1,…, xn), …, gm (x1,…, xn)).
Если заданы функции Jnm и операторы Snm, то можно считать заданными всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.
Так, если f(x1, x2)= h(g1(x1, x2), g2(x1)), то ее стандартный вид следующий: f(x1, x2)= S22(h(x1, x2), g1 (x1, x2), S12 (J21(x1, x2), g2(x1), g3(x1))), где g3 – любая функция от х1. Если же имеем f(x2, x1, х3, …, xn) и f(x1, x1, x3,…, xn), то пишем:
f(x2, x1, х3, …, xn) = f(J22(x1, x2), J21(x1, x2), х3, …, xn),
f(x1, x1, x3,…, xn)= f(J21(x1, x2), J21(x1, x2), х3, …, xn).
Def.Оператором примитивной рекурсии Rn называется процесс определения функфии f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:
f(x1, x2, …, xn, 0)= g(x1, x2,…, xn)
f(x1, x2, …, xn, y+1)=h(x1, x2,…, xn, y, f(x1, x2, …, xn, y)),
где g и h – две различные функции соответственно n и n+2 аргументов.
Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что функция f определена схемой примитивной рекурсии выражается равенством f(x1, x2, …, xn, y)=Rn(g, h). В случае, когда n=0, то есть определяемая функция f является одноместной, схема примитивной рекурсии принимает более простой вид:
f(0)=с, f(у+1)=h(y, f(y)), где с – константа.
Схема примитивной рекурсии определяет f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение функции f в точке у+1 зависит от значения функции f в точке у. Очевидно, что для вычисления f(x1,…, xn, k) понадобиться k+1 вычислений по схеме примитивной рекурсии – для у=0, k.Замечания:
Существенным в операторе примитивной рекурсии Rn является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной у (остальные n переменных x1, x2, …, xn на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров).
Формальное индуктивное определение примитивно-рекурсивной функции следующее:
функции 0, х`, Jnm для всех натуральных n, m, где nm являются примитивно-рекурсивными;
если g1(x1,…, xn), …gm(x1,…, xn), h(x1,…, xm) - примитивно-рекурсивные функции, то Snm(h, g1,…, gm) - примитивно-рекурсивные функции для любых натуральных n, m;
если g(x1,…, xn) и h(x1,…, xm, у, z) - примитивно-рекурсивные функции, то Rn(g, h) – примитивно-рекурсивная функция;
других примитивно-рекурсивных функций нет.
Схемной интерпретацией примитивной рекурсии может быть схема:
Эта схема состоит из элемента, вычисляющего за один такт функцию h от двух переменных и элемента задержки на один такт. По каналам схемы могут передаваться натуральные числа. Время t считается дискретным, то есть t=0, 1, 2, 3…. Схема имеет один вход х и один выход f. Выход f зависит не только от х, но и от момента t, в котором он рассматривается. В начальный момент t=0 второй вход h является константой с, зависящей от начального состояния схемы: f(x, 0)=h(x, c)=g(x). В момент t=1: f(x, 1)=h(x, f(x, 0)); в общем случае f(x, t+1)=h(x, f(x,t)). Нетрудно убедиться, например, что если h выполняет умножение, а с=1, то f(x, t)=xt+1.
Поскольку исходные (базисные) функции являются вычислимыми, а операторы суперпозиции и примитивной рекурсии вычислимость сохраняют, то множество всех примитивно-рекурсивных функций есть подкласс класса всех вычислимых функций;
Класс всех примитивно-рекурсивных функций счетен, поскольку каждая такая функция задается описанием ее построения из исходных функций.
Практически все арифметические функции, употребляемые в математике по конкретным поводам, являются примитивно-рекурсивными функциями, например: х+у, х*у, ху и т.д.