Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Вычислимость и разрешимость




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

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

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

Подмножество множества натуральных чисел M⊂ N называется разрешимым, если его характеристическая функция

χM(x)=1 при x∈M, χM(x)=0 при x∉M

рекурсивна. Содержательно разрешимость множества M означает, что существует алгоритм, позволяющий по любому числу x определить за конечное число шагов, принадлежит это число множеству M или нет.

Подмножество множества натуральных чисел M⊂ N называется перечислимым, если оно является областью значений некоторой общерекурсивной функции f. Перечислимость множества M означает, что его элементы могут быть последовательно выписаны (возможно с повторениям) с помощью некоторой эффективной процедуры. Всякое непустое разрешимое множество M является перечислимым.

Доказательство. Несложно определить перечисляющую функцию f. Пусть m – произвольный элемент множества M. Определяем по рекурсии:

f(0)=m; f(x+1)=χM(x)(x+1)+(1−χM(x+1))f(x),

то есть f(x+1)=x+1, если x+1∈M, и f(x+1)=f(x), если x+1∉M.􀀀

Обратное, вообще говоря, неверно. Не всякое перечислимое множество является разрешимым. Перечислимое множество разрешимо лишь в том случае, когда перечислимо также и его дополнение.

В конце п. 4.4 было показано, что частично рекурсивные функции можно эффективно перенумеровать, используя их рекурсивные описания. Некоторые номера соответствуют общерекурсивным функциям. Обозначим множество таких номеров через M и покажем, что множество M неперечислимо.

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

Доказательство. Предположим противное. Пусть ϕ(x) – общерекурсивная функция, множеством значений которой является M. Тогда последовательность ϕ(0), ϕ(1), ϕ(2),… содержит номера всех общерекурсивных функций, и только их. Следуя диагональному методу, определим функцию g(x) формулой

g(x)=fϕ(x)(x)+1.

Это определение дает алгоритм вычисления значений функции g(x). В соответствии с тезисом Черча, функция g(x) частично рекурсивна, и, значит, общерекурсивна, поскольку функция g(x) определена для любого x. Значит, функция g(x) должна получить свой номер при перечислении с помощью ϕ(x). Пусть этот номер равен n, то есть g(x)=fϕ(n)(x). Но тогда g(n)=fϕ(n)(n)+1=g(n)+1, что невозможно.􀀀

Вообще неперечислимые и неразрешимые семейства функций – это не «экзотика», а, скорее, норма.

Приведем без доказательства следующую теорему.

Терема (Райс). Никакое нетривиальное семейство вычислимых функций не является алгоритмически разрешимым.

Иными словами, если C – некоторое семейство вычислимых функций такое, что есть функции, входящие в это семейство, а есть и не входящие в него, то множество номеров функций из C неразрешимо. Не существует алгоритма, который бы позволял по номеру функции сказать, входит она в C или нет.

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

Булевы функции

Двоичные векторы

Любое положительное целое число имеет единственное двоичное представление (в виде суммы неповторяющихся степеней числа 2). Например:

7=1+2+4; 35=32+2+1.

В общем случае, чтобы получить двоичное представление целого числа x>0, можно воспользоваться следующим соотношением:

x = α0+2(α1+2(α2+…+2(αn−2+2αn−1)…),

где α0 – остаток от деления x на 2 (то есть α0=0, если x четно, и α0=1, если x нечетно); α1 – остаток от деления на 2 числа x1=(x−α0)/2; α2 – остаток от деления на 2 числа x2=(x1−α1)/2; и т.д. Тогда

x = αn−1⋅2n-1n−2⋅2n-2+…+α1⋅2+α0.

Числа α0, α1,…, αn−1 называют двоичными цифрами числа x, а последовательность из нулей и единиц

αn−1αn−2…α1α0

– двоичной записью числа x. Пишут также

x = (αn−1αn−2…α1α0)2.

Пример.

25=1+2⋅12=1+2⋅(0+2⋅6)=1+2⋅(0+2⋅(0+2⋅3))=

= 1+2⋅(0+2⋅(0+2⋅(1+2⋅1)),

откуда

25=1⋅1+0⋅2+0⋅4+1⋅8+1⋅16.􀀀

Самое большое число, которое можно записать с помощью n двоичных цифр, содержит в свой двоичной записи одни единицы. Это число равно

2n-1+2n-2+…+2+1=2n−1.

Декартову степень {0,1}n , n≥1, составляют всевозможные упорядоченные последовательности из нулей и единиц длины n. Мы будем называть такие последовательности n-мерными двоичными векторами.

Произвольному n-мерному двоичному вектору можно сопоставить неотрицательное целое число, двоичными цифрами которого служат компоненты вектора

12,…,αn)→ α1⋅2n-12⋅2n-2+…+αn-1⋅2+αn.

Этим устанавливается взаимно однозначное соответствие между множеством всех n-мерных двоичных векторов и множеством неотрицательных целых чисел, меньших 2n. Таким образом, общее число n-мерных двоичных векторов равно 2n, то есть |{0,1}n|=2n.

Пример. При n=3 имеем:

(0,0,0) ↔ 0; (0,0,1) ↔ 1; (0,1,0) ↔ 2; (0,1,1) ↔ 3;

(1,0,0) ↔ 4; (1,0,1) ↔5; (1,1,0) ↔ 6; (1,1,1) ↔ 7.􀀀

Пусть α=(α12,…,αn) и β=(β12,…,βn) – двоичные векторы. Будем писать α≤β (или β≥α), если αi≤βi для всех i=1,2,…, n. Если α≤β, но α≠β, будем писать α<β (последнее означает, что αi.≤βi для всех i=1,2,…, n, и при этом хотя бы одно из этих неравенств строгое). Заметим, что имеются векторы α и β, для которых неверно ни α≤β, ни β≤α. Такие векторы будем называть несравнимыми.

Примеры. Двумерные двоичные векторы можно рассматривать как вершины единичного квадрата в двумерном евклидовом пространстве:

(0,1)(1,1)(0,0)(1,0)

Векторы α и β связаны отношением ≤, если из вершины α можно пройти в вершину β по сторонам квадрата в направлении координатных осей (направо и вверх). Аналогично, трехмерные векторы соответствуют вершинам куба; векторы α и β связаны отношением ≤, если из вершины α можно пройти в вершину β по ребрам куба в направлении координатных осей.􀀀






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных