Войти на сайт

или
Регистрация

Навигация


4. Операторні та предикатні алгоритми -ІІ

 

(Рекурсивні функції на областях, що відмінні від N)

Оскільки БРМ працює тільки з натуральними числами, наше визначення обчислюваності і можливості розв'язання застосовано тільки до функцій і предикатів від натуральних чисел. Ці поняття легко поширюються на інші види об'єктів (тобто цілі числа, поліноми, матриці і т.д.) за допомогою кодування.

Кодуванням області D об'єктів називається явне й ефективне відображення α: D →N. Ми будемо говорити, що об'єкт α ? D кодується натуральним числом α (d). Припустимо, що f є функцією з D в D; тоді f природно кодується функцією f* з N в N, що відображає код кожного об'єкта d ? Dom(f) у код об'єкта f (d). У явному виді це можна записати як

 

f*=α · f ·a-1

Тепер можна поширити визначення Мнр-обчислюваності на область D, рахуючи функцію f обчислюваною, якщо f*–обчислювана функція натуральних чисел.

Приклад. Розглянемо область Z. Явне кодування можна задати функцією α, де

2n, якщо n ³ 0,

α-(n) =

-2n-1, якщо n < 0.

Тоді α-1 задається так:

(1/2) m, якщо m парне,

α-1 (m) =

(-1/2) (m+1), якщо m непарне.

Тепер розглянемо функцію х-1 на Z; позначаючи цю функ-ю через f, одержуємо f*:N →N, що задається:

1, якщо x:==0 (тобто х=α(0)),

f*(x)= х-2, якщо х> 0 і х парне (тобто х=а(п), п>0),

х +2, якщо х непарне (тобто х=α(n), п < 0).

Написання програми, що обчислює f*, є рутинною вправою; отже, х-1 є обчислювана функція на Z.

Приведене вище визначення очевидним образом розширюється на n-місцеві обчислювальні функції на області D і розв'язні предикати на D.

5. Алгоритмічні проблеми для L

 

Нижче дається огляд нерозв'язних проблем, що виникають у самій теорії обчислювальності, і обговорюються деякі методи доказу нерозв'язності. Нагадаємо, що предикат М(х) називається розв'язним, якщо його характеристична функція, що задається формулою


1, якщо M(x) правдиве,

Cm (x) =

0, якщо M(x) неправдиве

обчислювана. Це рівносильно твердженню про те, що предикат М (х) рекурсивний Предикат М (х) називається нерозв'язним, якщо він не є розв'язним. У літературі використовуються наступні терміни, еквівалентні твердженню про те, що предикат М (х) розв'язний:

М (х) рекурсивний,

М (х) має рекурсивну проблему дозволу,

М (х) рекурсивно розв'язний,

М (х) обчислювальний.

Алгоритм, що обчислює см, називається обчислювальною процедурою, для M(x).

1. Нерозв'язні проблеми в теорії обчислюваності

У більшості випадків докази нерозв'язності ґрунтуються на діагональному методі, як, наприклад, у наступному важливому прикладі.

1.1. Теорема. Проблема «x ÎWx» (чи, що еквівалентно, «функція fx(х) визначена», чи «Рx(х)¯», чи «функціяyu(х, х) визначена») нерозв'язна.

Доведення. Характеристична функція цієї проблеми задається наступною формулою:

1, якщо xÎ Wx

f(x)=0, якщо xÏ Wx

Припустимо, що функція f обчислювана, і приведемо це припущення до протиріччя. Саме за допомогою діагонального методу ми побудуємо обчислювану функцію g, таку, що Dom(g)¹Wx(= Dom(фx)), при всіх х, чого, мабуть, бути не може.

Як завжди при використанні діагонального методу, ми будемо прагнути до того, щоб множина Dom(g) відрізнялося від Wx у njxці х. Тому будемо домагатися того, щоб

x Î Dom (g) Ûx ÏWx

Визначимо тепер функцію g у такий спосіб:

g(x)= 0, якщо xÏ Wx (тобто якщо f(x)=0),

не визначена, якщо xÎ Wx (тобто якщо f(x)= 1).

Оскільки функція f обчислювана, то (по тезі Черча) обчислювана і функція g, що і дає необхідне протиріччя. (Більш докладно, оскільки функція g обчислювана, візьмемо таке т, що g=fm, тоді т Î Wm Û т Î Dom (g)Ûт Ï Wm, чого не може бути.)

Отже, ми робимо висновок, що функція f не є обчислюваною, і, отже, проблема «x ÎWx» нерозв'язна. ÿ

Зауважимо, що ця теорема зовсім не затверджує, що ми не можемо для будь-якого конкретного числа а сказати, чи буде визначене значення fa (a). Для деяких чисел зробити це дуже просто. Наприклад, якщо ми написали програму Р, що обчислює тотальну функцію, і Р=Рa, то ми відразу знаємо, що значення fa (a) визначено. Теорема говорить лише, що не існує єдиного загального методу рішення питання про те, чи буде fx(х) визначено; іншими словами, не існує методу, що працює при всіх х.

Простий наслідок цього результату полягає в наступному.


Информация о работе «Алгоритмічні проблеми»
Раздел: Математика
Количество знаков с пробелами: 54576
Количество таблиц: 5
Количество изображений: 0

Похожие работы

Скачать
33080
5
4

... число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра. 3. Непрерывные генетические алгоритмы. Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены ...

Скачать
18213
1
5

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

Скачать
26020
3
4

... M2(n) = O(l n), C2(n) = O(l n). Оскільки l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Тому що C1(n) < C2(n), M1(n) < M2(n), остаточно одержуємо оцінки складності алгоритму TreeSort за часом: M(n) = O(n log2 n), C(n) = O(n log2 n), У загальному випадку, коли n не є ступенем 2, сортуюче дерево будується трохи інакше. “Зайвий” елемент ...

Скачать
10075
2
1

... U4 сравнения двух целых чисел оставляем читателю в качестве упражнения. Замечание: исходное слово надо задать в форме  * Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга. Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий. Построение алгоритмов из алгоритмов. До сих пор, строя ту или иную МТ, или НАМ мы каждый раз ...

0 комментариев


Наверх