Logical operations and Kolmogorov complexityстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 31 октября 2014 г.
Аннотация:Conditional Kolmogorov complexity K(x|y) can be understood as the complexity of the problem “Y→X”, where X is the problem “construct x” and Y is the problem “construct y”. Other logical operations (∧,∨,↔) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability. This leads to interesting problems in algorithmic information theory. Some of these questions are discussed.