Обсуждение:Теорема о рекурсии — различия между версиями
| Строка 2: | Строка 2: | ||
: {{tick}} дать ссылки на английские источники и термины | : {{tick}} дать ссылки на английские источники и термины | ||
: {{tick}} у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. | : {{tick}} у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. | ||
| − | : {{tick}} следующая теорема о рекурсии во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить | + | : {{tick}} следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. |
| − | |||
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:59, 5 декабря 2012 (GST) | --[[Участник: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 или из последней лекции Станкевича)
