Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

энный мальчик и энная девочка

Мне нравятся -- да! мне нравятся математические статьи, в которых есть такие вот определения:

Определение: (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 может существовать подходящее решение проблемы сватовства, но это решение может оказаться невычислимым с помощью компьютера, слишком сложным для того, чтобы его даже в принципе можно было представить в качестве алгоритма.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments