tiphareth: гиперпростое множество

Настроение:	tired
Музыка:	Альтернативная Космонавтика -- 5.03.1995 Дом Ученых
Entry tags:	math, smeshnoe

гиперпростое множество
Среди прочего, Шень рассказал мне, что есть гиперпростое
множество. Это рекурсивно перечислимое множество A,
обладающее следующим свойством. Обозначим
n-й (в порядке возрастания) элемент дополнения к A
за b_n. Тогда последовательность {b_n} растет
быстрее любой вычислимой функции

Числа Грэма отдыхают, они растут ниибацца быстро,
но таки гораздо медленнее.

Еще есть максимальное множество,
это перечислимое множество A, такое, что любое
перечислимое множество, содержащее A, отличается
от A либо от натурального ряда на конечное множество.

Максимальные множества гиперпросты (это, кажется, ясно).
Также максимальные множества образуют орбиту относительно
группы вычислимых и обратимых подстановок натурального
ряда, сохраняющих перечислимые множества, с точностью
до конечных.

Конструктивная математика!

По степени живительной бредовости эта наука круче
ультрафильтров вдесятеро. Круче и неконструктивнее:
однако явных примеров максимального множества наука,
кажется, не ведает, несмотря на многочисленные
работы, им посвященные. При взгляде на подобное
сторонники финитизма должны биться в жутком
припадке и грызть на себе гениталии. Логически
рассуждая.

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

Привет

(Читать комментарии) - (Добавить комментарий)

Re: Раз уж зашёл, обозначу присутствие

kouzdra
2007-07-03 20:20 (ссылка)

А я вот не вполне понимаю, почему в случае действительного существования списка натуральных чисел в Haskell проблема нечётных совершенных чисел до сих пор числится открытой. Список-то допускает полный перебор!

Список бесконечный - и перебор соотвественно получится бесконечный. Что тут удивительного - даже многие конечные алгоритмы "всегда завершаются" сугубо теоретически - например я Вам на два счета заставлю любой из известных мне компиляторов java транслировать коротенькую программку до второго пришествия. Хотя там все разрешимо в теории.

А [0..] - это просто сокращение для кода вроде:
let nat n = n:nat (n+1) in nat 1
a:b - это список с головой a и хвостом b

По машинному представлению ничем не отличается от прочих списков.

Честно говоря, не очень понятно, как её "кодировать в машине". Было бы очень неплохо это уточнить

Ну там содержательный смысл ее в том, что объектами модели являются формулы теории вида "существует и единственное X, такое что ...". Точнее - классы эквивалентностей этих формул. А у Барвайса - обобщенная теорема, на случай теорий не со счетным, как у ZF множеством аксиом, а произвольным.

А вот это правильно! Теория о сношениях человека с дьяволом имела практические применения в избытке: ведьм реально жгли по всей Европе. Следовательно, каждое слово в «Malleus maleficarum» истинно.

Я хоть слово говорил об истинности?

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Раз уж зашёл, обозначу присутствие

http://users.livejournal.com/__gastrit/
2007-07-03 21:05 (ссылка)

Список, насколько моя знать, это объект, удовлетворяющий следующему индуктивному определению:

1) Пустой список есть список.
2) Если L - список, а t - объект, могущий быть элементом списка рассматриваемого вида, то результат "приписывания" t к L - тоже список.

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

А не в стороне - то, что Вы своё [0..] к пустому списку заведомо не редуцируете. И потому свойства Вашего [0..] ох как отличны от "списочных": для любого разрешимого свойства N натуральных чисел свойство «список содержит элемент со свойством N» тоже разрешимо, а вот свойство «нечто вроде [0..] содержит элемент со свойством N» - уже неразрешимо!

Об этом же я и писал в старых околоконструктивистских баталиях, на которые Вы тут ссылались: описать-то бесконечный класс объектов (средствами вроде Вашего [0..] или даже ещё более навороченными) можно - вот только считать, что с этим описанием потом можно работать как с авоськой картошки (допускать полный перебор, считать все вопросы разрешимыми), уже нельзя. А в ZF именно так и считают.

> Точнее - классы эквивалентностей этих формул.

Так "формулы" или "классы эквивалентности"? Вопрос не праздный: класс эквивалентности по неразрешимому отношению - это, вообще-то, "объект" совершенно неконструктивный и в машину не загоняемый.

> Я хоть слово говорил об истинности?

Я исхожу из того, что человек не будет защищать теорию, в истинности которой он не уверен. Вы ZF защищаете - со всеми отсюда вытекающими.

С уважением,
Гастрит

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Раз уж зашёл, обозначу присутствие

kouzdra
2007-07-03 21:22 (ссылка)

Суть этого определения в том, что любой "реальный" список можно эффективно "раздеть" до пустого

Если Вы внимательно посмотрите на свое определение - то убедитесь, что это неверно. Пример Вам только что был предъявлен.

эффективное на машине с одним объёмом памяти и быстродействием может быть неэффективно на другой

Там просто экспоненциальная сложность в некоторых местах вылезает. Так что - эффективно это не может быть ни на какой машине. С другой стороны - задача трансляции довольно многих практически используемых языков программирования вовсе алгоритмически неразрешима, Что не препятствует их использованию.

что с этим описанием потом можно работать как с авоськой картошки (допускать полный перебор, считать все вопросы разрешимыми), уже нельзя

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

Вопрос не праздный: класс эквивалентности по неразрешимому отношению - это, вообще-то, "объект" совершенно неконструктивный и в машину не загоняемый

Почему же не загоняемый - просто ответ не всегда будет получаться. В чем, самом по себе, криминала как я уже говорил, нет.

Я исхожу из того, что человек не будет защищать теорию, в истинности которой он не уверен. Вы ZF защищаете - со всеми отсюда вытекающими

Я знаю, что ZF безусловно является практически полезным инструментом, и склонен думать, что она скорее всего непротиворечива. И что даже если она окажется противоречива, проблему это создаст скорее технического рода. Как уже было с канторовской теорией. А что значит "ZF истинна" я не понимаю.

(Ответить) (Уровень выше)

(Читать комментарии) -