[{{mminutes}}:{{sseconds}}] X
Пользователь приглашает вас присоединиться к открытой игре игре с друзьями .
Теория вычислимости
(0)       Используют 0 человек

Комментарии

Ни одного комментария.
Написать тут
Описание:
спецкурс 2004
Автор:
xsy
Создан:
18 октября 2013 в 23:52 (текущая версия от 18 октября 2013 в 23:54)
Публичный:
Да
Тип словаря:
Книга
Последовательные отрывки из загруженного файла.
Содержание:
677 отрывков, 338173 символа
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) не определено.
 

Связаться
Выделить
Выделите фрагменты страницы, относящиеся к вашему сообщению
Скрыть сведения
Скрыть всю личную информацию
Отмена