December 9th, 2008

moose, transparent

в театр (израильское)

ijon убедил меня пойти сегодня на "Гамлета" по-английски, в постановке TNT Theatre. Прочитайте его отзыв, и если он убедит и вас, присоединяйтесь к нам сегодня вечером в пол-девятого в Тель-Авиве, в здании театра "Гешер". Билеты пока еще есть (я только что заказал), телефон кассы см. по ссылке.
moose, transparent

хроника

moose, transparent

глупые мысли вслух

Есть ли корреляция между количеством орального секса и экономическими показателями страны?

Например, пусть X - процент людей, которые регулярно занимаются оральным сексом (из всего взрослого населения), Y - валовой внутренний продукт на душу населения. Есть ли корреляция между X и Y?
moose, transparent

оригинальное доказательство второй теоремы неполноты

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

Несколько лет назад Харви Фридман придумал новое, очень простое и красивое доказательство второй теоремы о неполноте Геделя. Напомню, что первая теорема о неполноте утверждает, что достаточно мощная формальная система T обязательно неполна, т.е. есть утверждения о натуральных числах, которые она не может ни доказать ни опровергнуть (и из этого следует сразу, что есть истинные утверждения, которые она не может доказать). Вторая теорема о неполноте утверждает, что достаточно мощная (в несколько другом смысле) T не может доказать собственную непротиворечивость, если она действительно непротиворечива (если система противоречива, то она может доказать вообще все, что угодно, включая собственную непротиворечивость).

Вот доказательство Фридмана (многие технические подробности я опускаю). Главная идея его похожа на доказательство нерешаемости теоремы об остановке машин Тьюринга, где, напоминаю, строится определенная машина, которой в качестве входа дается ее собственное описание. Несколько технических объяснений я вынес в сноски в конце записи.

Мы начинаем с формальной системы T. Мы предполагаем, что T достаточно мощна, чтобы уметь доказывать все истинные утверждения вида "машина [M] останавливается на входных данных X" [1].

Теперь мы описываем машину TM, которая делает следующую хитрую штуку: Collapse )