энный мальчик и энная девочка
Oct. 21st, 2002 12:38 amМне нравятся -- да! мне нравятся математические статьи, в которых есть такие вот определения:
Определение: (1) Чётное натуральное число называется мальчиком; нечётное натуральное число называется девочкой. Мы используем B(n) вместо 2n и G(n) вместо 2n+1 и называем B(n) n-ным мальчиком, а G(n) - n-ной девочкой.
( и дальше... )
Это часть статьи, посвящённой анализу теоретико-рекурсивных аспектов теоремы Хола о сватовстве (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-ной девочкой.
( и дальше... )
Это часть статьи, посвящённой анализу теоретико-рекурсивных аспектов теоремы Хола о сватовстве (Hall's matchmaking theorem, которую по-русски обычно называют "теоремой Холла о паросочетании").
Опубликована в Proceedings of London Mathematical Society за 1972-й год. О теореме Хола, наверное, стоит отдельно как-нибудь написать. Но если вкратце совсем, она устанавливает необходимые и достаточные условия для того, чтобы множество "мальчиков" можно было сосватать с множеством "девочек" так, чтобы попарно совмещать только мальчиков и девочек, "знающих" друг друга. Но теорема Хола доказывается неконструктивно; т.е. в ней доказывается, что есть возможность всех удачно сосватать, но сам результат -- кого с кем -- при этом не строится. А эта статья изучает возможность того, что для какого-то "общества" R может существовать подходящее решение проблемы сватовства, но это решение может оказаться невычислимым с помощью компьютера, слишком сложным для того, чтобы его даже в принципе можно было представить в качестве алгоритма.