Обсуждение:Теорема о рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
Ладно, по сути претензий вроде нет, но вот оформление...
+
: {{tick}} во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)
Пожалуйста, расставь знаки препинания в концах предложений (ты с завидной регулярностью теряешь там точки), запятые и замени минусы на тире.  
+
: {{tick}} дать ссылки на английские источники и термины
Русский язык местами оставляет желать лучшего, но вот первое предложение доказательства второй формулировки меня убило.
+
: {{tick}} у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.
"Так как <tex>U</tex> - универсальная, то найдется для любой вычислимой всюду определенной <tex>n</tex> найдется такая вычислимая всюду определенная <tex>num</tex>, что <tex>n=U_{num(n)}</tex>". Сам-то понял, что сказал? [[Участник:Berezhkovskaya|Алёна Бережковская]]
+
: {{tick}} следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
 +
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:59, 5 декабря 2012 (GST)
  
Просто война. [[Участник:Vincent|Владислав Кононов]]
+
 
 +
Добавить примеры простых доказательств с использованием теоремы о рекурсии:
 +
: {{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 или из последней лекции Станкевича)