невозрастание сложности

[Dmitry Grebeniuk]

hi, Ruvim

Мне кажется, не существует такой МТ, чтобы K(S[i+1])-K(S[i]) было
бы больше, чем K("применить шаг МТ") (конечно же, предполагаем, что
алгоритм у нас постоянен и известен). Грубо говоря, "информация
сама по себе не возникает".

RP> А чем ограничена величина K("применить шаг МТ") ?
RP> Ведь, шаг MT может быть разным по "емкости", в зависимости от входных
RP> данных.

Она не ограничена, она постоянна. Она равна сложности строки русского языка
"применить шаг МТ", записанной в системе наших любимых терминов.

RP> Давай определим, какое минимальное значение принимает фукнция K(s)
..
RP> и эта сложность K(s) >= log( |s| ) + c.

RP> Сложность строки нулевой длины по этой формуле не определена ;)

Кстати вот это неправильно, так как сложность нулевой строки -- вполне
определенное число. Судя по всему, формула должна быть таки переписана в виде
K(s) >= log (1 + |s|) + c
, однако я не совсем уверен в этом вопросе.

RP> Учитывая, что функция K() невычислима, получается, что
RP> ее неопределенность (интервал, в котором лежит ее значение),
RP> в общем случае, увеличивается с увеличением длины строки.
RP> Hа графике это примерно область вниз от прямой y=x
RP> и вверх от кривой y=log(x), при x >= 1 (x целое - длина строки).

RP> Буде понятно -- продолжение следует.

Всё прекрасно понятно, жду продолжения.

RP> Интуитивно: похожие запрещающие законы должны быть и для ИИ.

Абсолютно согласен. Только за одним исключением: мы пока рассматриваем
чистую теорию, голую детерминированную МТ без обмена с внешним миром. И теории
будут складываться, и всё будет в полном шоколаде, таксзть, но как только
добавим внешнюю информацию -- всё, каюк.

bye

[Ruvim Pinka]

Вечер добрый!

Dmitry Grebeniuk, wrote on 02.03.2006 10:16

Post by Dmitry Grebeniuk
RP> Давай определим, какое минимальное значение принимает фукнция K(s)
...
RP> и эта сложность K(s) >= log( |s| ) + c.
RP> Сложность строки нулевой длины по этой формуле не определена ;)

Мы рассматриваем рекурентную последовательность
систем S[i]. Каждая такая система включает
как состояние ленты так и саму МТ: S[i] = p[i].F ,
где p[i] -- состояние ленты;
F -- вычислимая функция (МТ), представленная в виде строки;
знак '.' -- конкатенация строк.
Рекурентное соотношение: S[i+1] = F(p[i]).F
S0 задает начальную систему (p[0] и F).

Очевидно, S никогда не будет пустой, т.к. |F| > 0.
Поэтому, какое значение принимает функция K()
на пустой строке -- не имеет значения в нашем рассмотрении.

Post by Dmitry Grebeniuk
Кстати вот это неправильно, так как сложность нулевой строки -- вполне
определенное число. Судя по всему, формула должна быть таки переписана в виде
K(s) >= log (1 + |s|) + c
, однако я не совсем уверен в этом вопросе.

K(s) -- длина наименьшего из описаний, формально --
длина наименьшей из программ (машин Т.), выводящих пустую строку.
Какую длину может иметь программа, которая ничего не выводит?
По любому, может случиться, что длина этой программы < log (1 + |s|) + c = с ,
где c -- задает длину операции, выводящей строку как константу.

Post by Dmitry Grebeniuk

Мне кажется, не существует такой МТ, чтобы K(S[i+1])-K(S[i]) было
бы больше, чем K("применить шаг МТ") (конечно же, предполагаем, что
алгоритм у нас постоянен и известен). Грубо говоря, "информация
сама по себе не возникает".

RP> А чем ограничена величина K("применить шаг МТ") ?
RP> Ведь, шаг MT может быть разным по "емкости", в зависимости от входных
RP> данных.
Она не ограничена, она постоянна. Она равна сложности строки русского языка
"применить шаг МТ", записанной в системе наших любимых терминов.

Если известна хотя бы какая программа A, выводящая строку s,
можно точно утверждать, что сложность K(s) <= |A|

Наша последовательность систем S0, S[1], S[2], ... рекурента.
Например, нам известна такая программа, выводящая S[1]:
Взять из константы S0 p0 и F, получить p[1] применив F к p0, вывести S[1] как p[1].F.
Для S[n] есть программа:
Положить S равным константе S0
Для i от 1 до n
взять из S p и F, получить p2 применив F к p, положить S равным p2.F
Повторить.
Затем вывести S

Длина приведенной программы зависит только от S0 и n,
и увеличивается как log(n) с ростом n.

Таким образом, можно утверждать, что сложность n-ой из систем
не превышает длину приведенной программы, выводящей S[n].
Т.е. K( S[n] ) <= |S0| + log(n) + c (a)

Но, очевидно, есть более короткие программы, выводящие S[n].
Например, вместо константы S0 можно хранить минимальную программу,
которая выводить S0. Какова длина этой программы?
По определению, длина этой программы есть сложность S0 -- K(S0).
Делая подстановку в (a) получаем

K( S[n] ) <= K(S0) + log(n) + c

Если номер i в последовательности S[i] назвать 'временем',
то получается такой вывод: сложность системы (МТ + состояние ленты)
в процессе функционирования не может расти быстрей, чем логарифм от времени,
и определяется начальной точкой S0.
Точнее: эта рост верхнего ограничения сложности.

Очевидно, приращение на каждом шаге этой последовательности K( S[i] )
не постоянно, а падает по ~гиперболической зависимости.

Да, в приведенном доказательстве действительно есть некие допущения,
но они относятся к точности формулировок и не влияют на результат (имхо ;)

Post by Dmitry Grebeniuk
RP> Интуитивно: похожие запрещающие законы должны быть и для ИИ.
Абсолютно согласен. Только за одним исключением: мы пока рассматриваем
чистую теорию, голую детерминированную МТ без обмена с внешним миром. И теории
будут складываться, и всё будет в полном шоколаде, таксзть, но как только
добавим внешнюю информацию -- всё, каюк.

Если бы каюк был очевиден, у кого был бы интерес его выводить? ;)
Начальное состояние S0 это ведь и есть внешняя информация.


--
Ruvim

[Ruvim Pinka]

Dmitry Grebeniuk, wrote on 02.03.2006 10:16

Мне кажется, не существует такой МТ, чтобы K(S[i+1])-K(S[i]) было
бы больше, чем K("применить шаг МТ") (конечно же, предполагаем, что
алгоритм у нас постоянен и известен).

да, правильно. Формально:

S[i+1] = MetaF( S[i] )
K( S[i+1] ) <= K( S[i] ) + K(MetaF) + c
K( S[i+1] ) <= K( S[i] ) + c1
dK[i,i+1] <= c1 -- приращения за одни шаг не может быть выше некоторой константы.

Но, также действует и ограничение:
dK[i,i+1] <= ( K(S0) + log(i+1) + c2 ) - K( S[i] )

Поэтому, как только K( S[i] ) превосходит K(S0),
ограничение на приращение очень ужесточается.

Скажу более. Не существует такого S0,
которое обеспечит хотя бы несколько шагов подряд
на ~максимальном К().
Не существует алгоритма, который одну очень сложную
точку (близкую к величине K(S0) + log(i) + c )
первел бы в другую очень сложную.
Любая точка после сложной -- будет простой.

--
Ruvim