Участник:Shersh/Теорема о рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(sketch)
 
(начата Колмогоровская сложность)
Строка 1: Строка 1:
 +
== Неразрешимость универсального языка ==
 
== Теорема Успенского-Райса ==
 
== Теорема Успенского-Райса ==
 
== Колмогоровская сложность ==
 
== Колмогоровская сложность ==
 +
{{Определение
 +
|id=defK.
 +
|definition='''Колмогоровской сложностью''' строки <tex> x </tex> называется функция <tex> K(x) </tex>, которая равна минимальной длине программы <tex> p : p(\varepsilon) = x </tex>.
 +
}}
 +
=== Пример ===
 +
Колмогоровская сложность программы, выводящей <tex> n </tex> нулей <tex> K(0^n) \leqslant \log{n} + c </tex>. Просто программа, в которой записано <tex> n </tex> нулей. Но можно записать и более короткую программу, например вот такую:
 +
<code>
 +
  <tex>p_n</tex>():
 +
    '''for''' i = 1..n
 +
      print 0
 +
</code>
 +
 +
{{Теорема
 +
|id=thK.
 +
|about=Невычислимость Колмогоровской сложности
 +
|statement=Колмогоровская сложность {{---}} невычислимая функция.
 +
|proof=
 +
 +
}}
 
== Busy beaver ==
 
== Busy beaver ==
 
== Аналог I теоремы Гёделя о неполноте ==
 
== Аналог I теоремы Гёделя о неполноте ==
 
== Аналог II теоремы Гёделя о неполноте ==
 
== Аналог II теоремы Гёделя о неполноте ==
 
== Теорема о неподвижной точке ==
 
== Теорема о неподвижной точке ==

Версия 15:57, 28 декабря 2013

Неразрешимость универсального языка

Теорема Успенского-Райса

Колмогоровская сложность

Определение:
Колмогоровской сложностью строки [math] x [/math] называется функция [math] K(x) [/math], которая равна минимальной длине программы [math] p : p(\varepsilon) = x [/math].

Пример

Колмогоровская сложность программы, выводящей [math] n [/math] нулей [math] K(0^n) \leqslant \log{n} + c [/math]. Просто программа, в которой записано [math] n [/math] нулей. Но можно записать и более короткую программу, например вот такую:

 [math]p_n[/math]():
   for i = 1..n
     print 0

Теорема (Невычислимость Колмогоровской сложности):
Колмогоровская сложность — невычислимая функция.

Busy beaver

Аналог I теоремы Гёделя о неполноте

Аналог II теоремы Гёделя о неполноте

Теорема о неподвижной точке