энный мальчик и энная девочка
Oct. 21st, 2002 12:38 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaМне нравятся -- да! мне нравятся математические статьи, в которых есть такие вот определения:
Определение: (1) Чётное натуральное число называется мальчиком; нечётное натуральное число называется девочкой. Мы используем B(n) вместо 2n и G(n) вместо 2n+1 и называем B(n) n-ным мальчиком, а G(n) - n-ной девочкой.
Я это всё перевожу на скорую руку с английского, так что прошу простить мне неизбежные корявости.
(2) Если R - бинарное отношение над N (множеством натуральных чисел), то вместо "<x,y>∈R" (т.е. числа x и y связаны отношением R) мы будем писать "x знаетR y" или просто "x знает y" если R фиксирована.
(3) Общество - это такая двоичная реляция R над N, что (i) R симметрична (т.е. если x знает y, то y знает x); (ii) Если x знает y, то они разного пола; (iii) Каждый человек знает только конечное число других людей; (iv) Каждый человек знает хотя бы одного другого человека. Если выполняются только первые три условия, а четвёртое необязательно, то R называется частичным обществом.
(4) Если R - частичное общество, то мы можем разделить всех людей, участвующих в R, на клубы знакомств следующим образом: два человека принадлежат к одному клубу, если есть "цепочка знакомств" конечной длины, соединяющая их между собой.
(5) Если R - частичное общество, а f -- взаимно однозначная функция , определённая на подмножестве всех чисел n таких, что B(n) участвует в R ("взаимно однозначная" значит, что если x и y - разные числа, то f(x) и f(y) тоже обязательно будут разными числами), то f называется решением проблемы сватовства на R, если для каждого n выполняется, что B(n) знает G(f(n)).
(6) Частичное общество R называется разрешимым, если для него существует функция, решающая проблему сватовства.
Это часть статьи, посвящённой анализу теоретико-рекурсивных аспектов теоремы Хола о сватовстве (Hall's matchmaking theorem, которую по-русски обычно называют "теоремой Холла о паросочетании").
Опубликована в Proceedings of London Mathematical Society за 1972-й год. О теореме Хола, наверное, стоит отдельно как-нибудь написать. Но если вкратце совсем, она устанавливает необходимые и достаточные условия для того, чтобы множество "мальчиков" можно было сосватать с множеством "девочек" так, чтобы попарно совмещать только мальчиков и девочек, "знающих" друг друга. Но теорема Хола доказывается неконструктивно; т.е. в ней доказывается, что есть возможность всех удачно сосватать, но сам результат -- кого с кем -- при этом не строится. А эта статья изучает возможность того, что для какого-то "общества" R может существовать подходящее решение проблемы сватовства, но это решение может оказаться невычислимым с помощью компьютера, слишком сложным для того, чтобы его даже в принципе можно было представить в качестве алгоритма.
Определение: (1) Чётное натуральное число называется мальчиком; нечётное натуральное число называется девочкой. Мы используем B(n) вместо 2n и G(n) вместо 2n+1 и называем B(n) n-ным мальчиком, а G(n) - n-ной девочкой.
Я это всё перевожу на скорую руку с английского, так что прошу простить мне неизбежные корявости.
(2) Если R - бинарное отношение над N (множеством натуральных чисел), то вместо "<x,y>∈R" (т.е. числа x и y связаны отношением R) мы будем писать "x знаетR y" или просто "x знает y" если R фиксирована.
(3) Общество - это такая двоичная реляция R над N, что (i) R симметрична (т.е. если x знает y, то y знает x); (ii) Если x знает y, то они разного пола; (iii) Каждый человек знает только конечное число других людей; (iv) Каждый человек знает хотя бы одного другого человека. Если выполняются только первые три условия, а четвёртое необязательно, то R называется частичным обществом.
(4) Если R - частичное общество, то мы можем разделить всех людей, участвующих в R, на клубы знакомств следующим образом: два человека принадлежат к одному клубу, если есть "цепочка знакомств" конечной длины, соединяющая их между собой.
(5) Если R - частичное общество, а f -- взаимно однозначная функция , определённая на подмножестве всех чисел n таких, что B(n) участвует в R ("взаимно однозначная" значит, что если x и y - разные числа, то f(x) и f(y) тоже обязательно будут разными числами), то f называется решением проблемы сватовства на R, если для каждого n выполняется, что B(n) знает G(f(n)).
(6) Частичное общество R называется разрешимым, если для него существует функция, решающая проблему сватовства.
Это часть статьи, посвящённой анализу теоретико-рекурсивных аспектов теоремы Хола о сватовстве (Hall's matchmaking theorem, которую по-русски обычно называют "теоремой Холла о паросочетании").
Опубликована в Proceedings of London Mathematical Society за 1972-й год. О теореме Хола, наверное, стоит отдельно как-нибудь написать. Но если вкратце совсем, она устанавливает необходимые и достаточные условия для того, чтобы множество "мальчиков" можно было сосватать с множеством "девочек" так, чтобы попарно совмещать только мальчиков и девочек, "знающих" друг друга. Но теорема Хола доказывается неконструктивно; т.е. в ней доказывается, что есть возможность всех удачно сосватать, но сам результат -- кого с кем -- при этом не строится. А эта статья изучает возможность того, что для какого-то "общества" R может существовать подходящее решение проблемы сватовства, но это решение может оказаться невычислимым с помощью компьютера, слишком сложным для того, чтобы его даже в принципе можно было представить в качестве алгоритма.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2002-10-21 11:34 am (UTC)Re:
Date: 2002-10-21 11:57 am (UTC)Короче, они non-recursive, uncomputable, etc. Причём могут находиться ещё выше, на нетривиальных уровнях рекурсивной иерархии.