Обсуждение:Теорема о рекурсии

Материал из Викиконспекты
Версия от 00:06, 13 декабря 2012; Dgerasimov (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)
дать ссылки на английские источники и термины
у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.
следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.

--Дмитрий Герасимов 11:59, 5 декабря 2012 (GST)


Добавить примеры простых доказательств с использованием теоремы о рекурсии:

Теоремы Успенского-Райса
Невычислимости Колмогоровской сложности
Невычислимости Busy beaver
аналога I теоремы Геделя о неполноте
аналога II теоремы Геделя о неполноте
теоремы о неподвижной точке (простое док-во, есть в Sipser'e или из последней лекции Станкевича)