Алгоритмическое определение информации

[cema]

Ссылки из ljnauka на работы по алгоритмической теории информации:

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
http://dr-gng.dp.ua/files/gnoseo.htm

Если кто имеет чего сказать, с интересом послушаю.

Comments

[riftsh.livejournal.com]

а причем тут лженаука?

[cema.livejournal.com]

Вот потому-то я и вынул это дело из той дискуссии.

Там один участник сделал хитрый ход, как это принято в других местах (в Юзнете): перекинул мостик на то, что ему интересно, и вместо продолжения разговора стал говорить об этом, попутно, правда, обложив собеседников. Но здесь не Юзнет.

Мостик он перекинул таким образом: сделал заявление, что научная теория не продукт творчества учёного, а результат более-менее автоматического изучения накопленного экспериментального материала. (Кажется, это называется индукционным подходом.) Отсюда он перешёл к не-шенноновскому определению информации как наикратчайшей программе, описывающей набор данных. Вот это последнее мне достаточно интересно, но не относится к теме ljnauka. Первое же относится и обсуждается (или уже не обсуждается, посмотрим) в других веточках.

[(Anonymous)]

Ever heard of the Kolmogorov complexity of a source?

Thanks

[cema.livejournal.com]

Heard of it, yes. There is a grey area between math and computer science, which is either science or engineering or both, and it seems to me that Kolmogorov is on one side of it, while Chaitin is on the other one. I am more interested in the engineering aspects.

[pendelschwanz.livejournal.com]

Yes, I enjoy Chaitin.
Here is no "theory" at all, I find here a popular discussion about a well-known crisis in mathematics in the time of Goedel, and philosophical understanding of complicity. "Omega"-definition is a brilliant idea.
I cannot say it is very useful in "Computer Science", because a staring point of any computer problem is to estimate, is the problam solvable at all, and then to think about, how to restrict is. The modern problems of AI, like "translation", "text understanding", "image recognition" are generally solvable, but you often cannot find a "good quality solution" because of high complicity.
I do not see any "pseudo-science" here.

[cema.livejournal.com]

philosophical understanding of complicity

I certainly hope you meant "complexity". :-)

I do not see any "pseudo-science" here.

Neither do I, and this presents a problem of sorts. As soon as we see that something is definitely science, does it then leave the area of out interest and become offtopic?

[pendelschwanz.livejournal.com]

yeah, sorry, I mean "complexity" :-))
maybe this is offtopic. I cannot say that there is something false. It looks like an article in a holiday newspaper about science.

[riftsh.livejournal.com]

Интересная и местами очень квалифицированная дискуссия на эту тему случилась 10-12 лет назад в bionet.info-theory.

Вот несколько "входных точек", но внутри там все разветвлено и длилось несколько лет:

http://bionet.hgmp.mrc.ac.uk/hypermail/bio-info/bio-info.199502/0042.html
http://bionet.hgmp.mrc.ac.uk/hypermail/bio-info/bio-info.199502/0006.html
http://bionet.hgmp.mrc.ac.uk/hypermail/bio-info/bio-info.199503/0033.html
http://bionet.hgmp.mrc.ac.uk/hypermail/bio-info/bio-info.199411/0031.html
http://bionet.hgmp.mrc.ac.uk/hypermail/bio-info/bio-info.199209/0000.html

[cema.livejournal.com]

No need to be sorry. ;-)

I am not yet sure about the boundaries of ljnauka. Here, in my blog, nothing is off topic.

[cema.livejournal.com]

Любопытно. Спасибо!

Re: Thanks

[email-animal.livejournal.com]

Kolmogorov was not a Computer Scientist. He was a mathematician, one of the last ones who made significant contributions to a broad spectrum of subfields. And yes, Kolmogorov complexity is relevant here - it also calls for shortest representation of information.

[cema.livejournal.com]

Well, I understand that. When I said "Kolmogorov on one side", I meant "Kolmogorov's theory on one side", a shortcut. The approach is mathematically solid, like everything Kolmogorov (the man) did, but its practical use in computer programming has been limited.

THere are interesting philosophical (or logical, if one prefers that way) issues related to this approach, as well as Chaitin's, but I am not an expert in this.