Обсуждение:Колмогоровская сложность
Планирую в течении недели перевести статью с английской вики. Yrogirg 19:49, 18 марта 2008 (UTC) Явно скопировано. 139.18.181.124 15:32, 18 января 2009 (UTC)Ya
Соломонофф vs Соломонов[править код]
почитайте историю, там обворожительные истории просто, По мнению KleverI транслитерировать фамилию Solomonoff как Соломонов нельзя, а склонять можно.
109.22.53.217 00:14, 30 октября 2013 (UTC)
- Транслитерация фамилии «Solomonoff» как Соломонофф мотивируется, например, вот этим [1]. — KleverI 15:44, 30 октября 2013 (UTC)
Ошибка?[править код]
«Тем не менее, как легко понять, утверждение K(s)\geqslant L будет истинным для бесконечного множества строк, а точнее, для всех строк, за исключением конечного их числа.»
Мне кажется, нужно удалить концовку «, а точнее, для всех строк, за исключением конечного их числа.» И вот почему: построим БЕСКОНЕЧНОЕ множество строк, для которых K(s)>=L ложно. Действительно, пусть S_n — строка из n нулей. Программа for(int i=0;i<десятичное представление n;i++){printf("0");} имеет длину L = C + log_10 n символов, где C — константа. Имеем K(S_n) <= L < n при всех n >= n0, где n0 достаточно велико. Множество {S_{n0}, S_{n0+1}, S_{n0+2}, ...} обладает заявленным свойством. --yuramanouski
Ошибка 2 ?[править код]
В доказательстве невычислимости не учитывается размер кода подпрограммы KolmogorovComplexity(s) , чей размер неизвестен и, собственно, невозможность создания которой и доказывается в этом абзаце. Противоречие. С помощью функции мы доказываем невозможность создания функции.