1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 21
Текст из файла (страница 21)
Тогда существует разнозначная в.ф. g(x, t) такая, что для всех x, y, t ∈ ω выполняется ψx (y) = ψg(x,t) (y).В частности, для одноместной функции ψx существует бесконечно много чиселn ∈ ω таких, что ψx = ψn .§ 22. Единственность сильно универсальной функции85Доказательство. Рассмотрим ч.в.ф. f (x, t, y) = ψx (y) + 0· t (t — фиктивная). Полемме 68 существует разнозначная в.ф. g(x, t) такая, что f (x, t, y) = ψg(x,t) (y). Следовательно, ψx (y) = ψg(x,t) (y).Лемма 70.
Существует двухместная ч.в.ф. kx (y) такая, что если æx (y) — вычислимая перестановка на ω, то kx (y) = æ−1x (y).Доказательство. kx (y) = µz[|æx (z) − y| = 0] — искомая ч.в.ф. от переменных hx, yi.1−1Определение. Любая вычислимая биекция p : ω −−→ ω называется вычислимойнаперестановкой.Определение. Двухместные частичные функции ψn (x) и θn (x) называются вычис1−1лимо изоморфными, если существует вычислимая перестановка p : ω −−→ ω такая,начто для любых n, x ∈ ω выполняетсяψp(n) (p(x)) = p(θn (x)).Другими словами, ψ и θ вычислимо изоморфны, если существует вычислимая перестановка p, которая отображает график Γθ = {hn, x, θn (x)i | θn (x) ↓} покоординатнона график Γψ = {hn, x, ψn (x)i | ψn (x) ↓}.hn, xipyθ−−−→θn (x)pyhp(n), p(x)i −−−→ ψp(n) (p(x))ψТеорема 71 (о вычислимом изоморфизме сильно универсальных функций).Любые две сильно универсальные ч.в.ф.
ψn (x) и θn (x) вычислимо изоморфны.Доказательство. Нам нужно доказать, что существует вычислимая перестановка1−1p : ω −−→ ω такая, что для любых x, y ∈ ω выполняетсянаψp(x) (p(y)) = p(θx (y)).Докажем, что существует двухместная вычислимая функция hz (x) такая, что длялюбого z ∈ ω функция hz : ω → ω является вычислимой перестановкой, такой, чтодля любого x ∈ ω выполняется хотя бы одно из следующих двух условий:ψhz (x) = æz θx kzkz ψhz (x) æz = θx(∗)(∗∗)Допустим, мы уже доказали существование такой функции hz (x). Тогда по теореме о параметризации существует в.ф. s(z) такая, что hz (x) = æs(z) (x). Далее потеореме о неподвижной точке найдется число n ∈ ω такое, что æs(n) = æn = hn .
Обозначим p(x) = hn (x) = æn (x). Так как hn — вычислимая перестановка, то æn тоже−1вычислимая перестановка, и, следовательно, в силу леммы 70 kn = æ−1n = p . Тогдаиз (∗) и (∗∗) заключаем, что для любого x ∈ ω выполняется хотя бы одно из условий:ψp(x) = pθx p−1p−1 ψp(x) p = θx(∗)(∗∗)86Глава IV. Теория вычислимостиВ любом случае, получаем ψp(x) p = pθx , т. е. ψp(x) (p(y)) = p(θx (y)), и наша теоремадоказана.Таким образом, осталось доказать существование функции hz (x) с нужными свойствами. Поскольку график функции однозначно задает саму функцию, то мы будемстроить график функции Γh = {hz, x, hz (x)i | z, x ∈ ω}.
Поскольку в силу теоремы о графике вычислимость h равносильна вычислимой перечислимости Γh , то мыопишем алгоритм перечисления троек из графика Γh .Для каждого z ∈ ω мы опишем равномерный пошаговый алгоритм перечисленияпар hx, ui таких, что тройка hz, x, ui ∈ Γh . На каждом шаге будем добавлять новуютройку в график Γh . Шаги будут делиться на нечетные и четные. На шаге n будемстроить конечное множество Mn такое, что M0 ⊆ M1 ⊆ .
. . ⊆ Mn ⊆ . . ., и каждое Mnсостоит из пар hx, ui с условием hz, x, ui ∈ Γh .Перейдем к описанию пошаговой конструкции.Шаг 0. Полагаем M0 = ∅.Шаг 2t + 1 (добавление нового элемента в dom(hz )).а) Ищем наименьшее x, не содержащееся среди левых координат пар из M2t .б) Ищем u, не содержащееся среди правых координат пар из M2t , такое, что∀y ∈ ωψu (y) = æz θx kz (y)(∗).Данное u находится эффективно следующим образом.
По лемме 68 существуетв.ф. g(z, x) такая, что ψg(z,x) (y) = æz θx kz (y). Для заданных значений z и x числоv = g(z, x) является фиксированным. По лемме 69 существует разнозначнаяв.ф. r(v, s) такая, что для любого s ∈ ω выполняется ψv (y) = ψr(v,s) (y). Таккак множество {r(v, 0), r(v, 1), . . .} бесконечно, а множество M2t конечно, тонайдется наименьшее s такое, что число u = r(v, s) не содержится среди правыхкоординат пар из M2t , и ψu = ψv = æz θx kz . Данное u — искомое.в) Полагаем M2t+1 = M2t ∪ {hx, ui}, hz (x) = u. Перечисляем тройку hz, x, ui вграфике Γh .Шаг 2t + 2 (добавление нового элемента в range(hz )).а) Ищем наименьшее u, не содержащееся среди правых координат пар из M2t+1 .б) Находим аналогично нечетному шагу число x, не содержащееся среди левыхкоординат пар из M2t+1 , такое, что∀y ∈ ωkz ψu æz (y) = θx (y)(∗∗).в) Полагаем M2t+2 = M2t+1 ∪ {hx, ui}, hz (x) = u.
Перечисляем тройку hz, x, ui вграфике Γh .§ 22. Единственность сильно универсальной функции87M2t+2M2t+1M2t•••Определим M =Shzhz···hz•xhz•x0hz-•-•-•-•u-•u0Mt . Положим: hz (x) = u ⇐⇒ hx, ui ∈ M . По построению hzt∈ωявляется функцией. В силу пункта (а) нечетного шага dom(hz ) = ω. В силу пункта(а) четного шага range(hz ) = ω. Из построения также следует, что hz — инъективное1−1отображение. Так как M перечислимо, то по теореме о графике hz : ω −−→ ω —навычислимая перестановка, и по построению для hz выполняется (∗) или (∗∗) длялюбого значения x.Следствие 72.
Двухместная ч.в.ф. ψx (y) является сильно универсальной тогда итолько тогда, когда она вычислимо изоморфна клиниевской функции æx (y).Доказательство. (=⇒) Следует из предыдущей теоремы и из сильной универсальности клиниевской функции æx (y).(⇐=) Пусть ψx (y) вычислимо изоморфна æx (y). Следовательно, существует вычислимая перестановка p такая, что для любого x ∈ ω выполняется ψp(x) = p· æx · p−1 .Пусть f (x, y) — произвольная ч.в.ф.
Рассмотрим двухместную ч.в.ф. p−1 (f (x, p(z))).По s-m-n-теореме существует вычислимая разнозначная функция s(x) такая, чтоp−1 (f (x, p(z))) = æs(x) (z). Теперь, сделав замену z = p−1 (y), заключаем, что f (x, y) =p· æs(x) · p−1 (y) = ψp(s(x)) (y). Вычислимая разнозначная функция p(s(x)) является искомой.Следствие 73. Никакая слабо универсальная ч.в.ф. не является вычислимо изоморфной никакой сильно универсальной ч.в.ф.Глава VТеория сложности алгоритмов§ 23.О вычислительной сложностиКлассическая теория вычислимости, с введением в которую мы познакомились вдвух предыдущих главах, подразумевает, что все абстрактные вычислительные устройства удовлетворяют принципу потенциальной осуществимости, т.
е. предполагается, что при осуществлении процесса вычисления, определенного алгоритмом, мыимеем неограниченный запас времени и материалов. Однако количество простейшихдействий, необходимых для получения результата вычисления, может быть весьмабольшим. На первый взгляд, учитывая достижения индустрии компьютерных технологий, данная проблема кажется несущественной. Тем не менее, вычислительнаяпрактика показывает, что многие алгоритмические проблемы, которые в принципе разрешимы, невозможно решить на современных вычислительных устройствах,поскольку алгоритмы решения этих проблем требуют в буквальном смысле космических затрат времени и ресурсов. Примерами таких задач являются классическиезадачи из комбинаторики: задача о коммивояжере, задача о гамильтоновом цикле,задача выполнимости булевой формулы и др.Пример.
Рассмотрим, например, задачу о коммивояжере. Постановка этой задачи очень проста: на карте обозначены n городов и известны расстояния между ними, коммивояжеру (который находится в одном из этих городов) необходимо найтимаршрут обхода всех городов, имеющий минимальную длину. Теоретически эта задача безусловно разрешима. Если необходимо посетить n городов, то число всевозможных маршрутов равно в точности (n−1)!. Поэтому достаточно найти длины всехмаршрутов и выбрать из них минимальную. Однако если мы начнем реализовыватьэтот алгоритм на практике, то сразу придем к выводу о его непригодности. Допустим, коммивояжеру необходимо посетить 10 городов.
Тогда потребуется перебрать9! = 362880 маршрутов, такая задача вполне по силам современному компьютеру. Если же, например, количество городов равно 40, то потребуется перебрать 39! маршрутов, а это уже больше, чем 1045 . Даже если мы сможем просчитывать 1015 маршрутовв секунду (что гораздо быстрее, чем быстродействие многих современных суперкомпьютеров), то время, необходимое для завершения вычислений, составит несколькомиллиардов сроков жизни Вселенной!Теория вычислительной сложности отказывается от принципа потенциальной осуществимости.
Если в классической теории вычислимости совокупность всех алгоритмических проблем разбивалась на две категории — разрешимые и неразрешимые,то в теории сложности возникает более тонкая классификация алгоритмических проблем: в зависимости от затрачиваемых времени и ресурсов различают более приемлемые и менее приемлемые алгоритмы.
Общепринято, что если задачу нельзя решить§ 24. Недетерминированные машины Тьюринга89быстрее, чем за экспоненциальное время, то ее следует рассматривать как трудноразрешимую. В нашем примере с задачей о коммивояжере функция (n − 1)! растетбыстрее, чем 2n , поэтому предложенный алгоритм перебора всех маршрутов оказывается непригодным. Поскольку экспоненциальная функция (такая, как 2n ) растетбыстрее любой полиномиальной функции от n, то при таком соглашении задачи,решаемые алгоритмами полиномиальной сложности, будут легко разрешимыми.Таким образом, постулируется следующий тезис: алгоритмы, число операций которых оценивается некоторым полиномом p(n) от длины входных данных n, являются реально пригодными.При формальном изложении основ теории сложности в качестве модели вычислений традиционно используются машины Тьюринга.
При таком формализме времябудет измеряться числом тактов машины Тьюринга, затраченных на вычисление, апамять будет измеряться числом ячеек ленты, использованных при вычислении. Попричинам, которые скоро станут ясными, ключевое понятие в теории сложности —это недетерминированная машина Тьюринга.§ 24.Недетерминированные машины ТьюрингаОбычные машины Тьюринга, введенные нами ранее, называют также детерминированными машинами Тьюринга, подчеркивая тем самым, что в программе любойтакой машины для каждого состояния qi (i > 0) и любого внешнего символа aj существует ровно одна команда вида qi aj → .
. . Процесс вычисления на такой машинемы представляли как последовательность конфигураций, каждая из которых однозначно определялась предыдущей.По аналогии с недетерминированными конечными автоматами мы введем обобщенное понятие недетерминированной машины Тьюринга, которая отличается отдетерминированного варианта тем, что в ее программе для любого qi (i > 0) и любого aj может быть несколько (или нисколько) команд вида qi aj → .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
