| Теория вычислимости |
| 1 | Дополнительные главы теории вычислимости Учебное пособие по спецкурсу С. Ю. Подзоров НГУ, 2004 - 2005. 1 Введение Предполагается, что читатель знаком с теорией алгоритмов в объеме основного курса, читаемого на ММФ НГУ в первом семестре1. Кроме того, предполагается знание математической логики в объеме основного университетского курса. Главным образом это касается таких тем, как ординалы и исчисление предикатов. |
| 2 | Все необходимое из математической логики можно найти в книге 2. Большую часть изложенного в этом спецкурсе можно найти (иногда в несколько другой формулировке и с другими доказательствами) в книгах 3, 4, 5. Ниже мы кратко изложим те необходимые понятия и обозначения, которые вводятся в курсе теории алгоритмов, читаемом в первом семестре. Под конструктивным объектом понимается объект, который может быть полностью описан некоторой конечной последовательностью символов конечного алфавита. |
| 3 | Множество всех конструктивных объектов одинаковой природы образует конструктивное пространство. Примерами конструктивных пространств являются множества2 N, Nk для целого положительного k, N<^ (множество всех конечных последовательностей, составленных из натуральных чисел) и Pfln(N) (множество всех конечных подмножеств натурального ряда). ХВ том варианте, как его читает автор спецкурса на втором потоке. |
| 4 | На других потоках отсутствуют некоторые темы, например, конструктивные пространства. С курсом лекций второго потока в электронном варианте можно ознакомится, скачав документ по ссылке, расположенной на http:www.nsu.rueducationpodzorovAlg 2Натуральный ряд начинается с нуля. 1 Частичная функция из одного конструктивного пространства в другое называется частично вычислимой, если существует алгоритм, который по любому описанию объекта, попадающего в область определения этой функции, позволяет за конечное время получить описание значения функции на этом объекте и в то же время не заканчивает свою работу, если ему на вход подается описание конструктивного объекта, не принадлежащего области определения. |
| 5 | Частично вычислимая функция называется вычислимой функцией, если она всюду определена3. Область определения частичной функции f мы обозначаем через Sf, а область значений — через pf. Изоморфизмом конструктивных пространств называется вычислимая биекция между этими пространствами. Можно показать, что обратное к изоморфизму отображение всегда является вычислимой функцией. Все бесконечные конструктивные пространства изоморфны. |
| 6 | Для конструктивного пространства K изоморфизм из N на K называется гёделевской нумерацией пространства K. Для каждого бесконечного конструктивного пространства K зафиксируем его гёделевскую нумерацию yk.. Большинство понятий, которые позднее будут введены для объектов, связанных с N, могут быть перенесены на произвольное K через yk (например, A ^K называем рекурсивно перечислимым, если Y-l(A) — рекурсивно перечислимое подмножество N и т. п.). |
| 7 | Для случая K = N2 значение зафиксированной нами гёделевской нумерации на аргументе x будем обозначать (l(x),r(x)). Обратную функцию обозначим через c(x, y) (то есть через c обозначим единственную функцию со свойством c(l(x),r(x)) = x). Ясно, что функции l(x), r(x) и c(x,y) вычислимы4; кроме того, l(x) и r(x) — так называемые функции большого размаха (то есть такие функции из N в N, относительно которых у каждого натурального числа существует бесконечно много прообразов). |
| 8 | Аналогично для случая K = Nk значение зафиксированной гёделевской нумерации на аргументе x мы обозначаем (c'k(x),..., dk(x)) (считая, что cf(x) = l(x) и c2(x) = r(x)), а обратную функцию — ck(x\,... ,xk). Для функций из Nk в N имеется хорошо известный подход, опре- 3То есть определена во всех точках конструктивного пространства, элементы которого рассматриваются как ее аргументы. 4Обычно полагают c(x, y) = ((x + y)2 + 3x + y)2. |
| 9 | 2 деляющий вычислимость через так называемые частично рекурсивные функции (то есть функции, которые можно получить из базисных применением конечного числа суперпозиций, примитивных рекурсий и минимизаций, определения см. в основном курсе теории алгоритмов). Мы принимаем тезис Чёрча и считаем, что частичная вычислимость функций из Nk в N равносильна их частичной рекурсивности. Существует универсальная вычислительная машина5, работающая по шагам и позволяющая вычислять любую частично вычислимую функцию из N<^ в N. |
| 10 | Эта машина работает по программе; множество программ образует конструктивное пространство и каждая программа имеет номер в зафиксированной нами гёделевской нумерации. Для набора натуральных чисел x = x\, ...,xk пусть m, если все элементы набора x меньше t, длина набора меньше t и программа c номером n, получив на входе набор С, дает на выходе число m не более чем за t шагов; не определено, иначе. Для фиксированных n и x считаем, что fn(x) = m, если для некоторого to (а значит и для всех t ^ t0) рП (x) = m; в противном случае считаем, что значение ipn(x) не определено. |
| … |
Комментарии