Решетка Медведева (Роджерс).

[пианист]

В книжечке Роджерса сводимость массовой проблемы $\mathcal A$ к массовой проблеме $\mathcal B$ определяется соотношением
$(\exists z)(\Psi_z(\mathcal B) \subset \mathcal A)$,
где $\Psi_z$ некое производное оператора перечисления ($\S 13.7$).
Вопрос, в чем смысл такого направления включения? Вроде как логично было бы наоборот; так получается, что какие-то функции из $\mathcal A$ остаются (могут остаться) "снаружи", стало быть, какая же это сводимость?
Роджерс поясняет сей момент так "Может создаться ошибочное впечатление, что $\mathcal A$ и $\mathcal B$ фигурируют в определении в порядке, обратном к применявшемуся ранее в определениях сводимости других типов". Вот оно у меня и создалось ;(
Статью Медведева как-то с ходу не удалось найти.

(Оффтоп)

Любопытно было бы также узнать что-нибудь о самом Медведеве.
Нашел только, что он был аспирантом Колмогорова, вместе с Успенским, и это практически все.
Последняя (найденая) статья датируется 1972 годом.

[george66]

Дело в том, что Медведев по другому определяет массовую проблему. Обычно проблему понимают как "множество данных", для которого надо построить решение в виде некоторой функции из этого множества куда-то (например, разрешающей или полуразрешающей). Медведев же сразу определяет проблему как множество её решений (функций). Свести задачу А к задаче В - значит указать способ находить решение А, если бы у нас было решение В. То есть, указать способ по любому решению В находить некоторое решение А. Это и есть определение Медведева. При обычном подходе сводится "один набор данных данных к другому" в обратную сторону.
Медведева я на кафедре не застал и не видел, могу спросить Крупского или Плиско.
Поздравляю, что дошли до 13-й главы! Как нравится книжка?

[george66]

Ну, например, пусть есть множества натуральных чисел А и В. Проблема разрешимости для А сводится к проблеме разрешимости для В если мы придумали "как построить разрешаюшую функцию для А, если бы у нас была разрешаюшая функция для В". То есть, придумали способ по каждой разрешающей функции для В получать разрешаюшую функцию для А.

[пианист]

Задумчиво.. А почему тогда не по _некоторому_ решению $\mathcal B$ найти некоторое решение $\mathcal A$?
Ну т.е. (точнее говоря) $(\exists z)(\Psi_z(\mathcal B) \cap \mathcal A \neq \emptyset)$
Вроде бы, общий смысл "свести" передается..

(Оффтоп)

Да я так, галопом по европам, доказательства на уровне идей ;).
От книги, честно говоря, не в восторге, я бы предпочел все-таки несколько более подробное изложение ;)).
По сути, это нечто среднее между справочником и реферативным журналом, большая часть результатов только изложена, доказательств даже на идейном уровне не приведено.
Но вот сама тематика интересная, я как-то раньше думал - ну, там, теорема Геделя, диагональная процедура, вот это вот все. Оказывается, пейзажи там довольно разнообразные :)
Интерес по поводу Ю.Т. Медведева довольно праздный. Просто удивился - в книге Роджерса его результатам уделяется много внимания, а о нем как-то ничего не известно (в отличие от, например, Успенского).

[george66]

Там идеология такая: если бог нам пошлёт какое-то решение задачи В, мы сможем найти решение задачи А. Какое он пошлёт, неизвестно, надо быть готовым к любому.
Роджерс умер два-три года назад в возрасте около 90. Я хожу на форум FOM
https://cs.nyu.edu/pipermail/fom/
там интересно читать некрологи (некоторые люди там ещё Гильберта застали). Модератор там Мартин Девис, ему 90 лет.
В книге Роджерса классическая теория вычислимости, созданная в основном трудами Клини. Сейчас больше интереса вызывает "реальная вычислимость", то есть вычислимость за приемлемое время с приемлемыми затратами. Решётками сводимости уже мало кто занимается.

[пианист]

Ясно, спасибо.

(Оффтоп)

george66 в сообщении #1395202 писал(а):

Я хожу на форум FOM https://cs.nyu.edu/pipermail/fom/
там интересно читать некрологи (некоторые люди там ещё Гильберта застали). Модератор там Мартин Девис, ему 90 лет.

Форум в форме e-mail листа? Прикольно..

george66 в сообщении #1395202 писал(а):

В книге Роджерса классическая теория вычислимости, созданная в основном трудами Клини. Сейчас больше интереса вызывает "реальная вычислимость", то есть вычислимость за приемлемое время с приемлемыми затратами.

Ну это кажется понятным, вроде как ближе к приложениям (т.е. к деньгам).

george66 в сообщении #1395202 писал(а):

Решётками сводимости уже мало кто занимается.

А тема вычислимость - сходимость как? Тоже уже забыта?

[george66]

пианист в сообщении #1395299 писал(а):

А тема вычислимость - сходимость как? Тоже уже забыта?

Если имеете в виду вычислимость как непрерывность, то эта тема активно изучается, но в другом оформлении - лямбда-исчисление и теория типов. Простейший пример у меня в учебнике ("большой пример" в начале главы про пределы), дальше модели Скотта (книга Барендрегта "Ламбда-исчисление").

[пианист]

Спасибо!

[пианист]

(симпатичное рассуждение)

george66 в сообщении #1395301 писал(а):

модели Скотта (книга Барендрегта "Ламбда-исчисление").

Очень симпатичное рассужденьице про то, что непрерывные в топологии Скотта функции монотонны.
Вот бы все так просто и ясно в математике выводилось ;)

[george66]

Скотт двигался от абстрактного к конкретному. Сначала занимался "бесточечной топологией". Это такой подход в общей топологии, где вместо топологического пространства берут решётку его открытых множеств и затем всё определяют на языке решёток (непрерывные функции, компактность и т.д.) Там где-то возникают эти "полные порядки". А затем он их приспособил к лямбда-исчислению. На самом деле для лямбда-исчисления достаточно требовать, чтобы каждая возрастающая последовательность имела супремум.
Какое впечатление от открывающихся новых областей? Это та же самая математика, где вычисляют гомотопии, или какая-то другая?

[пианист]

george66 в сообщении #1406783 писал(а):

Скотт двигался от абстрактного к конкретному. Сначала занимался "бесточечной топологией". Это такой подход в общей топологии, где вместо топологического пространства берут решётку его открытых множеств и затем всё определяют на языке решёток (непрерывные функции, компактность и т.д.) Там где-то возникают эти "полные порядки". А затем он их приспособил к лямбда-исчислению. На самом деле для лямбда-исчисления достаточно требовать, чтобы каждая возрастающая последовательность имела супремум.

А Ершов как пришел к своей конструкции? Вроде бы, она получше, чем у Скотта..
Интересно, сколько вообще таких моделей построено, две есть в книжечке Баренбрегта, еще модель Ершова..

george66 в сообщении #1406783 писал(а):

Какое впечатление от открывающихся новых областей? Это та же самая математика, где вычисляют гомотопии, или какая-то другая?

Вы имеете в виду, применение рассуждений как в классическом матанализе, с пределами и непрерывностью, к проблемам (дискретным) алгоритмической вычислимости? Не, я пока до этого уровня не добрался, хотя надеюсь ;)

[george66]

Скотт в середине 90-х (в возрасте 60 лет) придумал "эквилогические пространства". Категория обычных топологических пространств не декартово замкнута (произведение есть, а экспоненты в общем случае нет, на множестве всех непрерывных функций из пространства $A$ в пространство $B$ не всегда есть хорошая топология). Эквилогическое пространство - это топологическое пространство, на котором задано (произвольное) отношение эквивалентности. Морфизмы эквилогических пространств - это непрерывные отображения, сохраняющие также эквивалентность. Неожиданно оказывается, что эта категория декартово замкнута. Она содержит все обычные топологические пространства (если брать тривиальную эквивалентность - равенство).

[пианист]

(а вот это не очень)

Снова Барендрегт.
Вот чего я в упор не понимаю, так это почему автору потребовалось сходимость Скотта вводить через _открытые_ множества?
Условие "для любого открытого $O$ и любой направленности $X$ из $\sqcup X \in O$ следует $X \cap O \neq \varnothing$", выглядящее сущей дичью, если перейти к _замкнутым_ множествам станет совершенно понятным "любое замкнутое $M$ вместе со всякой под-направленностью $X$, $X \subset M$ содержит также и ее точную верхнюю грань $\sqcup X \in M$".
Причем вроде даже и в упражнениях этого нет..

[george66]

Вот какой собачий бред
Пишет этот Барендрегт!

[пианист]

Неохота создавать новую тему, так что напишу здесь.
Встретил в Роджерсе забавную задачку (задача 9.40), спешу поделиться:
доказать, что поддерево двоичного дерева бесконечно тогда и только тогда, когда оно содержит бесконечную ветвь (поддерево, если что, это когда вместе с каждым узлом имеется и вся ветвь от корня до этого узла).
Теорема о веере.