Обсуждение:Теорема о рекурсии — различия между версиями
Vincent (обсуждение | вклад) |
|||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | : {{tick}} во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские) | |
| − | + | : {{tick}} дать ссылки на английские источники и термины | |
| − | + | : {{tick}} у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. | |
| − | + | : {{tick}} следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. | |
| + | --[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:59, 5 декабря 2012 (GST) | ||
| − | + | ||
| + | Добавить примеры простых доказательств с использованием теоремы о рекурсии: | ||
| + | : {{tick}} Теоремы Успенского-Райса | ||
| + | : {{tick}} Невычислимости Колмогоровской сложности | ||
| + | : {{tick}} Невычислимости Busy beaver | ||
| + | : {{tick}} аналога I теоремы Геделя о неполноте | ||
| + | : {{tick}} аналога II теоремы Геделя о неполноте | ||
| + | : {{tick}} теоремы о неподвижной точке (простое док-во, есть в Sipser'e или из последней лекции Станкевича) | ||
Текущая версия на 00:06, 13 декабря 2012
- ☐ во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)
- ☐ дать ссылки на английские источники и термины
- ☐ у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.
- ☐ следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
--Дмитрий Герасимов 11:59, 5 декабря 2012 (GST)
Добавить примеры простых доказательств с использованием теоремы о рекурсии:
- ☐ Теоремы Успенского-Райса
- ☐ Невычислимости Колмогоровской сложности
- ☐ Невычислимости Busy beaver
- ☐ аналога I теоремы Геделя о неполноте
- ☐ аналога II теоремы Геделя о неполноте
- ☐ теоремы о неподвижной точке (простое док-во, есть в Sipser'e или из последней лекции Станкевича)
