диспуты

Поделиться статьей в социальных сетях:

в избранное

Информация

Ссылка на оригинал: Stanford Encyclopedia of Philosophy

Впервые опубликовано 26 октября 2012 года; содержательно переработано 14 декабря 2018 года.

Философия информации занимается философским анализом понятия информации как с исторической, так и с систематической точек зрения. С появлением эмпирической теории познания в философии раннего Нового времени, с развитием различных математических теорий информации в XX веке, а также с развитием информационных технологий концепция «информации» заняла центральное место в лоне естественных наук и общественной жизни. Помимо прочего, этот интерес привел к появлению отдельной ветви философии, которая анализирует информацию во всех ее проявлениях (Adriaans and van Benthem 2008a, b; Lenski 2010; Floridi 2002, 2011). Информация стала центральной категорией как в естественных, так и в гуманитарных науках, и размышления на ее счет влияют на широкий круг философских дисциплин: от логики (Dretske 1981; van Benthem en van Rooij 2003; van Benthem 2006) и эпистемологии (Simondon 1989) до этики (Floridi 1999), от эстетики (Schmidhuber 1997a; Adriaans 2008) до онтологии (Zuse 1969; Wheeler 1990; Schmidhuber 1997b; Wolfram 2002; Hutter 2010).

Не существует единого мнения о точной природе философии информации как области. Некоторые авторы предлагали более или менее последовательные философии информации как попытки переосмыслить философию с новых точек зрения: с таких, например, как квантовая физика (Mugur-Schächter 2002), логика (Brenner 2008), семантическая информация (Floridi 2011; Adams & de Moraes 2016), коммуникация и системы сообщений (Capurro & Holgate 2011) и метафилософия (Wu 2010, 2016). Другие авторы (Adriaans & van Benthem 2008a; Lenski 2010) видят в ней, скорее, техническую дисциплину с глубокими корнями в истории философии, а также следствиями, важными для других различных дисциплин, таких как методология, эпистемология и этика. Какова бы ни была интерпретация природы философии информации, по-видимому, она предполагает амбициозную исследовательскую программу, состоящую из множества подпроектов. Последние варьируются от переосмысления истории философии в контексте современных теорий информации до глубинного анализа роли информации в естественных и гуманитарных науках, а также в обществе в целом.

В настоящее время термин «информация» в разговорной речи используется преимущественно как абстрактное массовое существительное и обозначает любое количество данных, кода или текста, которые хранятся, отправляются, принимаются и которые обрабатываются на любом носителе. Подробная история как самого термина «информация», так и различных связанных с ним понятий, является сложной, и по большей части ее еще предстоит написать (Seiffert 1968; Schnelle 1976; Capurro 1978, 2009; Capurro and Hjørland 2003). Точное значение термина «информация» варьируется в разных философских традициях, а его разговорное использование варьируется в зависимости от географии и от прагматики контекстов. Хотя анализ того, что понимается под «информацией», велся в русле западной философии с самого ее начала, эксплицитный анализ информации как философской концепции относительно недавний и датируется второй половиной ХХ века.

Существует сеть взаимосвязанных концепций информации, корни которых уходят в такие дисциплины, как физика, математика, логика, биология, экономика и эпистемология. Все эти локальные понятия группируются вокруг двух основных свойств:

Информация экстенсивна. Центральным для понимания этой идеи является понятие аддитивности: сочетание двух независимых наборов данных с равным количеством информации содержит вдвое больше информации, чем каждый из наборов данных по отдельности. Понятие экстенсивности естественным образом возникает в наших взаимодействиях с окружающим миром, когда мы подсчитываем и измеряем объекты и структуры. Основные концепции более абстрактных математических сущностей — таких, как множества, мультимножества и последовательности, — исторически были разработаны ранее, на основе структурных правил манипулирования символами (Schmandt-Besserat 1992). Математическая формализация экстенсивности при помощи логарифмической функции произошла в контексте исследований в области термодинамики в XIX веке (Больцман 1984) и в начале XX века (Гиббс 1950). При кодировании посредством более совершенных систем многомерных чисел (комплексных чисел, кватернионов, октонионов) концепция экстенсивности обобщается до более утонченных понятий аддитивности, которые перестают соответствовать нашей повседневной интуиции. Тем не менее они играют важную роль в последних разработках в теории информации, основанных на квантовой физике (фон Нейман 1964; Redei & Stöltzner 2001).

Информация уменьшает неопределенность. Количество получаемой нами информации линейно растет с величиной, на которую она уменьшает нашу неопределенность — вплоть до того момента, когда мы получили всю возможную информацию и количество неопределенности стало равно нулю. Связь между неопределенностью и информацией, вероятно, была впервые сформулирована философами-эмпириками (Локк 1985; Юм 1966). Юм явно отмечает, что выбор из большего числа возможностей дает больше информации. Это наблюдение достигло своей канонической математической формулировки в функции, предложенной Хартли (1959): она определяет объем получаемой нами информации, когда мы выбираем элемент из конечного множества. Единственной математической функцией, объединяющей эти две интуиции об экстенсивности и вероятности, является та, которая определяет информацию в терминах отрицательного логарифма вероятности: $I(A)= -\log P(A)$ (Shannon 1948; Shannon & Weaver 1949).

Впрочем, элегантность этой формулы не защищает нас от концептуальных проблем, которые она в себе таит. В ХХ веке были предложены различные варианты того, как формализовать понятие информации:

Качественные теории информации

1. Семантическая информация: Бар-Хиллел и Карнап разработали теорию семантической информации (Bar-Hillel and Carnap 1953). Флориди (Floridi 2002, 2003, 2011) определяет семантическую информацию как правильно сформированные, значимые и истинные данные. Формальные определения информации на основе энтропии (Фишер, Шеннон, квантовая, колмогоровская) работают на более общем уровне и необязательно измеряют информацию в значимых и достоверных наборах данных, — хотя можно отстаивать мнение, что для обеспечения измеримости данные должны быть правильно сформированы (см. обсуждение в разделе 6.6, посвященном логике и семантической информации). Семантическая информация по сути близка нашему повседневному наивному представлению об информации как о чем-то, что передается истинными утверждениями о мире.
2. Информация как состояние агента: формальная логическая трактовка таких понятий, как знание и вера, была инициирована Хинтиккой (Hintikka 1962, 1973). Дретцке (Dretske 1981) и ван Бентем вместе с ван Руджи (van Benthem & van Rooij 2003) изучали эти понятия в контексте теории информации (см. van Rooij 2004 о вопросах и ответах или Parikh & Ramanujam 2003 о неспециализированных сообщениях). Также, по-видимому, Данн имеет в виду схожие соображения, когда определяет информацию как «то, что остается от знания, когда отнимают веру, оправдание и истину» (Dunn 2001: 423; Dunn 2008). Виго предложил структурно-чувствительную теорию информации, основанную на сложности в овладении агентом тем или иным понятием (Vigo 2011, 2012).

Количественные теории информации

1. Функция Найквиста: Найквист (Nyquist 1924), вероятно, был первым, кто выразил количество «сведений», которое может быть передано при определенной скорости линии телеграфных систем, посредством логарифмической функции: $W= k \log m$, где $W$ — скорость передачи, $k$ является константой, а $m$ — это различные уровни напряжения, из которых мы выбираем.
2. Информация по Фишеру: количество информации, которую наблюдаемая случайная переменная $X$ несет о неизвестном параметре $θ$, от которого зависит вероятность сакмой $X$ (Fisher, 1925).
3. Функция Хартли: (Хартли 1959, Rényi 1961, Vigo 2012). Когда мы выбираем элемент из конечного множества $S$ при равномерном распределении, количество получаемой нами информации равняется логарифму мощности данного множества.
4. Информация по Шеннону: энтропия, $H$, дискретной случайной переменной $X$ является мерой количества неопределенности, связанной со значением $X$ (Shannon 1948; Shannon & Weaver, 1949).
5. Колмогоровская сложность: информацией, заключенной в двоичной строке $x$, является длина самой короткой программы p, способной произвести $x$ на исходной универсальной машине Тьюринга $U$ (Turing 1937; Solomonoff 1960, 1964a,b, 1997; Колмогоров 1965; Chaitin 1969, 1987).
6. Меры энтропии в физике: хотя они не во всех случаях строго соответствуют мерам информации, различные определенные в физике понятия энтропии тесно связаны с соответствующими понятиями информации. Мы упоминаем энтропию Больцмана (Больцман 1984), тесно связанную с функцией Хартли (Хартли 1959), а также энтропию Гиббса (Гиббс 1950), формально эквивалентную энтропии Шеннона и различным обобщениям, — таким, как энтропия Цаллиса (Tsallis 1988) и энтропия Реньи (Rényi, 1961).

До недавнего времени возможность объединения этих теорий скорее ставилась под сомнение (Adriaans & van Benthem 2008a), но после двух десятилетий исследований перспективы объединения выглядят более реалистичными.

Контуры единой концепции информации просматриваются в следующих направлениях:

• Философия информации — это подразделение философии, тесно связанная с философиями логики и математики. Философия семантической информации (Floridi 2011, D’Alfonso 2012, Adams & de Moraes, 2016), в свою очередь, является подразделением философии информации (см. «карту информации» в статье Семантические концепции информации).С этой точки зрения философия информации питает интерес к изучению своего предмета на самом общем уровне: данные вообще, правильно сформированные данные, данные об окружающей среде и т.д. Философия семантической информации добавляет измерения значения и истинности. Существует возможность интерпретировать количественные теории информации в рамках философии семантической информации (см. более детальное обсуждение в разделе 6.6).
• Различные количественные понятия информации связаны с различными нарративами (подсчет, получение сообщений, сбор информации, вычисления), укорененными в одной и той же базовой математической структуре. Многие проблемы философии информации центрированы вокруг сопряженных проблем в философии математики. Были изучены преобразования и редукции между различными формальными моделями (Cover & Thomas 2006; Grünwald & Vitányi 2008; Bais & Farmer 2008). Возникающая ситуация, судя по всему, мало чем отличается от сложившейся вокруг концепции энергии: существуют различные формальные подтеории касательно энергии (кинетическая, потенциальная, электрическая, химическая, ядерная) с четко определенными преобразованиями между ними. Кроме того, термин «энергия» свободно используется в разговорной речи.
  
• Основанные на агентности понятия информации естественным образом возникают, когда наш интерес расширяется от простого измерения и манипулирования символами до более сложной парадигмы агента со знаниями, убеждениями, намерениями и свободой выбора. Такие агентностные понятия связаны с развертыванием других концепций информации.

Возникновение согласованной теории количественного измерения информации в ХХ в. тесно связано с развитием теории вычислений. Центральное место в контексте последней занимают понятия Универсальности, Эквивалентность по Тьюрингу и Инвариантности: поскольку концепция системы Тьюринга определяет понятие универсального программируемого компьютера, по-видимому, все универсальные модели вычислений имеют одинаковую мощность. Сказанное подразумевает, что любые возможные меры информации, определяемые для универсальных моделей вычислений (рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.), асимптотически инвариантны. Это дает представление о единой теории информации, которая может оказаться господствующей исследовательской программой в ближайшие годы.

Информация в разговорной речи

Отсутствие точности и универсальная полезность термина «информация» идут рука об руку. В нашем обществе, где мы исследуем реальность с помощью приборов и установок все возрастающей сложности (телескопы, циклотроны) и общаемся с помощью все более развитых средств массовой информации (газеты, радио, телевидение, SMS, Интернет), полезно иметь абстрактное массовое существительное для «материала», который создается инструментами и который «течет» через эти средства. Исторически это общее значение появилось довольно поздно и, по всей видимости, связано с ростом средств массовой информации и спецслужб (Devlin & Rosenberg 2008; Adriaans and van Benthem 2008b).

В современной разговорной речи термин «информация» используется различными способами, во многих из которых он нечетко определен, а другие определения оказываются противоречивыми. Например, большинство людей рассмотрят следующий вывод как prima facie допустимый:

У тех же людей, вероятно, не возникнет проблем с утверждением «секретные службы иногда распространяют ложную информацию» или с предложением «информация, предоставленная свидетелями аварии, была расплывчатой ​​и противоречивой». Первое утверждение подразумевает, что информация обязательно является правдой, в то время как другие утверждения допускают возможность того, что информация является ложной, противоречивой и расплывчатой.

Судя по всему, в повседневном общении нет прагматического давления, принуждавшего бы стороны коммуникации сходиться к более точному определению понятия информации.

История термина и понятия информации

До второй половины XX века практически ни один современный философ не считал «информацию» важной философской концепцией. Термин не имеет словарной формы в известной энциклопедии Эдвардса (Edwards 1967) и не упоминается у Виндельбанда (Windelband 1903). В этом контексте интерес к «философии информации» возник недавно. И все же, оглядываясь назад из перспективы истории идей, мы понимаем, что размышления о понятии «информация» были преобладающей темой в истории философии. Реконструкция этой истории актуальна для изучения информации.

Проблема с любым подходом в жанре «истории идей» заключается в подтверждении основополагающего предположения, что изучаемая концепция действительно имеет преемственность в истории философии. В случае исторического анализа информации можно задаться вопросом, имеет ли понятие informatio, обсуждавшееся Августином, какое-либо отношение к информации Шеннона, кроме сходства терминов. В то же время можно задаться вопросом, является ли «исторический, простой метод»‹1› Локка важным вкладом в появление современной концепции информации — при том, что в своих работах Локк почти не использует термин «информация» в узкоспециальном смысле. Как показано ниже, вокруг понятия информации существует конгломерат идей, которые развивались с древности до недавних времен, однако необходимо дальнейшее изучение истории понятия информации.

Классическая философия

В классической философии «информация» была узкоспециальным понятием, связанным с теорией познания и онтологией, которая возникла из теории форм Платона (427–347 гг. до н.э.), развитой в ряде его диалогов («Федон», «Федр», «Пир», «Тимей», «Государство»). Различные несовершенные индивидуальные лошади в физическом мире могут быть идентифицированы как лошади потому, что они причастны статической, вневременной и внепространственной идее «лошадиности» в мире идей или форм. Когда более поздние авторы, — такие как Цицерон (106–43 гг. до н.э.) и Августин (354–430 гг. н.э.) — обсуждали понятия Платона на латыни, они использовали термины informare и informatio для перевода таких узкоспециальных греческих терминов, как eidos (сущность), idea (идея), typos (тип), morphе (форма) и prolepsis (представление). Корень «форма» все еще узнаваем в слове ин-форм-ация (Capurro and Hjørland 2003). Теория форм Платона была попыткой сформулировать решение различных философских проблем: она занимает промежуточное положение между статической (Парменид, ок. 450 г. до н.э.) и динамической (Гераклит, ок. 535–475 гг. до н.э.) онтологическими концепциями реальности и предлагает модель для изучения теории человеческого знания. Согласно Теофрасту (371–287 гг. до н.э.), аналогия с восковой табличкой восходит к Демокриту (около 460–380 / 370 г. до н.э.) («О чувствах» 50). В «Теэтете» (191c, d) Платон сравнивает функционирование нашей памяти с восковой табличкой, на которой запечатлены наши восприятия и мысли — так же как перстень-печатка оставляет отпечаток на воске. Обратите внимание, что метафора отпечатывания символов на воске по сути пространственная (экстенсивная) и не может быть легко согласована с внепространственной интерпретацией мира идей, развиваемой Платоном.

Можно получить представление о роли, которую играет понятие «форма» в классической методологии, если принять во внимание учение Аристотеля (384–322 гг. до н.э.) о четырех причинах. В аритотелианской методологии понимание объекта подразумевает понимание четырех различных его аспектов:

1. Материальная причина: Причиной называется то содержимое вещи, из чего она возникает; например, медь — причина изваяния и серебро — причина чаши, а также их роды суть причины;
2. Формальная причина: форма, или первообраз, а это есть определение сути бытия вещи, а также роды формы, или первообраза (например, для октавы — отношение двух к одному и число вообще), и составные части определения;
3. Действующая причина: то, откуда берет первое свое начало изменение или переход в состояние покоя; например, советчик есть причина, и отец — причина ребенка, и вообще производящее есть причина производимого, и изменяющее — причина изменяющегося;
4. Целевая причина: цель, т.е. то, ради чего нечто делается; например, цель гулянья — здоровье. В самом деле, почему человек гуляет? Чтобы быть здоровым, говорим мы. И, сказав так, мы считаем, что указали причину. (Аристотель 1976, «Метафизика», 1013a)

Тот факт, что в качестве примера приводится соотношение 2:1, также иллюстрирует глубокую связь между понятием форм и представлением о том, что мир управляется математическими принципами. Находясь под влиянием более старой пифагорейской традиции (Пифагор 572–500 гг. до н.э.), Платон полагал, что «все возникающее и происходящее в мире» можно измерить с помощью чисел («Политик», 285а). В ряде случаев Аристотель упоминает тот факт, что Платон связывал идеи с числами (Vogel 1974: 139). Хотя формальные математические теории информации появились только в ХХ веке, — и нужно быть осторожным с интерпретациями греческого понятия числа в сколько-нибудь современном смысле, — идея, что информация по существу была математическим понятием, восходит к классической философии. Форма объекта понималась как структура или паттерн, который можно описать при помощи чисел. Понятая таким образом форма имела как онтологический, так и эпистемологический аспект: она объясняет саму суть вещи так же хорошо, как и ее постижимость. Соответственно, понятие информации с самого начала философских размышлений уже было связано с эпистемологией, онтологией и математикой.

Две фундаментальные проблемы, которые не объясняются классической теорией идей или форм, таковы: 1) фактический акт познания объекта (т.е., если я вижу лошадь, каким образом идея лошади активируется в моем уме) и 2) процесс мышления как манипулирование идеями. Аристотель рассматривает эти вопросы в книге «О душе», привлекая аналогию «перстень-печатка-отпечаток-в-воске»:

В приведенных отрывках много влиятельных идей, а сами они могут быть задним числом прочитаны как программные для философии информации: процесс informatio может восприниматься как запечатление знаков на чистой восковой табличке (tabula rasa), а мышление может быть проанализировано как манипулирование символами.

Средневековая философия

На протяжении всего Средневековья размышлениями о концепции informatio поочередно были заняты многие мыслители. Показательным примером аристотелианского влияния является пассаж Августина в «О Троице», кн. XI. В нем он анализирует зрение как аналогию понимания Троицы. Есть три аспекта: телесная форма во внешнем мире, informatio посредством чувства зрения и форма, возникающая уже в уме. Для описания этого процесса информации Августин использует образ перстня-печатки, оставляющего отпечаток на воске (De Trinitate, XI Cap 2 par 3). Капурро (Capurro 2009) отмечает, что этот анализ можно интерпретировать как раннюю версию технической концепции «отправки сообщения» в современной теории информации, однако сама идея значительно старше и является общей темой уже в древнегреческой мысли (Платон, «Теэтет», 191c, d; Аристотель, «О душе», кн. II, гл. 12, кн. III, гл. 4; Теофраст, «О чувствах», 50).

Позднее понятие tabula rasa получило развитие в теории познания Авиценны (ок. 980–1037 гг. н.э.):

Идея развития человеческого разума из состояния чистой доски была темой романа арабского андалузского философа Ибн-Туфейля (1105–1185 гг. н.э., известного на западе как «Abubacer» или « Эбн Тофаил»). Этот роман назывался «Повесть о Хайе, сыне Якзана» (Ибн-Туфейль 1988) и описывал развитие изолированного ребенка на необитаемом острове. Более поздний — 1761 года — перевод этого текста на латынь под заголовком Philosophus Autodidactus повлиял на эмпирика Джона Локка при формулировании им доктрины tabula rasa.

Размышления о понятии informatio под влиянием Авиценны встречаются у таких мыслителей, как Фома Аквинский (1225–1274 гг.) и Дунс Скот (1265/66–1308 гг.). Когда Аквинат обсуждает вопрос о том, могут ли ангелы взаимодействовать с материей, он обращается к аристотелианской доктрине гилеморфизма (т.е. теории о том, что вещество состоит из материи (hylo [древесина], субстанция) и формы (morphè)). В этом месте Аквинский переводит ее как ин-формирование материи (informatio materiaе) (Summa Theologiae,1a 110 2, Capurro 2009; Аквинский 2005–2016). Дунс Скот ссылается на informatio в узскоспециальном смысле, когда обсуждает теорию зрения Августина в трактате последнего «О Троице», XI Cap 2 par 3 (Duns Scotus, 1639, De imagine, Ordinatio, I, d.3, p.3).

Напряжение, которое уже существовало в классической философии между платоновским идеализмом (universalia ante res) и аристотелианским реализмом (universalia in rebus), было выделено как проблема универсалий: существуют ли универсальные качества, — такие как «человечность» или идея лошади, — отдельно от индивидуальных сущностей, являющихся их инстанциациями? Именно в контексте отказа от универсалий Оккам (ок. 1287–1347 гг. н.э.) вводит свою всем известную бритву: не следует умножать сущности сверх необходимости. Во всех своих сочинениях Аквинский и Скот используют латинские термины informatio и informare в узкоспециальном смысле, Оккамом же эта терминология не используется.

Современная философия

История понятия информации в философии Нового времени сложна. Начиная примерно с XIV века термин «информация» появился в различных развивающихся европейских языках в общем значении «образование» и «запрос/разыскание». Французский исторический словарь Годфруа (Godefroy 1881) приводит в качестве ранних значений «информации» слова действие, учение, талант, наука. Термин также в явном виде использовался для юридических запросов (Dictionnaire du Moyen Français (1330–1500) 2010). Из-за этого разговорного использования термин «информация» постепенно теряет связь с понятием «форма» и все меньше и меньше появляется в формальном смысле в философских текстах.

В конце средневековья общество и наука существенно изменились (Hazard 1935; Ong 1958; Dijksterhuis 1986). В ходе длительного и сложного процесса аристотелианская методология четырех причин была преобразована, дабы служить потребностям экспериментальной науки:

1. Материальная причина развилась в современное представление о материи.
2. Формальная причина была переосмыслена как геометрическая форма в пространстве.
3. Действующая причина была переопределена как прямое механическое взаимодействие между материальными телами.
4. Целевая причина была отклонена как ненаучная. Из-за этого у современников Ньютона возникли трудности с понятием силы гравитации в его теории. Гравитация как действие на расстоянии казалась повторным введением целевых причин.

В этом меняющемся контексте переосмысляется и аналогия отпечатка в воске.

Следствием данного изменения в методологии становится то, что лишь явления, объяснимые через механические взаимодействия между материальными телами, могут быть изучены с научной точки зрения. В современном смысле это может быть понято как редукция интенсивных свойств до измеримых экстенсивных свойств. Для Галилея это прозрение является программным:

Позднее эти идеи привели к учению о различии между первичными качествами (пространство, форма, скорость) и вторичными качествами (тепло, вкус, цвет и т.д.). В контексте философии информации наблюдения Галилея по поводу вторичного качества «тепла» имеют особое значение, поскольку закладывают основы для изучения термодинамики в XIX веке:

Ключевым мыслителем, участвовавшим в описываемой трансформации является Рене Декарт (1596–1650). В его «Размышлениях о первой философии» после «доказательства» того, что материя (res extensa) и сознание (res cogitans) являются разными субстанциями (то есть формами бытия, существующими независимо друг от друга), вопрос о взаимодействии между этими субстанциями становится проблемой. Податливость воска является для Декарта явным аргументом против влияния res extensa на res cogitans (Размышления II, 15). Тот факт, что кусок воска легко теряет свою форму и другие качества при нагревании, означает, что чувства не подходят для идентификации объектов в мире. Таким образом, истинное знание может быть достигнуто только «проверкой ума». Здесь метафора воска, которая на протяжении более 1500 лет использовалась для объяснения чувственных впечатлений, используется для оспаривания возможности достичь знания через чувства. Так как сутью res extensa является протяженность, мышление принципиально не может быть понято как пространственный процесс. Декарт все еще использует термины «форма» и «идея» в первоначальном схоластическом негеометрическом (вневременном и внепространственном) смысле. Примером является краткое формальное доказательство существования Бога во втором ответе Мерсенну в «Размышлениях»:

Я называю их «идеями», говорит Декарт

Поскольку res extensa и res cogitans являются разными субстанциями, акт мышления никогда не может быть воспроизведен в пространстве: машины не могут иметь универсальных способностей разума. Декарт приводит два отдельных соображения в пользу этой позиции:

Этот отрывок релевантен теме, поскольку в нем прямо говорится о возможности искусственного интеллекта. Более того, его даже можно интерпретировать как аргумент против возможности создания универсальной машины Тьюринга: разум как универсальный инструмент никогда не может быть воспроизведён в пространстве. Эта концепция находится в противоречии с современной концепцией информации как измеримой величины, в которой она является пространственной по существу, т.е. экстенсивной (но в несколько другом смысле, нежели в используемом Декартом).

Декарт не предлагает новую интерпретацию понятий формы и идеи, однако создает почву для дискуссии о природе идей, которая развивается вокруг двух противоположных позиций:

Рационализм: Представление Декарта о том, что идеи являются врожденными и, следовательно, априорными. Эта версия рационализма подразумевает интерпретацию понятия идей и форм как вневременных, внепространственных, но сложных структур, например, идеи «лошади» (т.е. даже на уровне идеи обладающей головой, телом и ногами). Эта позиция также хорошо согласуется с интерпретацией познающего субъекта как созданного существа (ens creatu). Бог создал человека по своему собственному образу и тем самым предоставил человеческому уму адекватный набор идей, позволяющий последнему понять его — Божье — творение. В этой теории рост знаний априори ограничен; создание новых идей ex nihilo невозможно. Данную точку зрения трудно совместить с концепциями экспериментальной науки.

Эмпиризм: Концепции строятся в уме апостериорно — на основе идей, связанных с чувственными впечатлениями. Эта доктрина подразумевает новую интерпретацию концепции идеи как:

Здесь идеи понимаются как элементарные строительные блоки человеческого знания и рефлексии. Это хорошо согласуется с требованиями экспериментальной науки. Недостатком же является то, что разум никогда не сможет сформулировать аподиктические истины о причине и следствии или сути наблюдаемых сущностей, включая утверждения о своей идентичности. Человеческое знание становится принципиально вероятностным (Локк 1985: кн. I, гл. 4, п. 25)‹2›.

Поскольку эти идеи не участвуют в обосновании аподиктических знаний, необходимость подчеркивать вневременную и внепространственную природу идей исчезает. Построение понятий на основе сочетаний элементарных идей, которые сами основываются на чувственном опыте, открывает ворота для реконструкции знания как экстенсивного свойства агента: большее число идей подразумевает более вероятное знание.

Во второй половине XVII века формальная теория вероятности была разработана такими исследователями, как Паскаль (1623–1662), Ферма (1601 или 1606–1665) и Христиан Гюйгенс (1629–1695). Работа De ratiociniis in ludo aleae Гюйгенса была переведена на английский язык Джоном Арбетнотом (Arbuthnot 1692). Для этих авторов мир был по сути механистическим и, следовательно, детерминированным, отсюда вероятность была лишь качеством человеческого знания, проистекающим из его несовершенства:

Вероятно, данный текст повлиял на Юма, который первым объединил формальную теорию вероятностей с теорией познания:

Здесь знание о будущем рассматривается как степень веры, измеряемая вероятностью, — которая, в свою очередь, объясняется числом конфигураций, которые способна иметь детерминированная система в мире. Все основные строительные блоки современной теории информации на месте, они присутствуют здесь. С помощью своей новой концепции знания эмпирики заложили основу для последующего развития термодинамики как редукции вторичного качества тепла к первичным качествам тел.

В то же время термин «информация», по-видимому, утратил большую часть своего узскоспециального значения в трудах эмпириков, поэтому новая линия развития не была обозначена в качестве нового толкования понятия «информация». Локк иногда использует фразу, что наши чувства «информируют» нас о мире, и иногда использует слово «информация».

Юм, кажется, использует информацию таким же случайным образом, когда замечает:

Впрочем, методология эмпиризма и сама не была беcпроблемной. Ее наибольшая проблема заключалась в том, что все знания становятся вероятностными и апостериорными. Иммануил Кант (1724–1804) был одним из первых, кто указал, что человеческий разум обладает метаконцепциями пространства, времени и причинности, которые никогда не могут быть поняты как результат простого сочетания «идей». Более того, эти интуиции позволяют нам с уверенностью формулировать научные прозрения: например, что сумма углов треугольника в евклидовом пространстве равна 180 градусам. Это обстоятельство не может быть объяснено в эмпиристских рамках. Если знание создается при помощи комбинации идей, тогда должен существовать априорный синтез идей в человеческом разуме. Согласно Канту, это подразумевает, что человеческий разум может оценить свою собственную способность формулировать научные суждения. В «Критике чистого разума» Кант разработал трансцендентальную философию как исследование необходимых условий человеческих знаний. Хотя трансцендентальная программа Канта не вносит непосредственный вклад в развитие концепции информации, она оказала заметное влияние на исследования основ математики и других областей знания, имеющих отношение к этой теме. Примерами тому за XIX и XX века могут служить работы Фреге, Гуссерля, Рассела, Брауэра, Витгенштейна, Гёделя, Карнапа, Поппера и Куайна.

Историческое развитие значения термина «информация»

История термина «информация» неразрывно связана с изучением центральных проблем эпистемологии и онтологии в западной философии. Зародившись в качестве узкоспециального термина в классических и средневековых текстах, термин «информация» почти исчез из философского дискурса в философии Нового времени, но приобрел популярность в разговорной речи. Постепенно термин получил статус абстрактного массового существительного, т.е. приобрел значение, никак не относящееся к классическому его смыслу, ориентированному на процесс. В таком виде термин был подхвачен несколькими исследователями (Fisher 1925; Shannon 1948) в ХХ веке, которые ввели формальные методы измерения «информации». Это, в свою очередь, привело к возрождению философского интереса к понятию информации. Столь сложная история, похоже, является одной из главных причин, почему формулировка определения единого понятия информации, удовлетворявшего бы всем нашим представлениям, так трудна. Исторически релевантны как минимум три разных значения слова «информация»:

«Информация» как процесс бытия информированным (ин-формирования). Это самое старое значение, обнаруживаемое в трудах таких авторов, как Цицерон (106–43 гг. до н.э.) и Августин (354–430 гг. н.э.): оно теряется в современном дискурсе, хотя связь информации с процессами (т.е. вычислениями, потоками или отправлением сообщений) все еще существует. В классической философии можно сказать, что когда я распознаю лошадь в качестве таковой, тогда «форма» лошади появляется в моем уме. Этот процесс и есть моя «информация» о природе лошади. Также акт обучения можно назвать «информацией» ученика. В том же смысле можно сказать, что скульптор создает скульптуру, «информируя» кусок мрамора. Задача скульптора — «ин-формация» статуи (Capurro & Hjørland 2003). Это ориентированное на процесс значение довольно надолго сохранилось в западноевропейском дискурсе: даже в XVIII веке Робинзона Крузо мог подразумевать под образованием своего слуги Пятницы его «информацию» (Дефо 1935). В данном значении термин также используется Беркли: «Я люблю информироваться всеми темами, которые встречаются на моем пути, а особенно наиболее важными» (Беркли 1996, диалог 1, разд. 5, п. 6/10). 

«Информация» как состояние агента (информированность), т.е. как результат процесса информирования (см. предыдущее значения). Если кто-то учит ученика теореме Пифагора, то после завершения этого процесса можно сказать, что ученик «обладает информацией о теореме Пифагора». В этом значении термин «информация» является результатом той же подозрительной формы субстантивации глагола (informare > informatio), что и многие другие узкоспециальные термины в философии (субстанция, сознание, субъект, объект). Этот вид терминологии печально известен своими концептуальными трудностями. Можно ли вывести факт, что у меня «есть» сознание, из того, что я и есть сознание? Можно ли получить тот факт, что у меня «есть» информация, из того, что я был информирован? Переход к этому современному конкретизированному значению, по-видимому, происходил постепенно и был общим для пространства Западной Европы по меньшей мере с середины XV века. В эпоху Возрождения ученого можно было бы назвать «человеком информации» так же, как мы сегодня можем сказать, что кто-то получил образование (Adriaans and van Benthem 2008b; Capurro & Hjørland 2003). В «Эмме» Джейн Остен можно прочесть: «Мистер Мартин, я полагаю, человек, не слишком сведущий (man of information) в тех предметах, кои не входят в круг его занятий. Он не привержен к чтению?» (Остин 2015: 12).

«Информация» как предрасположенность информировать, т.е. как способность объекта информировать агента. Когда акт обучения меня теореме Пифагора оставляет во мне информацию об этой теореме, естественно предположить, что текст, в котором теорема объясняется, на самом деле «содержит» эту информацию. Текст обладает способностью информировать меня, когда я его читаю. В том же смысле, когда я получил информацию от учителя, я способен передать эту информацию другому ученику. Таким образом, информация становится чем-то, что можно хранить и измерять. Это последнее понятие информации как абстрактного массового существительного получило широкое признание в современном обществе и обрело окончательную форму в XIX веке, позволив Шерлоку Холмсу сделать следующее наблюдение: «…друг Лестрейд держал в руках информацию, ценность которой он сам не знал» («Приключение знатного холостяка», Конан Дойль 2016).

Строительные блоки современных теорий информации

Оглядываясь назад, мы замечаем: многие понятия, имеющие отношение к системам оптимальных кодов, идеальным языкам, а также к связи между языками вычисления и обработки, были постоянными предметами философских размышлений с XVII века.

Языки

Один из наиболее сложных проектов, посвященных универсальному «философскому» языку был разработан епископом Джоном Уилкинсом в работе «Опыт о подлинной символике и философском языке» (1668). Проект Уилкинса состоял из сложной системы символов, которые предположительно были связаны с однозначными понятиями в реальности. Построения такого рода сделали философов чувствительными к глубоким связям между языком и мышлением. Эмпирическая методология позволила представить развитие языка как системы условных знаков, соответствующих связям между идеями в человеческом уме. Проблема, которая в настоящее время известна как проблема «заземления символов» (как произвольные знаки приобретают свое интерсубъективное значение), была одной из наиболее обсуждаемых в XVIII веке в контексте проблемы происхождения языков. Самые разные мыслители, — такие как Вико, Кондильяк, Руссо, Дидро, Гердер и Гаман, — внесли свой вклад в ее обсуждение. Центральный вопрос заключался в том, был ли язык задан априори (Богом) или же он был создан и, следовательно, являлся изобретением самого человека. Типичным примером существовавшего тогда интереса к этой теме был конкурс, анонсированный Королевской прусской академией наук в 1769 году‹3›:

Спор продолжался более века без какого-либо заключения, и в 1866 году Парижское лингвистическое общество (Société de Linguistique de Paris) исключило этот вопрос из перечня обсуждаемых‹4›.

С философской точки зрения более релевантной является работа Лейбница (1646–1716) по так называемой characteristica universalis: понятию универсального логического исчисления, которое было бы идеальным средством для научных рассуждений. Центральное предположение в философии Лейбница заключается в том, что такой совершенный язык науки принципиально возможен в силу совершенной природы мира как творения Бога (ratio essendi = ratio cognoscendi, основание бытия есть основание знания). Этот принцип был отвергнут Вольфом (1679–1754), который предложил более эвристически ориентированную characteristica combinatoria (van Peursen 1987). Данным идеям предстояло дождаться таких мыслителей, как Буль (1854, «Исследование законов мышления»), Фреге (1879, «Исчисление понятий» [Фреге 1997]), Пирс (который уже в 1886 году предположил, что электрические цепи могут использоваться для обработки логических операций), а также Уайтхед и Рассел (1910–1913, Principia Mathematica [2005–2006]), в чьих руках они нашли плодотворное применение.     

Оптимальные коды

Тот факт, что частота использования тех или иных букв различается в зависимости от языка, был известен с момента изобретения книгопечатания. Для набора английского текста принтеры нуждались в большем количестве «e» и «t», чем «х» или «d». Знание об этом широко использовалось при расшифровки закодированных сообщений с XVII века (Kahn 1967; Singh 1999). В 1844 году помощник Сэмюэля Морзе Альфред Вейль определил частоту букв, используемых в местной газете в Морристауне, Нью-Джерси, а затем использовал это для оптимизации кода азбуки Морзе. Так что ядро ​​теории оптимальных кодов было создано задолго до того, как Шеннон разработал его математическую основу (Shannon 1948; Shannon & Weaver 1949). Исторически важными, но философски менее значимыми являются усилия Чарльза Бэббиджа по созданию вычислительных машин (Разностная машина в 1821 году и Аналитическая машина в 1834–1871 гг.), а также попытка Ады Лавлейс (1815–1852 гг.) разработать то, что считается первым языком программирования для Аналитической машины.

Числа

Самый простой способ представления чисел — это унарная система. В ней длина представления числа равна размеру самого числа, т.е. число «десять» представляется в виде «\\\\\\\\\\». Классическая римская система счисления является улучшением, поскольку содержит разные символы для разных порядков величины (один = I, десять = X, сто = C, тысяча = M). Однако эта система имеет и огромные недостатки, поскольку для кодирования натуральных чисел в принципе требуется бесконечное количество символов, а вследствие этого одни и те же математические операции (сложение, умножение и т.д.) принимают различные формы при работе с разным порядком величины. Около 500 г. н.э. в Индии было изобретено число ноль. Используя ноль в качестве заполнителя, мы можем кодировать бесконечное количество чисел конечным набором символов (один = 1, десять = 10, сто = 100, тысяча = 1000 и т.д.). С современной точки зрения возможно бесконечное количество позиционных систем счисления, если у нас есть 0 в качестве заполнителя и конечное число других символов. Наша обычная десятичная система счисления имеет десять цифр «0, 1, 2, 3, 4, 5, 6, 7, 8, 9» и представляет число двести пятьдесят пять как «255». В двоичной системе счисления у нас есть только символы «0» и «1». Здесь двести пятьдесят пять представлено как «11111111». В шестнадцатеричной системе с 16 символами (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f) это же число может быть записано как «ff». Отметим, что длина этих представлений значительно отличается.

Концепция позиционной системы счисления была привнесена в Европу персидским математиком аль-Хорезми (ок. 780 — ок. 850 г. н.э.). Его основная работа, посвященная числам (al-Khwarizmi, ок. 820 г. н.э.), была переведена на латынь как Liber Algebrae et Almucabola в XII веке — от ее названия, среди прочего, происходит термин «алгебра». Наше слово «алгоритм» происходит от Algoritmi, латинской формы имени автора. Позиционные системы счисления упростили коммерческие и научные расчеты.     

В 1544 году Майкл Стифель ввел понятие степени числа в Arithmetica integra (Stifel 1544). Таким образом, 8 можно записать как $2^3$, а 25 как $5^2$ . Понятие показателя степени сразу же предполагает понятие логарифма как обратной к нему функции: $\log_b b^a) = a$. Стифель сравнил арифметическую последовательность:     

$$-3, -2, -1, 0, 1, 2, 3$$

в которой члены имеют разность 1, с геометрической последовательностью:

$$\frac{1}{8}, \frac{1}{4}, \frac{1}{2} , 1, 2, 4, 8$$

в которой члены имеют отношение 2. Показатели степени позволили ему переписать значения второй таблицы как:

$$2^{-3}, 2^{-2}, 2^{-1}, 2^0 , 2^1 , 2^2, 2^3$$

где объединены обе таблицы. Возможно, это была первая логарифмическая таблица. Более определенная и практическая теория логарифмов разработана Джоном Непером (1550–1617) в его основной работе (Napier 1614). Он придумал термин логарифм (logos + arithmetic: соотношение чисел). Как видно из совпадения арифметических и геометрических прогрессий, логарифмы сводят произведения к суммам,

$$\log_b (xy) = \log_b (x) + \log_b (y)$$

деления сводят к вычитанию,

$$\log_b (x/y) = \log_b (x) - \log_b (y)$$

а возведение в степень — к умножению:

$$\log_b (x^p) = p \log_b (x)$$

После публикации логарифмических таблиц Бриггсом (Briggs 1624) эта новая методика облегчения сложных вычислений быстро завоевала популярность.

Физика

Галилей в 1623 году уже делал предположение, что анализ таких явлений, как тепло и давление, может быть сведен к изучению движений элементарных частиц (Галилей 1987). В рамках эмпирической методологии это представимо в виде вопроса о том, как сенсорный опыт вторичного качества тепла объекта или газа может быть сведен к движению частиц. Бернулли («Гидродинамика», опубликовано в 1738 году [Бернулли 1950]) был первым, кто разработал кинетическую теорию газов: в ней макроскопически наблюдаемые явления описываются в терминах микросостояний систем частиц, подчиняющихся законам ньютоновской механики — однако это была скорее интеллектуальная попытка придумать адекватную математическую трактовку. Клаузиус (Clausius 1850) сделал окончательный шаг, когда ввел понятие длины свободного пробега частицы между двумя столкновениями. Это открыло путь для статистической трактовки данных явлений Максвеллом, который сформулировал свое знаменитое распределение в 1857 году: оно было первым статистическим законом в физике. Окончательная же формула, связавшая все понятия вместе (и выгравированная на надгробии автора, хотя фактическая формула принадлежит Планку), была разработана Больцманом:

$$S = k \log W$$

Она описывает энтропию $S$ системы в терминах логарифма числа возможных микросостояний $W$, согласующихся с наблюдаемыми макроскопическими состояниями системы, где $k$ является известной постоянной Больцмана. При всей своей простоте значение этой формулы для современной науки трудно переоценить. C точки зрения теории информации выражение «$\log W$» может интерпретироваться по-разному: 

• Как количество энтропии в системе.
• Как длина числа, требуемого для подсчета всех возможных микросостояний, соответствующих макроскопическим наблюдениям.
• Как длина оптимального индекса, который нам нужен для идентификации конкретного текущего, но неизвестного микросостояния системы, т.е. это мера нашей «нехватки информации».
• В качестве меры вероятности любого типичного конкретного микросостояния системы, согласующегося с макроскопическими наблюдениями.  
  

Таким образом, данная формула связывает аддитивную природу логарифма с экстенсивными качествами энтропии, вероятности, типичности и информации, благодаря чему представляет собой фундаментально важный шаг в использовании математики для анализа природы. Позднее Гиббс (1950) уточнил формулу:

$$S = -\sum_i p_i \ln p_i,$$

где $p_i$ — вероятность того, что система находится в микросостоянии под номером «$i^{\textrm{th}}$». Эта формула была взята Шенноном (1948; Shannon & Weaver 1949) для характеристики коммуникационной энтропии системы сообщений. Хотя между математической трактовкой энтропии и информацией существует тесная связь, точная интерпретация этого факта с тех пор и до нашего времени является источником противоречий (Harremoës & Topsøe 2008; Bais & Farmer 2008).   

Вехи развития в философии информации

Современные теории информации появились в середине ХХ века в особом интеллектуальном климате, в котором дистанция между науками и областями академической философии была довольно велика. Некоторые философы проявляли особо антинаучную позицию: например, Хайдеггер с его позицией «Der Wissenschaft denkt nicht» («Наука не мыслит»). С другой стороны, философы из Венского кружка открыто дискредитировали традиционную философию как занимающуюся иллюзорными проблемами (Carnap 1928). Программа исследований логического позитивизма была строгой реконструкцией философии, основанной на сочетании эмпиризма и последних достижений в логике. Возможно, из-за этого интеллектуального климата ранние значимые события в теории информации происходили в отрыве от основных линий философских размышлений. Перелом в этой ситуации обозначился с работы Дрецке в начале 80-х (Dretske 1981). С начала века интерес к философии информации значительно вырос — в основном под влиянием работы Лучано Флориди по семантической информации. Также быстрое теоретическое развитие квантовых вычислений и связанного с ними понятия квантовой информации оказали влияние на философские размышления. 

Поппер: информация как степень фальсифицируемости

Исследовательская программа логического позитивизма Венского кружка в первой половине ХХ  века оживила старый проект эмпиризма. Цель Кружка состояла в том, чтобы реконструировать научные знания на основе прямых наблюдений и логической связи между утверждениями об этих наблюдениях. Старая критика Канта в отношении эмпиризма была возвращена к жизни ​​Куайном (1951). В рамках логического позитивизма индукция была признана недействительной, и причинно-следственная связь не могла быть установлена ​​объективно. В своей книге «Логика и рост научного знания» (Logik der Forschung, 1934) Поппер формулирует хорошо известный критерий демаркации, который сам он недвусмысленно считает решением юмовской проблемы индукции (Popper 1934 [1977: 42]). Научные теории, сформулированные как общие законы, никогда не могут быть окончательно верифицированы, но могут быть фальсифицированы всего лишь одним наблюдением. Это означает, что теория «более» научна, если она содержательно богаче и дает больше возможностей для фальсификации:

Эта цитата в контексте исследовательской программы Поппера показывает, что стремление измерить объем эмпирической информации в научной теории, представленной в виде набора логических утверждений, уже было признано философской проблемой — более чем за десять лет до того, как Шеннон сформулировал свою теорию информации. Поппер осознает тот факт, что эмпирическое содержание теории связано с ее фальсифицируемостью, а также что это, в свою очередь, связано с вероятностью конкретных утверждений в составе теории. Теории с более эмпирической информацией менее вероятны. Поппер отличает логическую вероятность от числовой вероятности («которая применяется в теории азартных игр и статистике», Поппер 1983: 157; курсив автора). В отрывке, который является программным для последующего развития концепции информации, он определяет понятие логической вероятности следующим образом: 

Поппер так и не преуспел в формулировке хорошей формальной теории для измерения этого количества информации, хотя в более поздних работах он предполагает, что теория информации Шеннона может быть полезной (Popper 1934 [1977], 404 [Appendix IX, from 1954]). Эти вопросы впоследствии были разработаны в философии науки. Теория конформации изучает индукционную теорию и то, как доказательства «поддерживают» определенную теорию (Huber 2007). Хотя работа Карнапа подстегнула важные разработки как в философии науки, так и в философии информации, связь между этими двумя дисциплинами, похоже, была потеряна. В работе Кёйперса (Kuipers 2007a) нет упоминания теории информации или какой-либо более фундаментальной работы в области философии информации, однако эти две дисциплины определенно имеют области пересечения. (См., напр., обсуждение так называемого парадокса черных воронов в Kuipers 2007b и Rathmanner & M. Hutter 2011).

Шеннон: информация, определенная с точки зрения вероятности

В двух знаковых работах Шеннон (Shannon 1948; Shannon & Weaver 1949) выразил коммуникационную энтропию системы сообщений A следующей формулой:

$$H(P) = -\sum_{i\in A} p_i \log_2 p_i$$

Здесь $p_i$ — вероятность сообщения $i$ в $A$. Это выражение является точным аналогом формулы энтропии Гиббса в физике. Использование логарифмов по основанию 2 гарантирует, что длина кода измеряется в битах (двоичных цифрах). Легко увидеть, что коммуникационная энтропия системы максимальна, когда все сообщения имеют равную вероятность и, следовательно, являются типичными.

Количество информации $I$ в отдельном сообщении $x$ задано выражением:

$$I(x) = -\log p_x$$

Эта формула может быть интерпретирована как обратная к энтропии Больцмана; она также охватывает ряд наших основных интуиций относительно информации:

• Сообщение $x$ имеет определенную вероятность возникновения $p_x$, от 0 до 1.
• Если $p_x = 1$, тогда $I(x) = 0$. Если мы уверены в получении сообщения, тогда оно буквально не содержит «ничего нового». Чем меньше вероятность сообщения, тем больше информации оно содержит. Сообщение типа «Солнце взойдет завтра», судя по всему, содержит меньше информации, чем сообщение «Иисус — это Цезарь», как раз потому, что второе утверждение вряд ли кто-то будет отстаивать (хотя его можно найти в интернете).
• Если два сообщения $х$ и $у$ не связаны между собой, тогда $I(x\textrm{ и } y)=I(x) + I(y)$. Информация экстенсивна. Количество информации в двух объединенных сообщениях равно сумме количеств информации в отдельных сообщениях.
  

Информация, представленная через отрицательный логарифм вероятности, является единственной математической функцией, которая в точности выполняет эти ограничения (Cover & Thomas 2006). Шеннон предлагает теоретическую структуру, в которой двоичные строки могут интерпретироваться как слова в языке (программирования), содержащем определенное количество информации (см. раздел 3.1). Выражение $-\log p_x$ задает точную длину оптимального кода для сообщения $x$ и как таковое формализует старую интуицию о том, что коды более эффективны при более коротких представлениях букв с большей частотой встречаемости (см. раздел 3.2). Логарифмы как способ сведения умножения к сложению (см. раздел 3.3) являются естественном представлением экстенсивных свойств систем — и уже в качестве таковых были использованы физиками в XIX веке (см. раздел 3.4).    

Таким образом, утверждения «Иисус – это Цезарь» и «Луна сделана из зеленого сыра» могут содержать одинаковое количество информации, в то время как их значение совершенно различное. Значительная часть усилий в области философии информации была направлена ​​на разработку более семантически-ориентированных теорий информации (Bar-Hillel and Carnap 1953; Floridi 2002, 2003, 2011). Хотя предложения Шеннона поначалу были почти полностью проигнорированы философами, в последние десятилетия значительность их влияния на философские проблемы стала очевидной. Дрецке (Dretske 1981) был одним из первых, кто проанализировал философские следствия теории Шеннона, однако точная связь между различными системами логики и теории информации все еще неясна (см. раздел 6.6).

Соломонов, Колмогоров, Хайтин: информация как длина программы

Проблема соотнесения набора утверждений с набором наблюдений, а также определения соответствующей вероятности, была рассмотрена Карнапом (Carnap 1945, 1950). Он различал две формы вероятности: вероятность$_1$ или «степень подтверждения» $P_1 (h ; e)$ представляет собой логическую связь между двумя предложениями, гипотезой $h$ и предложением $e$, в котором сообщается о ряде наблюдений. Утверждения такого типа либо аналитические, либо противоречивые. Вторая форма, вероятность$_2$ или «относительная частота», является статистической концепцией. По словам его ученика Соломонова (Solomonoff 1997): 

Метод приписывания вероятностей, используемый Карнапом, не был универсальным и сильно зависел от используемых систем кодирования. Общая теория индукции с использованием правила Байеса может быть развита только тогда, когда мы можем приписать универсальную вероятность «любой возможной последовательности» символов. В работе 1960 года Соломонов (Solomonoff 1960, 1964а, b) был первым, кто набросал план решения этой проблемы. Он сформулировал понятие, сегодня известное как универсальное распределение вероятности: рассмотрим множество всевозможных конечных строк в качестве программ для универсальной машины Тьюринга $U$ и определим вероятность строки $x$ символов в терминах длины самой короткой программы $p$, которая выдаёт $x$ на $U$.

Это понятие алгоритмической теории информации несколько позже было независимо изобретено Колмогоровым (Kolmogorov 1965) и отдельно Хайтиным (Chaitin 1969). Левин (Levin 1974) разработал математическое выражение универсальной априорной вероятности как универсальной (т.е. максимальной) нижней полувычислимой полумеры $M$ и показал, что отрицательный логарифм $M (x)$ совпадает с колмогоровской сложностью $x$ с точностью до аддитивного логарифмического члена. Действительное определение меры сложности таково:

Колмогоровская сложность. Алгоритмическая сложность строки $x$ равна длине $l (p)$ наименьшей программы $p$, которая производит $x$, будучи запущенной на универсальной машине Тьюринга $U$ , обозначенной как: $U(p)=x$:

$$K(x):=\min_p \{l(p), U(p)=x\}$$

Алгоритмическая теория информации (она же колмогоровская теория сложности) превратилась в богатую область исследований с широким спектром сфер применения, многие из которых философски актуальны (Li and Vitányi 1997):

• Она дает нам общую теорию индукции. Использование правила Байеса позволяет по-новому переформулировать принцип бритвы Оккама с точки зрения минимальной длины описания (Rissanen 1978, 1989; Barron, Rissanen, Yu 1998; Grünwald 2007) и минимальной длины сообщения (Wallace 2005). Стоит отметить, что Домингос (Domingos 1998) выступил против общезначимости этих принципов.
• Она позволяет нам сформулировать значение вероятности и информационного наполнения для отдельных объектов — даже для отдельных натуральных чисел.
• Она закладывает основы теории обучения, где последнее понимается как процедура сжатия данных (Adriaans 2007).
• Она дает определение случайности строки в терминах несжимаемости. Это само по себе привело к возникновению совершенно новой области исследований (Niess 2009; Downey & Hirschfeld 2010).
• Она позволяет нам сформулировать объективную априорную меру предсказательной ценности теории с точки зрения дефицита случайности в последней. Иными словами, лучшая теория — это наикратчайшая теория, которая делает данные условно случайными по отношению к теории (Vereshchagin and Vitányi 2004).

Впрочем, у этого подхода есть и свои недостатки:

1. Алгоритмическая сложность невычислима, хотя во многих практических случаях ее можно аппроксимировать, причем коммерческие программы сжатия в некоторых случаях приближаются к теоретическому оптимуму (Cilibrasi and Vitányi 2005).
2. Алгоритмическая сложность — это асимптотическая мера (т.е. она дает правильное значение с точностью до константы). В некоторых случаях значение этой константы недопустимо использовать из практических соображений.
3. Хотя самая короткая теория всегда является лучшей с точки зрения дефицита случайности, постепенно возрастающее сжатие наборов данных в общем случае не является хорошей стратегией обучения, так как дефицит случайности не уменьшается монотонно с коэффициентом сжатия (Adriaans and Vitányi 2009).
4. Общность определений, предоставляемых алгоритмической теорией информации, зависит от общезначимости концепции универсальной машины Тьюринга и, следовательно, в конечном итоге — от интерпретации тезиса Чёрча — Тьюринга.
5. Колмогоровская сложность объекта не учитывает количество времени, которое требуется для фактического вычисления объекта. В этой связи Левин предложил вариант колмогоровской сложности, который выбраковывает время вычислений (Левин 1973, Levin 1984):
   
   Сложность Левина. Сложность Левина строки $х$ является суммой длины $l (p)$ и логарифма от времени вычисления, требуемого производящей $x$ наименьшей программе $p$, которая запущена на универсальной машине Тьюринга $U$, обозначенной как $U(p) = x$:
   $$Kt(x):=\min_p \{l(p) + \log(time(p)), U(p)=x\}$$

Алгоритмическая теория информации получила быстрое признание в качестве фундаментальной теории информации. В известном многим введении в «Теорию информации» авторы книги утверждают: «…мы считаем сложность Колмогорова (т.е. АТИ) более фундаментальной, чем энтропию Шеннона» (Cover and Thomas 2006: 3).

Идея о том, что теория алгоритмической сложности является основой для общей теории искусственного интеллекта (и теории познания), уже была предложена Соломоновым (Solomonoff 1997) и Хайтиным (Chaitin 1987). Некоторые авторы защищают позицию, что сжатие данных является общим принципом, определяющим мышление человека (Chater & Vitányi 2003; Wolff 2006). Хаттер (Hutter 2005, 2007а, b) утверждает, что формальная и полная теория Соломонова по существу решает проблему индукции: Xаттер (Hutter 2007a) и Ратманнер и Хаттер (Rathmanner & Hutter 2011) перечисляют множество связанных с индукцией классических философских и статистических проблем, а затем утверждают, что теория Соломонова решает все эти проблемы или их всех избегает. Вероятно, из-за своего технического характера теория была в значительной степени проигнорирована философским сообществом. Тем не менее, ее выделяют как один из самых фундаментальных вкладов в теорию информации в XX  веке, и она явно актуальна для ряда философских вопросов, в том числе для упомянутой проблемы индукции. 

Систематические соображения

В математическом смысле информация связана с измерением экстенсивных свойств классов систем с конечными, но неограниченными размерностями (системы частиц, текстов, кодов, сетей, графов, игр и т.д). Это указывает на возможность единообразной трактовки различных теорий информации. В «Руководстве по философии информации» выделяются три различные формы информации (Adriaans and van Benthem 2008b):

Информация-А: Знание, логика, передаваемое в информативных ответах содержание

Информация-В: Вероятностная, теоретико-информационная, измеряется количественно

Информация-C: Алгоритмическая, сжатие кода, измеряется количественно

Благодаря недавним исследовательским находкам, связи между Информацией-B (Шеннон) и Информацией-C (Колмогоров) стали понятны достаточно хорошо (Cover and Thomas 2006). Представленный в данной статье исторический материал дает основание предположить, что размышления об Информации-А (логике, знании) имеют куда больше исторических переплетений, чем казалось общеизвестным до сих пор. Исследовательская программа логического позитивизма может быть задним числом охарактеризована как попытка объединить интерпретацию логики возможных миров с вероятностными рассуждениями (Carnap 1945, 1950; Поппер 1987; из недавних подходов в этой области см. Hutter et al. 2013). Современные попытки создать байесовскую эпистемологию (Bovens and Hartmann 2003), по-видимому, не в курсе усилий, проделанных в первой половине ХХ века. Однако попытка объединить Информацию-А и Информацию-В представляется жизнеспособным интеллектуальным предприятием. Кроме того, связь между термодинамикой и теорией информации стала куда более тесной, в частности, благодаря работе Гелл-Манна и Ллойда (Gell-Mann & Lloyd 2003) (см. также: Bais and Framer 2008). Верлинде (Verlinde 2011, 2017) даже представил модель редукции гравитации к информации.

Философия информации как расширение философии математики

Когда речь заходит об основных определениях понятия информации, — таких как информация Шеннона, колмогоровская сложность, семантическая информация и квантовая информация, — объединяющий подход к философии информации представляется возможным, если интерпретировать ее как расширение философии математики. В этом случае ответы на вопросы наподобие «Что такое данные?» и «Что такое информация?» вытекают из ответов на сопряженные вопросы вроде «Что такое множество?» и «Что такое число?». Оглядываясь назад, можно увидеть, сколь многие открытые проблемы в философии математики вращаются вокруг понятия информации.

Коль скоро мы примем эти понятия как основополагающие, остальные данные теории и вычисления разворачиваются вполне естественно. Здесь можно «вставить» свою любимую эпистемологическую или метафизическую позицию, хотя по сути это не влияет на фундаментальные проблемы в философии вычислений и информации. Можно придерживаться формалистского, платонического или интуиционистского взгляда на математическую вселенную — и все же соглашаться с базовым представлением о том, что такое эффективное вычисление. В силу своей финитистской и конструктивистской природы теория вычислений, по всей видимости, обитает в той общей зоне, где пересекаются упомянутые онтологические теории. 

Информация как природное явление

Информация как научная концепция естественным образом возникает в контексте нашего повседневного взаимодействия с природой, когда мы измеряем вещи. Примерами тому служат вполне обычные действия: измерение размера объекта с помощью палки, подсчет с помощью пальцев или рисование прямой линии с помощью куска веревки. Эти процессы являются опорными точками для таких абстрактных понятий как длина, расстояние, число и прямая линия, в свою очередь, выступающих строительными блоками науки. Сам факт, что эти концепции основаны на нашем конкретном опыте взаимодействия с реальностью, гарантирует их применимость и полезность. Исторически самые ранние следы обработки информации, которые мы можем обнаружить, группировались вокруг таких бытовых областей как счет, администрирование и хозяйственный учет.

Пример: подсчетные палочки 

Одним из самых элементарных устройств измерения информации является унарный подсчет с использованием счетных палочек‹5›. Счетные палочки использовались уже около 20 000 лет назад. Убив оленя, гипотетический доисторический охотник мог зарегистрировать этот факт, сделав царапину «|» на куске дерева. Каждый штрих на такой палке представляет объект / предмет / событие. Процесс унарного подсчета основан на простейшей операции объединения символов в последовательности. Данный метод измерения иллюстрирует примитивную версию концепции экстенсивности информации: длина последовательностей является мерой количества подсчитанных предметов. Обратите внимание, что такой последовательный процесс подсчета является некоммутативным и неассоциативным. Если «|» — наш основной символ, а $\oplus$ — наш оператор конкатенации‹6› , то последовательность знаков имеет вид:       

$$((\dots(| \oplus |) \dots) \oplus |)\oplus |)$$

Новый символ всегда объединяется в цепочку в конце последовательности.

Данный пример помогает понять важность контекста при анализе информации. Сама по себе царапина на палочке может вообще не иметь никакого значения, но, как только мы решим, что такая царапина представляет другой объект или событие, она становится значимым символом. Когда мы манипулируем ей в таком контексте, мы обрабатываем информацию. В принципе, простая царапина может представлять любое событие или объект, которые нам нравится: символы условны.   

Определение: символ — это отметка, знак или слово, которое указывает, означает или понимается как представляющий нечто — идею, объект или отношение.

Символы являются семантическими якорями, с помощью которых системы манипулирования символами связаны с миром. Обратите внимание, что, при условии истинности, метаутверждение:

устанавливает, что такое семантическая информация:

• она правильно сформирована: у сообщения есть определенный синтаксис.
• она значима: царапина «|» имеет значение только в контексте, где она фактически сделана преднамеренно (например, на палочке или в скале, чтобы служить заметкой о вполне определенном явлении).
• она правдива.

Манипуляция символами может принимать различные формы и не ограничивается последовательностями. В доисторические времена уже существовало множество примеров различных форм обработки информации.

Пример: подсчет овец в Месопотамии

По мере того, как поселения Месопотамии проходили период урбанизации, в них около 8000 г. до н.э. возникли ранние системы учета скота — для этого использовались глиняные жетоны (Schmandt-Besserat 1992). Для разных типов животных — например, овец и коз, — использовались жетоны различной формы. После пересчета жетоны упаковывались в шаровидный глиняный сосуд с наружными отметками, указывающими на его содержимое. Сосуд запечатывали, чтобы результаты пересчета животных нельзя было изменить. Так появились и ранние формы письма. После 4000 г. до н.э. жетоны стала насаживать на веревку, чтобы сохранить порядок. 

В этом примере для нас важна историческая трансформация из множеств в строки, которые являются более сложной форма кодирования информации. Формально мы можем выделить несколько уровней сложности комбинации жетонов:

• Неупорядоченный массив одинаковых жетонов в сосуде. Он представляет собой множество. Жетоны могут свободно перемещаться в сосуде. Единственное релевантное качество — это количество (объем) жетонов.
• Неупорядоченный массив жетонов разных типов в сосуде. Он представляет собой так называемое мультимножество. Теперь имеют значение как объем, так и частота встречаемости элементов.
• Упорядоченный массив типизированных жетонов на веревке. Он представляет собой последовательность символов. В данном случае имеющим значение качеством является длина строки.

Обработка символов и экстенсивность: множества, мультимножества и строки

Последовательности символов кодируют больше информации, чем мультимножества, а мультимножества более выразительны, чем множества. Таким образом, появление самой письменности можно рассматривать в виде стремления найти наиболее выразительное представление административных данных. При измерении информации в последовательностях сообщений важно различать такие аспекты, как повторение, порядок и группировка. Экстенсивные аспекты информации могут быть изучены в терминах подобных структурных операций. Мы можем изучать наборы сообщений посредством операторов, определенных на последовательностях символов.

Определение: Пусть $m, n, o, p, …$ являются символами, а $\oplus$ является тензором или же оператором конкатенации. Определим класс последовательностей следующим образом: 

1. Любой символ — это последовательность.
2. Если $\alpha$ и $\beta$ — последовательности, тогда $(\alpha\oplus\beta)$ тоже последовательность.

Для последовательностей мы определяем следующие основные свойства на уровне конкатенации символов:

• Сжатие:
  $$(m\ \oplus m) = m.$$
  Сжатие уничтожает информацию о частоте внутри последовательности. Физическая интерпретация: два вхождения одного и того же символа могут сокращаться до одного вхождения, когда они объединены в цепочку.
• Коммутативность (переместительность):
  $$(m\ \oplus n) = (n\ \oplus\ m)$$
  Коммутативность уничтожает информацию о порядке в последовательности. Физическая интерпретация: символы могут меняться местами, когда они соединены в цепочку.
• Ассоциативность (сочетательность):
  $$(p\oplus (q \oplus r)) = ((p \oplus q)\oplus r)$$
  Ассоциативность уничтожает информацию о вложенности в последовательности. Физическая интерпретация: символы могут быть перегруппированы, когда они объединены в цепочку.

Наблюдение: системы последовательностей со сжатием, коммутативностью и ассоциативностью ведут себя как множества. Рассмотрим уравнение:
$$\{p,q\} \cup \{p,r\} = \{p,q,r\}$$
Если в качестве моделей этих множеств мы возьмём две последовательности $(p \oplus q)$ и $(p \oplus r)$, соответствующий вывод таков:
$$(p \oplus q),(p \oplus r) \vdash ((p \oplus q) \oplus r)$$

Доказательство:

Множества: Последовательности сообщений распадаются на множества при условиях сжатия, коммутативности и ассоциативности. Множество — это массив объектов, в которомкаждый элемент встречается только один раз:

$$\{a,b,c\} \cup \{b,c,d\} = \{a,b,c,d\},$$

причем не важно, в каком порядке:

$$\{a,b,c\} = \{b,c,a\}.$$

Множества связаны с нашей повседневной наивной концепцией информации как новой, ранее неизвестной информации. Мы обновим наше множество только в том случае, если получим не встречавшееся ранее сообщение. Это понятие информации забывчиво как в отношении последовательности, так и в отношении частоты встречаемости. Множество сообщений не может быть восстановлено. Такое «поведение» связано с понятием экстенсиональности множеств: нас интересует только равенство элементов, а не частота встречаемости.

Мультимножества: последовательности сообщений распадаются на мультимножества при условиях коммутативности и ассоциативности. Мультимножество — это массив объектов, в которых один и тот же элемент может встречаться несколько раз.

$$\{a,b,c\} = \{b,c,a\}.$$

причем не важно, в каком порядке:

$$\{a,b,a\} = \{b,a,a\}.$$

Мультимножества связаны с чувствительной к ресурсам концепцией информации, определенной в информации Шеннона. Нас интересует частота (встречаемости) сообщений. Впрочем, это понятие информации забывчиво в отношении последовательности. Мы обновляем наше множество каждый раз, когда получаем сообщение, но забываем о структуре последовательности. Такое «поведение» связано с экстенсивностью информации: нас интересуют как равенство элементов, так и частота встречаемости.

Последовательности: Последовательности обладают ассоциативностью. Последовательности — это упорядоченные мультимножества: $aba \neq baa$. Вся структура последовательности сообщений сохраняется. Последовательности связаны с колмогоровской сложностью, определяемой как длина последовательности символов.

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

Наблюдение: Взаимозависимость между понятиями последовательности и мультимножества можно интерпретировать как формализацию податливости куска воска, — метафоры, в качестве парадигмы информации пронизывающей всю историю философии. Различные последовательности (формы) являются представлениями одного и того же мультимножества (материи). Объем куска воска (длина строки) является постоянным и, следовательно, является мерой количества информации, которая может быть представлена ​​в воске (то есть в последовательности символов). С точки зрения квантовой физики стабильность куска воска, похоже, является новым свойством: статистическая нестабильность объектов на атомном уровне выравнивается, когда манипулируют сразу большим их количеством.

Множества и числа

Понятие множества в математике считается фундаментальным. Любой идентифицируемый массив дискретных объектов можно рассматривать как множество. Связь между теорией множеств и понятием информации становится ясной, когда мы проанализируем основное утверждение:

$$e \in A,$$

прочитываемое так, что объект е является элементом множества A. Обратите внимание, что, при условии истинности, это утверждение представляет собой фрагмент семантической информации. Оно правильно сформировано, значимо и правдиво. По сути, понятие информации уже используется в основных строительных блоках математики. Философский вопрос «Что такое множества?», ответ на вопрос ti esti, неявно определяется аксиомами Цермело–Френкеля, первая из которых — об экстенсиональности:

Идея, что математические понятия неявно определяются набором аксиом, была предложена Гильбертом, однако не является бесспорной (по этому вопросу с ним полемизировал логик и математик Фреге). Из того, что определение задается неявным образом, следует: у нас есть лишь примеры того, чем являются множества — но нет возможности сформулировать какой бы то ни было положительный предикат, определяющий их. Элементы множества могут не быть ни физическими, ни абстрактными, ни пространственными, ни временными, ни простыми, ни реальными. Единственным требованием на их счет является возможность сформулировать четкие суждения о членстве. Такое неявное определение понятия множества отнюдь не беспроблемно. Мы могли бы определить объекты, которые на первый взгляд кажутся правильными множествами, но после проверки окажутся внутренне несовместимыми. Так возникает основа для парадокса Рассела.

Парадокс Рассела:

Этот парадокс, ставший побудительным мотивом для многих исследований в области оснований математики, является вариантом «парадокса лжеца», приписываемым критскому философу Эпимениду (около 6 г. до н.э.), утверждавшему, что критяне всегда лгут. Сущность такого типа парадоксов заключается в сочетании понятий: универсальности, отрицания и самореференции (ссылки на себя).

Любой не являющийся критянином человек может заявить, что все критяне всегда лгут. Для критянина же это невозможно из-за универсального отрицательного самореференциального характера высказывания. Если это утверждение верно, тогда он не лжет, что делает утверждение неверным: перед нами настоящий парадокс, основанный на самопротиворечии. В том же ключе Рассел придумал концепцию множества всех множеств, которые не являются членами самих себя, для которых нельзя определить принадлежность. По-видимому, множество всех множеств является недопустимым объектом в теории множеств. В целом в философии и математике существует предел, до какой степени система способна проверять утверждения о себе внутри системы.

Неявное определение понятия множеств влечет за собой то, что класс по своей сути открыт. Скорее, есть математические определения объектов, насчет которых неясно или крайне противоречиво понять, будут ли они определять множество или нет.

Современная философия математики начинается с теории чисел Фреге — Рассела (Фреге 1997, Goodstein 1957), сформулированной в терминах множеств. Если мы примем понятие класса объектов как допустимое и фундаментальное, оно вместе с понятием взаимно-однозначного соответствия между классами объектов позволяет нам определить числа как множества равномощных классов.

Определение:

Два множества $A$ и $B$ равномощны, $A \sim B$, если между ними существует взаимно-однозначное соответствие, т.е. функция $f: A \rightarrow B$ такая, что для любого $a \in A$ существует ровно один $f(a) \in B$.

Любое множество, к примеру, из четырех объектов тогда становится представлением числа 4, и для любого другого множества объектов мы можем установить членство в классе эквивалентности, определяющем число 4, определив взаимно-однозначное соответствие ко множеству из нашего примера.

Определение:

Если $A$ — конечное множество, тогда $\mathcal{S}_A = \{X \mid X \sim A \}$ — класс всех множеств, равномощных A. Соответствующая операция обобщения это функция мощности: $|A|=\mathcal{S}_A = \{X \mid X \sim A \} = $. Так определяется натуральное число $|A|= n \in \mathbb{N}$, связанное со множеством $A$.

Мы можем реконструировать большие части математической вселенной, выбрав подходящие математические примеры объектов для ее заполнения. Начнем с предположения, что существует единственный уникальный пустой набор $\emptyset$, который представляет число 0. Это дает нам существование множества только с одним членом, $\{\varnothing\}$, для представления числа 1 — и, повторяя эту конструкцию, множество из $\{\varnothing,\{\varnothing\}\}$ для представления 2, а далее возникает весь набор натуральных чисел $\mathbb{N}$. Тогда элементарная арифметика определяется на основе аксиом Пеано:             

1. Ноль — это число.
2. Если $a$ — число, следующий элемент за $a$ — тоже является числом.
3. Ноль не следует ни за каким числом.
4. Два числа, для которых следующие за ними элементы равны, сами равны.
5. (аксиома индукции.) Если множество чисел $S$ содержит ноль, а также следующий элемент для каждого числа в $S,$ тогда каждое число находится в $S$.
   

Возникающий фрагмент математической вселенной является относительно бесспорным: как платоники, так и конструктивисты могут согласиться с его основными достоинствами. На основе аксиом Пеано мы можем определить более сложные функции: такие как сложение и умножение (которые являются замкнутыми на $\mathbb{N}$), и обратные функции, вычитание и деление (которые не являются замкнутыми — и приводят ко множеству целых чисел $\mathbb{Z}$ и множеству рациональных чисел $\mathbb{Q}$).   

Измерение информации в числах

Мы можем определить понятие информации для числа $n$ с помощью неопределенной функции $I(n)$. Мы видим, что сложение и умножение определяют мультимножества: обе операции не являются сжимающими, однако являются коммутативными и ассоциативными. Предположим, что мы интерпретируем тензорный оператор $\oplus$ как умножение $\times$. Представляется естественным определить семантику для $I(m \times n)$ в терминах сложения. Если мы получим оба сообщения, $m$ и $n$, общий объем информации в объединенных сообщениях будет суммой объема информации в отдельных сообщениях. Это приводит к следующим ограничениям:

Определение: ограничение аддитивности: 

$$I(m \times n) = I(m) + I(n)$$

Кроме того, мы хотим, чтобы большие числа содержали больше информации, чем меньшие, что приводит к:

Определение: ограничение монотонности: 

$$I(m) \leq I(m + 1)$$

Мы также хотим выбрать определенное число $a$ в качестве нашей основной единицы измерения: 

Определение: ограничение нормализации: 

$$I(a) = 1$$

Следующая теорема принадлежит Реньи (Rényi 1961):

Теорема: Логарифм — единственная математическая операция, которая удовлетворяет ограничениям аддитивности, монотонности и нормализации. 

Наблюдение: Логарифм $\log_a n$ от числа $n$ точно характеризует нашу интуицию о понятии информации в числе $n$. Когда мы решили, что 1) мультимножества являются правильной формализацией понятия экстенсивности, а 2) умножение является правильной операцией для выражения аддитивности, тогда логарифм является единственной функцией измерения, удовлетворяющей нашим ограничениям.
Мы определяем:

Определение: для всех натуральных чисел $n \in \mathbb{N}^{+}$

$$I(n) = \log_a n.$$

• Для $a$ = 2 нашей единицей измерения является бит.
• Для $a$ = $e$ (т.е. число Эйлера) нашей единицей измерения является гнат.
• Для $a$ = 10 нашей единицей измерения является Хартли.

Измерение информации и вероятностей в числовых множествах

Теперь для конечных множеств мы можем указать количество получаемой информации, когда нам известен определенный элемент из множества, — информации, условной по отношению к знанию о множестве в целом.

Определение: пусть $S$ — конечное множество, и мы имеем:

$$e \in S$$

тогда

$$I(e \mid S) = \log_a |S|,$$

т.е. логарифм от мощности множества.

Чем больше множество, тем сложнее поиск — и тем больше информации мы получаем, когда находим искомое. Верно и обратное: без какой-либо дополнительной информации вероятность выбрать определенный элемент из $S$  является $p_S(x) = \frac{1}{|S|}$. Связанная с этим функция — так называемая функция Хартли:

Определение: если выборка осуществляется равномерно случайным образом из конечного множества $S$, выявленная после получения результата информация задается функцией Хартли (Хартли 1959):   

$$H_0(S)= \log_a |S|$$

Сочетание этих определений дает теорему, которая связывает воедино понятия условной информации и вероятности:

Теорема об объединении: Если $S$ — конечное множество, тогда

$$I(x\mid S) = H_0(S)$$

Информация об элементе x из множества $S$, условная по отношению ко можеству, равна вероятности того, что мы выберем этот элемент $x$ при равномерном распределении — которое является мерой нашего незнания в случае, когда нам известно множество, но мы не знаем, какой элемент из него должен быть выбран.

Замечание: обратите внимание, что функция Хартли объединяет понятия энтропии, как оно определено Больцманом ($S = k \log W$, где $W$ — мощность множества микросостояний системы $S$), с понятием информации Шеннона $I_S(x) = - \log p(x)$. Если мы считаем $S$ набором сообщений, тогда вероятность выбрать элемент $x$ из набора (т.е. получить сообщение из $S$) при равномерном распределении $p$, равна $\frac{1}{|S|}$. $H_0(S)$ также известна как энтропия Хартли от $S$.

Используя эти результаты, мы определяем условное количество информации в подмножестве конечного множества следующим образом:

Определение: Если $A$ — конечное множество, а $B$ — произвольное подмножество $B \subset A$, где $|A|=n$ и $|B|=k$, имеем:

$$I(B\mid A)=\log_a {n \choose k}$$

Это всего лишь приложение нашего основного определения информации: мощность класса подмножеств $A$ размера $k$ равняется ${n \choose k}$.

Формальные свойства понятия вероятности задаются аксиомами вероятности Колмогорова:

Определение: $P(E)$ — вероятность того, что произойдет некое событие $E$. Тогда $(\Omega, F,P)$, где $P(\Omega)=1$, является вероятностным пространством, с выборочным пространством $\Omega$, пространством событий $F,$ а также вероятностной мерой $P$.

Пусть$P(E)$ — вероятность того, что произойдет некое событие $E$. Тогда пусть $(\Omega, F,P)$, где $P(\Omega)=1$, будет вероятностным пространством, с выборочным пространством $\Omega$ , пространством событий $F$, а также вероятностной мерой $P$.

1. Вероятность события является неотрицательным действительным числом.
2. Существует единица измерения. Вероятность того, что произойдет хотя бы одно из событий в пространстве событий, равна 1: $P(\Omega= 1)$
3. Вероятность аддитивна по множествам:
   $$P \left(\bigcup^{\infty}_{i=1} E_i \right) = \sum^{\infty}_{i=1} P(E_i)$$

Одним из следствий является монотонность: если $A \subseteq B$, подразумевается, что $P(A) \leq P(B)$. Обратите внимание, что описанное выше — то же самое понятие аддитивности, как оно определено для понятия информации. Впрочем, на субатомном уровне аксиома аддитивности Колмогорова теряет свою актуальность в пользу более утончённого понятия (см. раздел 5.3).

Перспективы объединения

С философской точки зрения важность рассмотренной теоретической конструкции заключается в том, что она ведет к онтологически нейтральной концепции информации, основанной на крайне ограниченной надежной базе аксиоматических предположений:

• Схема редукционна в том смысле, что, как только человек принимает такие понятия, как классы и отображения, определение понятия информации в контексте более сложных математических понятий возникает естественным образом.
• Схема универсальна в том смысле, что понятие множества универсально и открыто.
• Схема семантична в том смысле, что само понятие множества является семантическим понятием.
• Схема объединяет различные понятия (множества, мощность, числа, вероятность, экстенсивность, энтропия и информация) в единую согласованную концептуальную структуру.
• Схема онтологически нейтральна в том смысле, что понятие множества или класса не подразумевает каких-либо онтологических ограничений для его возможных членов.

Схема также показывает, как теория информации Шеннона и понятие энтропии Больцмана коренятся в более фундаментальных математических концепциях.

Хотя многие вопросы все еще остаются открытыми, — особенно в контексте отношений между теорией информации и физикой, — перспективы объединенной теории информации теперь выглядят лучше, чем в самом начале XXI века.       

Обработка информации и поток информации

Определение количества информации в числе при помощи логарифма позволяет нам классифицировать другие математические функции с точки зрения их способности обрабатывать информацию. Информационная эффективность функции — это разница между количеством информации на входе функции и количеством информации на выходе (Adriaans 2016 [OIR]). Она позволяет нам измерить, как информация протекает сквозь множество функций. Мы используем сокращение $f(\overline{x})$ вместо записи $f(x_1,x_2,\dots,x_k)$:

Определение: информационная эффективность функции: Пусть $f: \mathbb{N}^k \rightarrow \mathbb{N}$ будет функцией от $k$ переменных. Мы имеем:

• входную информацию $I(\overline{x})$ и
• выходную информацию $I(f(\overline{x}))$.
• Информационная эффективность выражения $f(\overline{x})$ равняется
  $$\delta(f(\overline{x}))= I(f(\overline{x})) - I(\overline{x})$$
• Функция $f$ является сохраняющей информацию, если $\delta(f(\overline{x}))=0$, т.е. содержит точно такое же количество информации, что и в своих вводных параметрах,
• она является сбрасывающей информации, если $\delta(f(\overline{x}))\lt 0$ и
• она имеет постоянную информацию, если $\delta(f(\overline{x})) = c$.
• она является расширяющей информацию, если $\delta(f(\overline{x}))\gt 0$.

В целом детерминированные системы обработки информации не создают новую информацию. Они только обрабатывают ее. Следующая фундаментальная теорема о взаимодействии между информацией и вычислениями принадлежит Адриансу и Ван Эмде Боасу (Adriaans and Van Emde Boas 2011): 

Теорема: детерминированные программы не расширяют информацию. 

Это соответствует как теории Шеннона, так и колмогоровской сложности. Результат детерминированной программы всегда один и тот же, поэтому вероятность результата равна 1, что, согласно теории Шеннона, дает 0 битов новой информации. Схожая ситуация и с колмогоровской сложностью: вывод программы никогда не может быть более сложным, чем длина самой программы плюс константа. Это глубоко проанализировано в Adriaans and Van Emde Boas 2011. В детерминированном мире дела обстоят так, что

$$\texttt{program(input)=output},$$

тогда

$$I(\texttt{output}) \leq I(\texttt{program}) + I(\texttt{input}).$$

Бесконечные вычисления изучаются в теории областей Скотта (Abramsky & Jung 1994).

Оценка информационной эффективности элементарных функций нетривиальна. Примитивные рекурсивные функции имеют одну операцию расширения информации, подсчет, одну операцию отбрасывания информации, выбор, а все остальные являются нейтральными в отношении информации. Информационная эффективность более сложных операций определяется сочетанием подсчета и выбора. С точки зрения информационной эффективности элементарные арифметические функции представляют собой сложные семейства функций, которые описывают вычисления с одинаковым результатом, но с разными историями вычислений.     

Некоторые арифметические операции расширяют информацию, некоторые имеют постоянную информацию, а некоторые сбрасывают информацию. Во время выполнения детерминированных программ может иметь место расширение информации, но, если программа эффективна, описательная сложность вывода ограничена. Поток информации определяется последовательностью типов операций и балансом между сложностью операций и количеством переменных.

Мы кратко обсудим информационную эффективность двух основных рекурсивных функций для двух переменных и их возможности кодирования:

$$(2 + 98) + (47 + 53) = (2 + 47) + (53 + 98) = 200,$$

однако:

$$\delta(2+98) + \delta(47 + 53) + \delta(100 + 100) \approx -1.08 > \\delta(2 + 47) + \delta(53 + 98) + \delta(49 + 151) \approx -1.74$$

Даже с познавательной точки зрения мы испытываем эту разницу в сложности, когда вычисляем одну и ту же сумму разными способами:

Наблюдение: информационная эффективность не обладает свойством ассоциативности в случае сложения. Если $S$ является конечным множеством натуральных чисел, тогда выражение:

$$\delta\left(\sum_{i \in S} i\right)$$

не определено.

Это частично объясняет, почему так называемая проблема суммы подмножеств (см. раздел 6.3) является трудной. Информационная оптимальность выражений, описывающих суммы подмножеств чисел, не определяется однозначно, а это влияет на возможности поиска в этих множествах. 

Сложение связано с хранением информации посредством последовательностей или строк символов.  Это сбрасывает информацию для натуральных чисел больше 1. У нас есть $\delta(a+ b) \lt 0$, поскольку $\log (a + b) \lt \log a + \log b$. Тем не менее сложение обладает и свойствами сохранения информации. Если мы добавим числа с разными логарифмическими единицами, мы можем восстановить частоту единиц из полученного числа:

Поскольку информация в строительных блоках — 100, 10 и 1 — дана, числовое представление еще можно восстановить. Это означает, что натуральные числа в принципе кодируют посредством сложения степеней $k$ два вида информации: числовое значение и частоту. Мы можем использовать это для кодирования сложных типов информации в единичных натуральных числах. В основном это позволяет кодировать любые натуральные числа в виде строки символов длиной $\lceil \log_k n \rceil$, которая определяет количественную меру величины информации в числе с точки зрения длины его кода. См. раздел 3.3, где приведен исторический анализ важности открытия позиционных систем счисления для теории информации.

Умножение по определению сохраняет информацию. Мы имеем: $\delta(a \times b) = 0$, поскольку $\log (a \times b) = \log a + \log b$. Тем не менее умножение не сохраняет всю информацию, имеющуюся на входе: порядок операции теряется. Но это именно то, что нам нужно от оператора, характеризующего экстенсивную меру: сохраняются только экстенсивные качества чисел. Если мы умножим два числа $3 × 4$, то результат $12$ позволит нам восстановить исходное вычисление, поскольку мы можем привести все его компоненты к их самым элементарным значениям: $2 × 2 × 3 = 12$ . Это приводит к наблюдению, что некоторые числа действуют как информационные строительные блоки других чисел, что дает нам понятие простого числа:         

Определение: простое число — это число, которое делится только на себя или на 1. 

Понятие простого числа приводит к основной теореме арифметики: 

Теорема: каждое натуральное число $n$, большее чем $1$, является либо простым числом, либо произведением мультимножества $A_p$ простых чисел, причем это мультимножество является уникальным для $n$ .

Множители числа образуют так называемое мультимножество: набор, который может содержать несколько копий одного и того же элемента — например, число $12$ определяет мультимножество $\{2,2,3\}$, в котором число $2$ встречается дважды. Это делает мультимножества мощным устройством для кодирования информации, поскольку они кодируют качественную информацию (то есть числа $2$ и $3$), а также количественную информацию (то есть тот факт, что число $2$ встречается дважды, а число $3$ — только один раз). Сказанное подразумевает, что, с точки зрения умножения простых чисел, натуральные числа также кодируют два типа информации: числовое значение и частоту. И мы вновь можем использовать это для кодирования сложных типов информации в единичных натуральных числах.

Информация, простые числа и множители

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

(Не)регулярность множества простых чисел

Со времен античности известно, что существует бесконечное количество простых чисел. Доказательство простое. Предположим, что множество простых чисел $P$ конечно. Теперь перемножьте все элементы из $P$ и добавьте $1$. Полученное число не может быть разделено ни на один член $P,$ поэтому множество $P$ является неполным. Оценка распределения плотности простых чисел по числовому ряду приведена в Теореме о простых числах. В ней утверждается, что промежутки между простыми числами на множестве натуральных чисел размера n имеют примерное значение ln $n$, где ln — натуральный логарифм, основанный на числе Эйлера $e$. Уточнение оценки плотности дает так называемая гипотеза Риманна, сформулированная им в 1859 году (Goodman and Weisstein 2019), считающаяся глубочайшей нерешенной проблемой в математике, хотя большинство математиков считают эту математическую гипотезу истинной.

(Не)оптимальность факторизации

Поскольку умножение сохраняет информацию, функция до некоторой степени обратима. Процесс поиска уникального набора простых чисел для определенного натурального числа $n$ называется факторизацией. Обратите внимание, что использование термина «только» в определении простого числа подразумевает, на самом деле, отрицательную характеристику: число $n$ является простым, если не существует числа между 1 и $n$, способного выступить в качестве делителя. Это обстоятельство дает нам эффективную (effective) процедуру факторизации ряда $n$ (просто попробуйте разделить $n$ на все числа от $1$ до $n$), но такие методы не оптимальны (efficient).   

Если мы используем позиционную систему счисления для представления числа n, тогда процесс определения множителей $n$ методом проб и ошибок займет у детерминированной компьютерной программы максимум $n$ испытаний — а это дает экспоненциальное время вычисления по длине представления числа, которое равно $\lceil \log n \rceil$. Факторизация методом проб и ошибок сравнительно простого числа, — скажем, состоящего из двухсот цифр, которое кодирует довольно маленькое сообщение, — легко может занять у компьютера размером со всю нашу вселенную больше времени, чем прошло с момента Большого взрыва. Таким образом, даже будучи теоретически возможными, подобные алгоритмы совершенно непрактичны. 

Факторизация, возможно, является примером так называемой взаимно-однозначной «функции с секретом» (trapdoor one-to-one function), которая легко вычисляется в одну сторону, но с очень большим трудом — в обратную. Остается открытым вопросом, является ли факторизация действительно сложной, хотя большинство математиков считают эту проблему трудной. Обратите внимание, что факторизацию в данном контексте можно рассматривать как процесс декодирования сообщения. Если факторизация сложна, ее можно использовать как метод шифрования. Классическое шифрование основано на умножении кодов с большими простыми числами. Предположим, что у Алисы есть сообщение, закодированное как большое число $m$, и она знает, что у Боба есть доступ к большому простому числу $p$. Она отправляет число $p × m = n$ Бобу. Так как Бобу известно число $p$, он может легко восстановить $m$, вычислив $m = n / p$. Так как факторизация сложна, для любого другого человека, получившего сообщение $n$, восстановить значение $m$ окажется непосильным трудом.

Тестирование первичности vs. факторизация

Хотя в настоящий момент неизвестно, существуют ли оптимальные методы факторизации на классических компьютерах, существует оптимальный алгоритм, способный решить, является ли число простым или нет: так называемый тест простоты AKS (Agrawal et al. 2004). Так что мы можем знать, что некоторое число не является простым, даже если у нас все еще нет доступа ко множеству его множителей.

Классические vs. квантовые вычисления

Теоретически, факторизация является оптимальной на квантовых компьютерах с использованием алгоритма Шора (Shor 1997). Этот алгоритм имеет неклассическую квантовую подпрограмму, встроенную в детерминированную классическую программу. Массив квантовых битов можно моделировать посредством комплексных многомерных векторных пространств, что в принципе позволяет анализировать экспоненциальное число $2^n$ корреляций между массивами из $n$ объектов. В настоящее время не ясно, будут ли большие квантовые компьютеры достаточно стабильны, чтобы получить практическое применение. Впрочем, больше не может быть подвергнуто сомнению то обстоятельство, что мир на квантовом уровне имеет соответствующие вычислительные возможности: например, квантовые генераторы случайных чисел доступны в качестве коммерческого продукта (см. в Википедии статью «Аппаратный генератор случайных чисел»). Как только жизнеспособные квантовые компьютеры станут доступными, почти все существующие методы шифрования станут бесполезными, хотя они и могут быть заменены квантовыми версиями методов шифрования

Наблюдение: существование бесконечного набора простых чисел указывает на следующее – хотя множество натуральных чисел $\mathbb{N}$ определяется в соответствии с аксиомами Пеано, характеристика данного множества с их помощью является фундаментально неполной. 

Мы можем сделать бесконечное количество наблюдений относительно множества $\mathbb{N}$, которые не подразумеваются аксиомами напрямую, но требуют значительных вычислений.   

Неполнота арифметики

В исторической работе 1931 года Курт Гёдель доказал, что любая непротиворечивая формальная система, содержащая элементарную арифметику, является фундаментально неполной — в том смысле, что она содержит истинные утверждения, которые не могут быть доказаны внутри системы. В философском контексте это означает следующее: семантика формальной системы, — достаточно богатая, чтобы содержать элементарную математику, — не может быть определена посредством математических функций внутри самой системы. Иными словами, существуют утверждения, которые содержат семантическую информацию о системе, будучи правильно сформированными, значимыми и истинными, но не будучи вычислимыми.   

Ключевой здесь является концепция рекурсивной функции. Такие функции определены на области чисел. Понятие Гёделя о рекурсивной функции наиболее близко к тому, что мы связываем с вычислениями в повседневной жизни. По сути это элементарные арифметические функции, работающие на натуральных числах: такие как сложение, вычитание, умножение и деление, а также все другие функции, которые могут быть определены поверх них.     

Здесь мы приводим лишь базовую структуру доказательства. Предположим, что $F$ — формальная система, состоящая из следующих компонентов:

• Она имеет конечный набор символов.
• Она имеет синтаксис, который позволяет нам комбинировать символы в правильно сформированные формулы.
• Она содержит набор детерминированных правил, позволяющих нам получать новые утверждения из данных утверждений.
• Она содержит элементарную арифметику, определяемую аксиомами Пеано (см. раздел 5.1.3 выше).

Кроме того, предположим, что $F$ является непротиворечивой системой, т.е. она никогда не выведет ложные утверждения из истинных. В своем доказательстве Гёдель использовал кодирующие возможности умножения для построения образа системы (см. обсуждение нумерации Гёделя из статьи о теоремах Гёделя о неполноте). Согласно основной теореме арифметики, любое число может быть однозначно разложено на простые числа. Это определяет взаимно-однозначное отношение между мультимножествами чисел и самими числами: число 12 может быть построено на основе мультимножества $\{2,2,3\}$ как $12 = 2 × 2 × 3$, и наоборот. Это позволяет нам кодировать любую последовательность символов в виде конкретного индивидуального числа следующим образом: 

• Уникальный номер присваивается каждому символу.
• Простые числа определяют местоположение символа в строке.
• Фактическое число одинаковых простых чисел в составе множества простых множителей определяет символ.

На основании этих правил мы можем закодировать любую последовательность символов в виде так называемого гёделева номера, например, число:

$$2 × 3 × 3 × 5 × 5 × 7 = 3150$$

кодирует мультимножество $\{2,3,3,5,5,7\}$ , которое представляет строку «abba» в предположении $a=1,$ $b=2$. При этом отметим, что удовлетворяются и условия, близкие к тем, что приводят к парадоксу Рассела: сама элементарная арифметика достаточно богата, чтобы выразить универсальность, отрицание и самоференцию.           

Теорема: Любая формальная система, содержащая элементарную арифметику, принципиально неполна. Она содержит утверждения, которые являются истинными, но не доказуемыми.  

В контексте философии информации неполнота математики является прямым следствием богатства возможностей натуральных чисел кодировать информацию. В принципе любая детерминированная формальная система может быть представлена ​​посредством элементарных арифметических функций. Следовательно, если сама такая система содержит арифметику как подсистему, она содержит бесконечную цепочку эндоморфизмов (т.е. образов себя). Такая система способна рассуждать о своих собственных функциях и доказательствах, но, поскольку она непротиворечива (а следовательно, в системе невозможно построить парадоксы), она по необходимости является неполной.

Информационные и символические вычисления

Рекурсивные функции — это абстрактные отношения, определенные на натуральных числах. В принципе они могут быть определены без каких-либо ссылок на пространство и время (т.е. физические характеристики). Такие функции следует отличать от операций, которые мы используем для их вычисления. Эти операции в основном зависят от типа символических представлений, которые мы для них выбираем. Мы можем представить число семь в виде унарного числа $|||||||$, двоичного числа $111$, римского числа $VII$ или арабского числа $7$ — и в зависимости от нашего выбора различные типы последовательных манипуляций с символами становится возможным использовать для вычисления сложения «два плюс пять — семь», которое может быть представлено как:      

Следовательно, мы можем прочитать эти четыре предложения как четыре утверждения об одной и той же математической истине — или же как утверждения, определяющие результаты четырех разных операций.

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

1. Парадигма рекурсивной функции изучает вычисления в терминах абстрактных функций на натуральных числах вне пространства и времени. Интерпретируя следующее выражение как математический факт, знак «$+$» в $10 + 101 = 111$ означает математическую функцию, называемую сложением, а знак «$=$» обозначает равенство.
2. Парадигма манипулирования символами изучает вычисления в терминах последовательных операций на пространственных представлениях строк символов. Если интерпретировать следующее выражение как операцию, знак «$+$» в $10 + 101 = 111$ означает ввод для последовательного процесса манипуляции символами, а знак «$=$» обозначает результат этой операции, или же вывод. Такой алгоритм может иметь следующую форму:
   
   $$\begin{aligned} \tt{ 10}\\ \tt{+ 101} \\ \hline \tt{ 111} \end{aligned}$$

Сказанное приводит к следующему предварительному определению:

Определение: Детерминированные вычисления в макроскопическом масштабе могут быть определены как локальные последовательные манипуляции с дискретными объектами в соответствии с детерминированными правилами.

В природе также существует много других способов выполнения подобных вычислений. Можно было бы использовать счеты, изучать химические процессы или просто манипулировать последовательностями, составленными из гальки на пляже. Тот факт, что объекты наших манипуляций дискретны, вместе с наблюдением, что набор данных является самоотносимым, подразумевает, что область данных в принципе является Дедекинд-бесконечной:

Определение: Множество $S$ является Дедекинд-бесконечным, если оно имеет биекцию $f: S \rightarrow S^{\prime}$ такую, что правильное подмножество $S^{\prime} \subset S$.

Поскольку элементы данных дискретны и конечны, область данных будет счетно бесконечной и, следовательно, изоморфной множеству натуральных чисел.

Определение: Бесконечное множество $S$ является счетным, если существует его биекция со множеством натуральных чисел $\mathbb{N}$.   

Для бесконечных счетных множеств понятие информации определяется следующим образом:

Определение: Пусть $S$ счетное и бесконечное, а функция $f:S \rightarrow \mathbb{N}$ определяет взаимно-однозначное соответствие, тогда:
$$I(a\mid S,f) = \log f(a),$$
т.е. количество информации в индексе $a$ в $S$ задается $f$.

Обратите внимание, что соответствие для $f$ указано эксплицитно. Как только такая индексальная функция определена для класса объектов в реальном мире, манипулирование этими объектами можно интерпретировать как форму вычисления.

Машины Тьюринга

Как только мы выбрали свои символы и свои правила для операций, система начинает производить утверждения о мире.

Наблюдение: Мета-предложение:

определяет семантическую информацию в том же смысле, что и выражение $e \in A$ для множеств (см. раздел 6.6 ). Утверждение является правильно сформированным, значимым и истинным.

В целом мы можем изучать манипулирование символами на абстрактном уровне, без каких-либо смысловых импликаций. Подобного рода теория была опубликована Аланом Тьюрингом (1912–1954). Тьюринг разработал общую теорию вычислений, сосредоточив внимание на реальных операциях с символами, которые выполняет математик (Turing 1936). Для него компьютер являлся абстракцией настоящего сидящего за столом математика, получающего в корзину для входящих бумаг записанные проблемы (ввод), решающего их в соответствии с установленными правилами (процесс) и оставляющего их для дальнейшего забора в корзине для исходящих бумаг (вывод).

Тьюринг впервые сформулировал понятие общей теории вычислений, следуя схожей линии мысли. Он предложил рассуждать об абстрактных машинах, которые работают на бесконечных лентах с тремя символами: пробел $(b)$, ноль $(0)$ и один $(1)$. Следовательно, область данных для машин Тьюринга — это набор соответствующих конфигураций ленты, которые могут быть связаны со множеством двоичных строк, состоящих из нулей и единиц. Машины могут читать и записывать символы на ленте, а также у них есть функция перехода, которая определяет их действия в различных условиях. На абстрактном уровне машины Тьюринга работают как функции.

Определение: Если $T_i$ - машина Тьюринга с индексом $i$, а $x$ — строка нулей и единиц на ленте, которая функционирует как ввод, тогда $T_i(x)$ обозначает конфигурацию ленты после остановки машины, т.е. вывод.

Существует бесконечное количество машин Тьюринга. Тьюринг обнаружил, что существуют так называемые универсальные машины Тьюринга $U_j$, которые могут эмулировать любую другую машину Тьюринга $T_i$.     

Определение: Выражение $U_j(\overline{T_i}x)$ обозначает результат эмуляции вычисления $T_i(x)$ на $U_j$ после прочтения саморазграничивающего описания  $\overline{T_i}$ машины $T_j$. 

Саморазграничивающий код необходим, потому что входные данные для $U_j$  кодируются как одна строка $\overline{T_i}x$. Универсальная машина $U_j$ разделяет входную строку $\overline{T_i}x$ на две составляющие ее части: описание машины $\overline{T_i}$ и вход для этой машины $x$.

Это приводит к предположению о возможности существования «супермашины», которая эмулирует все возможные вычисления на всех возможных машинах и предсказывает результат их работы. Используя технику, называемую диагонализацией (позволяющей проанализировать перечисление всех возможных машин, работающих по описаниям всех возможных машин), Тьюринг доказал, что такая машина не может существовать. Более формально:

Теорема: не существует такой машины Тьюринга, которая предсказывала бы для любой другой машины Тьюринга, останавливается ли та, получив определенный ввод, или нет.

Это подразумевает, что для некоторой универсальной машины $U_i$ невычислимо множество вводов, получив которые она останавливается за конечное время. Не всякая машина остановится на любом вводе.

Определение: Множество остановки — это множество комбинаций машин Тьюринга $T_i$ и вводов $x$ таких, что вычисление $T_i(x)$ останавливается.   

Существование универсальных машин Тьюринга указывает на то, что рассматриваемый класс воплощает понятие универсальных вычислений: любое вычисление, которое может быть выполнено на конкретной машине Тьюринга, также может быть выполнено на любой другой универсальной машине Тьюринга. Это задает математическую основу концепции общего программируемого компьютера. Приведенные наблюдения имеют отношение к теории информации: определенные меры информации, — такие как колмогоровская сложность, — определены, но невычислимы. 

Доказательство существования невычислимых функций в классе машин Тьюринга аналогично результату Гёделя о неполноте в случае элементарной арифметики. Коль скоро машины Тьюринга были определены для изучения понятия вычисления, они тем самым содержат элементарную арифметику. Класс машин Тьюринга сам по себе достаточно богат, чтобы выразить универсальность, отрицание и самоотносимость. Следовательно, машины Тьюринга могут моделировать универсальные негативные утверждения о себе. Проделанное Тьюрингом доказательство невычислимости также мотивировано парадоксом лжеца, а понятие останавливающейся на определенном вводе машины аналогично понятию доказательства, которое существует для определенного утверждения. В то же время машины Тьюринга удовлетворяют условиям теоремы Гёделя: их можно моделировать как формальную систему $F$, которая содержит элементарную арифметику Пеано.

Наблюдение: поскольку взаимная эмуляция возможна, парадигма рекурсивных функций и парадигма манипулирования символами имеют одинаковую вычислительную силу. Любая функция, которая может быть вычислена в одной парадигме, также по определению может быть вычислена и в другой.

Это понимание может быть обобщено:

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

Из этого наблюдения прослеживаются сильные и далекоидущие философские следствия, богатые не только с точки зрения теории вычислений, но и для нашего понимания концепции информации.

Универсальность и инвариантность

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

Малая теорема об инвариантности: Понятие информации в строке $x$, измеряемой как длина наименьшей строки символов s программы для универсальной машины Тьюринга $U$ такой, что $U(s)=x$, является асимптотически инвариантным при выборе различных универсальных машин Тьюринга

Доказательство: Доказательство этого просто и актуально для философии информации. Пусть $l(x)$ — длина строки символов $x$. Предположим, у нас есть две разные универсальные машины Тьюринга $U_j$ и $U_k$. Поскольку они универсальны, они обе могут эмулировать вычисление $T_i(x)$ машины Тьюринга $T_i$ с $x$ на вводе:

$$U_j(\overline{T}_i^jx)  \\U_k(\overline{T}_i^kx)$$

Здесь $l(\overline{T}_i^j)$ — длина кода $T_i$ на $U_j$, а $l(\overline{T}_i^k)$ — длина кода для $T_i$ на $U_k$. Пусть $l(\overline{T}_i^jx) \ll l(\overline{T}_i^kx)$, т.е. код для $T_i$ на $U_k$ намного менее оптимален, чем на $U_j$. Заметим, что сам код для $U_j$ имеет постоянную длину, т.е $l(\overline{U}_j^k)=c$. Поскольку $U_k$ является универсальной машиной, осуществимо вычисление: 

$$U_k(\overline{U}_j^k \ \overline{T}_i^jx)$$

Длина ввода для этого вычисления составляет:

$$l(\overline{U}_j^k \ \overline{T}_i^jx) = c + l(\overline{T}_i^jx)$$

Следовательно, спецификация вводных данных для вычисления $T_i(x)$ на универсальной машине $U_k$ никогда не должна быть длинее некоторой константы. $\Box$      

Это доказательство лежит в основе теории колмогоровской сложности и первоначально принадлежит Соломонову (Solomonoff 1964а, b), а открыто оно было независимо друг от друга Колмогоровым (Kolmogorov 1965) и Хайтиным (Chaitin 1969). Обратите внимание, что это понятие инвариантности может быть обобщено на класс полных по Тьюрингу систем:

Большая теорема об инвариантности: Понятие информации, измеряемой в терминах длины вводных данных для вычисления, асимптотически инвариантно для полных по Тьюрингу систем. 

Доказательство: Предположим, что мы имеем полную по Тьюрингу систему $F$. По определению, любое вычисление $T_i(x)$ на машине Тьюринга можно эмулировать в $F$ и наоборот. Пусть будет специальная универсальная машина Тьюринга $U_F$, которая эмулирует вычисления $T_i(x)$ в $U_F(\overline{T}_i^Fx)$. В принципе $\overline{T}_i^F$ может использовать крайне неоптимальный способ кодирования программ, так что $\overline{T}_i^F$ может иметь любую длину. Заметим, что код любой другой универсальной машины $U_j$, эмулируемой $U_F$, имеет постоянную длину, т.е. $l(\overline{U}_j^F)=c$. А, поскольку $U_F$ является универсальным, мы также можем вычислить: 

$$U_F(\overline{U}_j^F \ \overline{T}_i^jx)$$

Длина ввода для этого вычисления составляет:

$$l(\overline{U}_j^F \ \overline{T}_i^jx) = c + l(\overline{T}_i^jx)$$

Следовательно, спецификация вводных данных для вычисления $T_i(x)$ на универсальной машине UF никогда не должна быть длинее некоторой константы. $\Box$

То, насколько сильный этот результат, становится ясно, когда мы более подробно проанализируем класс Тьюринг-полных систем.

Каждый из этих подходов по-своему проясняет аспекты понятия вычисления. Позже возникло еще больше примеров. Класс эквивалентных по Тьюрингу систем весьма разнообразен. Помимо очевидных кандидатов — таких как все языки программирования общего назначения (C, Fortran, Prolog и пр.) — он также содержит и некоторые неожиданные элементы, в частности, различные игры (например, Magic: The Gathering [Churchill 2012]). Таблица ниже дает обзор некоторых концептуально интересных систем:

Обзор некоторых Тьюринг-полных систем

Отсюда мы делаем следующее:

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

Прямым следствием этого наблюдения будет:

Наблюдение: Общая теория вычислений и информации, определяемая классом машин Тьюринга, является онтологически нейтральной.

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

Тезис Черча-Тьюринга: класс машин Тьюринга характеризует понятие алгоритмических вычислений в точности. 

Мы приводим обзор аргументов за и против данного тезиса:

Аргументы в пользу тезиса: Теория машин Тьюринга, по-видимому, является наиболее общей теорией, которую мы можем сформулировать, так как она основана на крайне ограниченном наборе предположений о том, что такое вычисления. Тот факт, что она универсальна, также указывает на ее общность. Трудно представить, в каком смысле более мощная система могла бы быть «более» универсальной. Даже если бы мы могли думать о такой более мощной системе, ввод и вывод такой системы должны быть конечными и дискретными, равно как было бы конечным и время вычислений. Итак, в конце концов, любое вычисление будет иметь вид конечной функции между конечными наборами данных — а в принципе все подобные отношения можно промоделировать на машинах Тьюринга. Тот факт, что все известные нам системы вычислений, которые до сих пор были определены, имеют одинаковую мощность, также подтверждает тезис.

Аргументы против тезиса: Тезис в его нынешнем виде недоказуем. Класс Тьюринг-полных систем является открытым. Он определяется на основе существования отношений эквивалентности между системами. В этом смысле он не определяет понятие вычисления по существу. Это не дает нам философской теории, которая бы определяла, что в точности такое вычисления. Следовательно, это не позволяет нам априори исключать какую-либо систему из класса. В любое время может появиться подход к понятию вычисления, который будет существенно сильнее. Более того, природа предоставляет нам более сильные понятия вычислений в виде квантовых вычислений. Квантовые биты на самом деле являются обобщением обычной концепции битов, которая связана с манипулированием символами, хотя в итоге квантовые вычисления до сих пор не потребовали от нас переопределять понятие вычисления. Впрочем, мы никогда не можем исключать, что исследования в области физики, биологии или химии определят системы, которые заставят нас сделать это. Действительно, разные авторы предлагали такие системы, но в настоящее время насчёт убедительных кандидатов нет единого мнения (Davis 2006). Дершовиц и Гуревич (Dershowitz and Gurevich 2008) утверждают, что подтвердили гипотезу, подразумеваемую тезисом Чёрча — Тьюринга, но их результат не является общепринятым (см. обсуждение «Вычислимость — что бы значило опровергнуть тезис Черча-Тьюринга» на англ.).

«Быть Тьюринг-полной» кажется вполне естественным условием для (формальной) системы. Любая достаточно богатая для представления натуральных чисел и элементарных арифметических операций система полна по Тьюрингу. Требуется конечное множество операций, определенных на множестве дискретных конечных элементов данных, которое было бы достаточно богатым, чтобы сделать систему самореференциальной: тогда ее операции могут быть описаны ее же элементами данных. Это частично объясняет, почему мы способны использовать математику для описания нашего мира. Абстрактное понятие вычисления, определяемое как функции на числах в абстрактном мире математики, и конкретное понятие вычисления с помощью манипулирования объектами в повседневном мире вокруг нас, совпадают. Концепции вычисления и информации, подразумеваемые парадигмой рекурсивных функций и парадигмой манипулирования символами одинаковы. 

Наблюдение: если принять тот факт, что тезис Чёрча — Тьюринга является открытым, это будет означать также открытость вопроса о существовании универсального понятия информации. На данном этапе исследования невозможно определить априорные условия для теории такой степени общности.    

Квантовая информация и за ее пределами

На сегодняшний день у нас есть внятное понимание концепции классических вычислений, однако следствия для области вычислений и информации из квантовой физики могут определять программу философских исследований на десятилетия, если не дольше. Тем не менее уже ясно, что подобное исследование оказывает влияние на традиционные философские позиции: представление Лапласа (1999) о том, что вселенная по сути детерминирована, сфальсифицировано эмпирическими наблюдениями. Квантовые генераторы случайных чисел стали коммерчески доступными (см. в Википедии статью «Аппаратный генератор случайных чисел»), а квантовые флуктуации воздействуют на неврологические, биологические и физические процессы в макроскопическом масштабе (Albrecht & Phillips 2014).

Стандартные вычисления в макроскопическом масштабе могут быть определены как локальные, последовательные манипуляции с дискретными объектами в соответствии с детерминированными правилами. У них есть естественная интерпретация в виде операций над множеством натуральных чисел $N$ и естественная функция меры, заданная логарифмической операцией $\log: \mathbb{N} \rightarrow \mathbb{R}$, связывающая действительные числа с каждым натуральным числом. Такое определение дает нам адекватную информационную меру для счетных бесконечных множеств, — включая такие классы чисел, как целые числа $\mathbb{Z}$, замкнутые при вычитании, и рациональные числа $\mathbb{Q}$, замкнутые при делении.

Операция умножения с соответствующей логарифмической функцией характеризует нашу интуицию об аддитивности понятия информации. Это приводит к естественной биекции между множеством натуральных чисел $\mathbb{N}$ и множеством мультимножеств чисел (т.е. множествами из простых множителей). Понятие мультимножества связано со свойствами коммутативности и ассоциативности. Эта схема может быть расширена на другие классы чисел, когда мы изучаем алгебры с делением в более высоких размерностях. В следующей таблице приведен обзор некоторых соответствующих классов чисел вместе со свойствами определенной для них операции умножения:

Таблица упорядочена исходя из логики возрастающей общности. Если отталкиваться от множества натуральных чисел  $\mathbb{N}$, возможны различные расширения (с учетом замыкания при вычитании, $\mathbb{Z}$, и при делении, $\mathbb{Q}$). Это классы чисел, для которых у нас есть адекватные конечные символические представления в макроскопическом масштабе. Для элементов действительных чисел $\mathbb{R}$ такие представления недоступны. Действительные числа $\mathbb{R}$ вводят компонент манипулирования бесконечными объемами информации в одной операции.            

Наблюдение: Для практически всех $e \in \mathbb{R}$ мы имеем $I(e) = \infty$.       

Более сложные алгебры с делением могут быть определены, когда мы вводим мнимые числа в виде отрицательных квадратов $i^2 = -1$. Теперь мы можем определить комплексные числа: $a + bi$, где $a$ — действительная часть и $bi$ — мнимая часть. Комплексные числа можно интерпретировать как векторы в двумерной плоскости. Следовательно, они теряют такую характеристику, как понятие строгого линейного порядка между символами. Сложение осуществляется довольно просто:

$$(a + bi) + (c + di) = (a + b) + (c + d)i$$

Умножение следует правилу нормального распределения, но результат этой операции теперь менее интуитивен, так как включает отрицательный член, сгенерированный $i^2$: 

$$(a + bi) (c + di) = (ac - bd) + (bc + ad)i$$

В этом контексте умножение перестает быть чисто экстенсивной операцией:

Наблюдение: умножение мнимых чисел является информационно неоптимальным. В частности, равенство $\sqrt{xy} = \sqrt{x} \sqrt{y}$ не выполняется, как это видно из следующего примера:   

$$1 = \sqrt{1}= \sqrt{-1 \times -1} \neq \sqrt{-1} \sqrt{-1}= i \times i = -1$$

Могут быть определены и более сложные системы счисления с обобщениями данного типа умножения в 4 и 8 измерениях. Кервайр (Kervaire 1958), а также Ботт и Мильнор (Bott & Milnor 1958) независимо доказали, что единственными четырьмя алгебрами деления, построенными на действительных числах, являются $\mathbb{R}$, $\mathbb{C}$, $\mathbb{H}$ и $\mathbb{O}$, поэтому таблица дает полное представление обо всех возможных алгебрах, которые определяют понятие экстенсивности. Для каждого из классов чисел в таблице может быть разработана отдельная теория измерения информации, основанная на свойствах умножения. Для счетных классов $\mathbb{N}$, $\mathbb{Z}$ и $\mathbb{Q}$ эти теории эквивалентны стандартной концепции информации, подразумеваемой понятием эквивалентности по Тьюрингу. Вплоть до действительных чисел эти теории удовлетворяют нашим интуитивным представлениям об экстенсивности информации. Для комплексных чисел понятие информационной оптимальности умножения разрушено. У кватернионов отсутствует свойство коммутативности, а у октонионов — еще и ассоциативность. Эти модели являются не просто абстрактными конструкциями, так как соответствующие алгебры играют важную роль в наших описаниях природы:

1. Комплексные числа используются для построения математических моделей квантовой физики (Nielsen & Chuang 2000).
2. Кватернионы выполняют ту же роль в специальной теории относительности Эйнштейна (De Leo 1996).
3. Некоторые физики считают, что октонионы образуют теоретическую основу для единой теории сильных и электромагнитных взаимодействий (например, Furey 2015).

Мы кратко обсудим применение векторных пространств в квантовой физике. Классическая информация измеряется в битах. Реализация битов в природе включает в себя макроскопические физические системы с по крайней мере двумя различными стабильными состояниями и процессом обратимого перехода с низкой энергией (т.е. переключатели, реле, транзисторы). Наиболее фундаментальный способ хранения информации в природе на атомном уровне включает в себя кубиты. Кубит описывается вектором состояния в двухуровневой квантово-механической системе, которая формально эквивалентна двумерному векторному пространству над комплексными числами (фон Нейман 1964; Nielsen & Chuang 2000). Квантовые алгоритмы в некоторых случаях имеют принципиально меньшую сложность (например, алгоритм Шора для факторизации целых чисел (Shor 1997)).

Определение: Квантовый бит, или кубит, является обобщением классического бита. Квантовое состояние кубита представляется в виде линейной суперпозиции двух ортонормированных базисных векторов:

$$\ket{0} = \begin{bmatrix}1 \\ 0 \end{bmatrix}, \ket{1} = \begin{bmatrix}0 \\ 1 \end{bmatrix}$$

Здесь используется так называемый Дирак или понятие «бра-кет»: где $\ket{0}$ и $\ket{1}$ произносятся как «кет 0» и «кет 1». Два вектора вместе образуют вычислительный базис $\{\ket{0}, \ket{1}\}$, который определяет вектор в двумерном гильбертовом пространстве. Сочетание $n$ кубитов представлено вектором суперпозиции в $2^n$-мерном гильбертовом пространстве, например:

$$\ket{00} = \begin{bmatrix}1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \ket{01} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \ket{10} = \begin{bmatrix}0 \\ 0 \\ 1 \\ 0 \end{bmatrix}, \ket{11} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$

Чистый кубит — это когерентная суперпозиция базисных состояний:   

$$\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$$

где $\alpha$ и $\beta$ — комплексные числа, подчиняющиеся следующему ограничению: 

$$|\alpha|^2 + |\beta|^2 = 1$$

Таким образом, значения компонентов могут быть интерпретированы как вероятности: $|\alpha|^2$ — вероятность того, что кубит имеет значение $0$ и $ |\beta|^2$ — вероятность того, что кубит имеет значение $1$. 

В рамках этой математической модели наша интуиция о вычислениях как локальных последовательных манипуляциях с дискретными объектами в соответствии с детерминированными правилами развивается в гораздо более богатую парадигму:

1. Бесконечная информация. Внедрение действительных чисел облегчает манипулирование объектами бесконечной описательной сложности, хотя в настоящее время нет никаких указаний на то, что подобная выразительность действительно необходима в квантовой физике.
   
2. Неклассическая вероятность. Комплексные числа способствуют принятию более широкого понятия экстенсивности, в котором вероятности перестают быть классическими. Третья аксиома Колмогорова теряет свою актуальность в пользу усиливающих или подавляющих друг друга вероятностей, в результате чего теряется экстенсивность информации.
3. Суперпозиция и запутанность. Представление кубитов посредством комплексных многомерных векторных пространств подразумевает, что кубиты перестают быть изолированными дискретными объектами. Квантовые биты могут находиться в суперпозиции — т.е. в ситуации, когда они находятся в двух дискретных состояниях одновременно. Квантовые биты флуктуируют и, следовательно, они генерируют информацию. Более того, квантовые состояния кубитов могут коррелироваться, даже когда носители информации разделены большим расстоянием в пространстве. Известное как запутанность, это явление разрушает свойство локальности классических вычислений.

Из анализа выше ясно, что описание нашей вселенной на очень малых (и очень больших) масштабах включает в себя математические модели, чуждые нашему опыту реальности в повседневной жизни. Свойства, которые позволяют нам понять мир (наличие устойчивых дискретных объектов, которые сохраняют своё тождество в пространстве и времени), похоже, являются эмерджентными аспектами гораздо более сложной реальности — непостижимой для нас за пределами ее математических описаний. Тем не менее на макроскопическом уровне вселенная «потворствует» элементарным процессам — таким как подсчет, измерение длины и манипулирование символами, — которые позволяют нам разработать последовательную иерархию математических моделей, и некоторые из них, похоже, описывают и более глубокую структуру реальности.

В некотором смысле те же математические свойства, которые привели к развитию элементарных систем учета в Месопотамии четыре тысячи лет назад, все еще помогают нам проникать в мир субатомных структур. В последние десятилетия информация стала жизненно важной концепцией в физике. Сет Ллойд и другие (Zuse 1969; Wheeler 1990; Schmidhuber 1997b; Wolfram 2002; Hutter 2010) проанализировали вычислительные модели различных физических систем. Понятие информации играет важную роль в анализе черных дыр (Lloyd & Ng 2004; Bekenstein 1994). Эрик Верлинде (Verlinde 2011, 2017) предложил теорию, в которой гравитация анализируется с точки зрения информации. На данный момент эти модели кажутся чисто описательными без какой-либо возможности эмпирической проверки.

Аномалии, парадоксы и проблемы

Некоторые из фундаментальных вопросов философии информации тесно связаны с существующими философскими проблемами, другие выглядят новыми. В этом разделе мы обсудим ряд наблюдений, которые могут определить повестку дня будущих исследований. Некоторые из актуальных вопросов:

1. Существуют ли описания, уникально идентифицирующие объект, но не содержащие всю информацию об объекте, на который ссылаются?
2. Создают ли вычисления новую информацию?
3. Есть ли разница между построением и систематическим поиском?

Со времен Фреге большинство математиков, судя по всему, считают ответ на первый вопрос положительным (Фреге 1997). Описания «Утренняя звезда» и «Вечерняя звезда» связаны со способами идентификации планеты Венера, но они не дают доступа ко всей информации о самом объекте. Если бы они ее давали, тогда открытие «вечерняя звезда на самом деле — тот же объект, что и утренняя звезда» было бы неинформативным. Если мы хотим придерживаться этой позиции, мы вступаем в конфликт, поскольку с точки зрения теории информации ответ на второй вопрос отрицательный (см. раздел 5.1.7). И все же это наблюдение крайне противоречиво, потому что оно подразумевает, что мы никогда не сможем построить новую информацию на основе детерминированных вычислений — что и приводит к третьему вопросу. Данные проблемы группируются вокруг одной из фундаментальных открытых проблем философии информации: 

Открытая проблема. Каково взаимодействие между информацией и вычислениями? 

Вопрос можно перефразировать следующим образом: должны ли мы использовать сложность Колмогорова или Левина (Levin 1973, 1974, 1984) в качестве нашей основной меры информации? Фактически оба варианта приводят к релевантным, но принципиально различным теориям информации. При использовании меры Левина вычисления генерируют информацию, и ответ на три вопроса выше — «да», однако это не так при использовании меры Колмогорова. Поднятые вопросы связаны со многими проблемами как в математике, так и в информатике. Сопряженные вопросы — такие как приближение, вычислимость и частичная информация — также изучаются в контексте областей Скотта (Abramsky & Jung 1994). Ниже мы обсудим некоторые релевантные наблюдения.

Парадокс систематического поиска

Сущность информации заключается в том, что она уменьшает неопределенность. Это наблюдение приводит нас к проблемам, возникающим в непрозрачных контекстах — например, когда мы ищем объект. Трудность такого рода иллюстрирует парадокс Менона: 

Парадокс связан с другими открытыми проблемами в информатике и философии. Предположим, что Джон ищет единорога. Маловероятно, что единороги существуют, поэтому, с точки зрения теории Шеннона, Джон получит много информации, если найдет это животное. И все же, с дескриптивной колмогоровской точки зрения, Джон не получит новую информацию, так как уже знает, что такое единороги. Соответствующий парадокс систематического поиска можно сформулировать следующим образом:   

Пример: В 1742 году Гольдбах предположил, что каждое четное число больше 2 может быть записано как сумма двух простых чисел. До сегодняшнего дня эта гипотеза остается недоказанной. Рассмотрим термин «Первое число, которое нарушает гипотезу Гольдбаха». Он не дает нам всей информации о числе, так как оно может и не существовать. Приставка «первый» гарантирует, что описание, если оно существует, является уникальным и дает нам алгоритм для поиска числа. Это частичное однозначно идентифицирующее описание. Соответствующий алгоритм является эффективным лишь в том случае, если число действительно существует, иначе он будет работать вечно. Если мы найдем число, это будет хорошей новостью, но с точки зрения дескриптивной сложности само число будет совершенно неинтересным, поскольку мы уже знаем требующиеся для его нахождения свойства. Обратите внимание: даже если у нас есть число $n$, являющееся контрпримером к гипотезе Гольдбаха, может оказаться трудным осуществить проверку этого факта: возможно, нам придется проверить почти все простые числа $\leq n$. Такую проверку можно сделать эффективно (т.е. процедурно, и мы всегда получим результат), но, насколько нам известно, не оптимально (так как она может потребовать «примерно» $n$ различных вычислений).

Возможное решение в данном случае — указать ограничение, что измерять информационное содержание объекта посредством частичных описаний незаконно, однако это разрушит нашу теорию дескриптивной сложности. Обратите внимание, что сложность объекта — это длина самой короткой программы, которая создает объект на универсальной машине Тьюринга. В этом смысле фраза «первое число, которое нарушает гипотезу Гольдбаха» является прекрасным описанием программы, и она адекватно измеряет дескриптивную сложность такого числа. Краткое описание отражает тот факт, что число, если оно существует, является весьма особенным, — и тем самым оно имеет высокую вероятность появления в некотором математическом контексте.

Существуют отношения, в рамках которых хорошо изучены философские проблемы — такие как онтологический аргумент Ансельма в пользу существования Бога и кантианский контраргумент, утверждающий, что бытие не является предикатом. Чтобы избежать подобных проблем, Рассел предложил интерпретировать уникальные описания экзистенциально (Russell 1905): тогда предложение типа «Король Франции лыс» будет иметь следующую логическую структуру:

$$\exists (x) (KF(x) \wedge \forall (y)(KF(y) \rightarrow x=y) \wedge B(x))$$

Такая интерпретация не помогает нам анализировать проблемы разрешимости, связанные с существованием. Предположим, предикат $L$ верен для $x$, если я ищу $x$; тогда логическая структура фразы «я ищу короля Франции» будет следующей:

$$\exists (x) (KF(x) \wedge \forall (y)(KF(y) \rightarrow x=y) \wedge L(x)),$$

т.е., если короля Франции не существует, то, что я его ищу, не может быть правдой, что неудовлетворительно. Крипке (1982) раскритиковал решение Рассела и предложил свою так называемую каузальную теорию референции, в которой имя получает отсылку к предмету посредством первоначального акта «крещения». Затем оно становится жестким десигнатором, следуя за которым, можно вернуться к этому первоначальному акту благодаря причинно-следственным связям. Таким образом, ad hoc описания вроде «Джон был четвертым человеком, вышедшим из лифта сегодня утром» способны установить семантику для имени.        

В контексте математики и теории информации соответствующая концепция встречается в областях имен, конструктивных предикатов и ad hoc предикатов чисел. Для любого числа в принципе будет бесконечное число истинных утверждений о нем. Поскольку элементарная арифметика неполна, будут существовать также истинные, но недоказуемые утверждения о числах. В пределе лишь исчезающее малая часть чисел будет иметь истинные предикаты, которые действительно сжимают их описание. Рассмотрим следующие утверждения:

• Символ «$8$» — это имя числа восемь.
• Число $x$ — это 1000-е (тысячное) число Фибоначчи.
• Число $x$ — это первое число, которое нарушает гипотезу Гольдбаха.

Первое утверждение просто указывает имя для числа. Второе утверждение дает частичное описание, которое является конструктивным, сжимающим информацию и уникальным. $1000$-е число Фибоначчи имеет $209$ цифр, поэтому описание «$1000$-е число Фибоначчи» гораздо оптимальнее, чем фактическое имя числа. Более того, у нас есть алгоритм для построения числа. Это может быть отнюдь не так для описания в третьем утверждении. Мы не знаем, существует ли первое число, которое нарушает гипотезу Гольдбаха — но если оно есть, описание вполне может быть ad hoc и тем самым не даст нам никакой подсказки для построения числа. Это приводит к предположению, что существуют эффективные в плане сжатия данных ad hoc описания:

Предположение: Существуют числа, которые сжимаются неконструктивными уникальными эффективными описаниями, т.е. достоверность описания можно эффективно проверить, обратившись к числу, но число не может быть эффективно построено из описания — только лишь посредством систематического поиска. 

Предположение является более общим вариантом так называемого тезиса P vs NP (см. раздел 6.3 ). Если заменить термин «эффективный» термином «оптимальный», получится формулировка тезиса $\textrm{P} \neq \textrm{NP}$. 

Эффективный поиск в конечных множествах

Когда мы ограничиваемся эффективным поиском в конечных множествах, проблемы «частичного описания» и «построение vs. поиск» остаются. Кажется естественным предположить, что когда у человека есть определение множества чисел, он также имеет всю информацию о членах множества и его подмножествах, однако это не так. В целом, вычисление количества информации во множестве чисел является крайне нетривиальной проблемой. Мы приводим некоторые результаты:

Лемма. $A$ подмножество $A \subset S$  множества $S $ может содержать больше условной ко множеству информации, чем содержит само множество.

Доказательство: рассмотрим множество $S$ всех натуральных чисел, меньших чем п. Дескриптивная сложность этого множества в битах $\log_2 n + c$. Теперь построим $A$, выбрав половину элементов из $S$ случайным образом. Обратите внимание, что:

$$I(A\mid S)=\log_2 {n \choose {n/2}}$$

У нас есть:

Условная дескриптивная сложность этого множества будет: $I(A\mid S) \approx n + c \gg \log n + c$. $\Box$

Прямым следствием из этого является возможность потерять информацию при объединении двух множеств. Еще более сильный результат таков:

Лемма: Элемент множества может содержать больше информации, чем само множество. 

Доказательство: рассмотрим множество из $S$ натуральных чисел, меньших чем $2^n$. Мощность $S$ равна $2^n$ . Дескриптивная сложность этого множества равна $\log n + c$ битов, но для половины элементов $S$ нам нужно $n$ бит, чтобы их описать. $\Box$

В этом случае описание самого множества крайне сжимаемо, но оно все еще содержит несжимаемые элементы. Когда мы объединяем или разделяем множества чисел, равно как добавляем или удаляем элементы, влияние на объем информации обычно трудно предсказать, а иногда оно может даже не быть вычислимым:

Теорема: Информация не монотонна при заданных теоретических операциях.

Доказательство: Непосредственное следствие из приведенных выше лемм. $\Box$ 

Эти выводы показывают, как понятие информации пронизывает нашу повседневную жизнь. Когда у Джона в кармане два яблока, кажется, что он может делать с ними все, что захочет, тогда как на самом деле, выбрав одно из двух, он создал (новую) информацию. Сопутствующие последствия для проблем поиска очевидны: мы всегда можем эффективно выполнять ограниченный поиск по элементам и множеству подмножеств множества. Следовательно, когда мы ищем такой набор подмножеств посредством частичных описаний, тогда результат генерирует (новую) информацию. Этот анализ prima facie, похоже, заставляет нас признать, что в математике есть простые описания, которые позволяют нам идентифицировать сложные объекты посредством систематического поиска. Когда мы ищем объект, у нас мало информации о нем; когда же мы наконец находим его, наша информация увеличивается до набора полных фактов об искомом объекте. Это противоречит нашим нынешним теориям информации (Шеннон и Колмогоров): согласно им, описание, позволяющее эффективно идентифицировать объект путем детерминированного поиска, содержит всю необходимую информацию об объекте. Временная сложность процесса поиска не имеет значения.

Проблема Р vs. NP, описательная сложность vs. временная сложность исполнения алгоритма

В последние десятилетия математики размышляли над cопряженным вопросом: предположим, что проверить, нашел ли я искомое было бы легко — но насколько сложно было бы найти сам объект? В математике и информатике, судя по всему, существует значительный класс задач разрешимости, которые не могут быть конструктивно решены за полиномиальное время $t(x)=x^c$, где $c$ — постоянная, а $x$ длина ввода, но решаемы лишь путем систематического поиска по большей части пространства решений, что может занять экспоненциальное время, $t(x)=c^x$. Это различие в грубом приближении совпадает с разделением проблем на осуществимые в вычислительном отношении и нет. 

Вопрос о существовании таких проблем был сформулирован как возможная эквивалентность между классом $P$ — задач разрешимости, которые могут быть решены за полиноминальное по отношению ко вводу время, — и классом $NP$ задач, решение которых может быть проверено за полиноминальное по отношению ко вводу время (Garey & Johnson 1979)

Пример: Известным примером класса $NP$ является так называемая проблема суммы подмножеств: существует ли для конечного множества натуральных чисел $S$ подмножество $S^{\prime}\subseteq S$, члены которого суммируются до некоторого числа $k$? Очевидно, что когда некто предлагает в качестве решения этой задачи $X \subseteq S$, мы можем легко проверить, являются ли элементы $X$ суммируемыми до значения $k$, но, возможно, нам придется проверить почти все подмножества $S$ чтобы самим найти такое решение.

Выше приведен пример так называемой задачи разрешимости. Ответ прост: «да» или «нет», но может оказаться трудным найти сам ответ. Заметим, что постановка условного вопроса к $S$ имеет описательную сложность $\log k + c$, тогда как большинство случайных подмножеств $S$ имеют условную описательную сложность $|S|$. Таким образом, любое подмножество $S^{\prime}$, члены которого суммируются до $k$, может иметь большую описательную сложность, чем формулировка проблемы поиска. В этом смысле поиск, по-видимому, генерирует информацию. Проблема же состоит в том, что, если искомое множество существует, процесс поиска ограничен — и, следовательно, эффективен: т.е. фраза «первое подмножество $S$, суммируемое до $k$» является адекватным описанием. Если $\textrm{P} = \textrm{NP}$, то колмогоровская сложность и сложность Левина множества $S′$ будут примерно совпадать; если же $\textrm{P} \neq \textrm{NP}$, то в некоторых случаях $Kt(S^{\prime}) \gg K(S^{\prime})$. Обе позиции — теория, в соответствии с которой поиск генерирует новую информацию, и теория, согласно которой этого не происходит, — контринтуитивны с разных точек зрения.           

Даже будучи крайне сложной, проблема $P$ vs. $NP$ при этом является плодотворным источником исследований в области информатики и математики; относительно же ее философской значимости, впрочем, было опубликовано не так уж много. То, что ее решение может иметь глубокое философское влияние, иллюстрирует цитата Скотта Ааронсона:

Фактически, если $\textrm{P} = \textrm{NP}$, тогда каждый объект, который легко описать и легко проверить, должно быть также легко найти.   

Выбор модели и сжатие данных

В современной научной методологии последовательные аспекты научного процесса формализованы в терминах эмпирического цикла — согласно де Груту (de Groot 1969), в нем выделяются следующие этапы:

1. Наблюдение: Наблюдение явления и исследование его причин.
2. Индукция: Формулировка гипотез — обобщенных объяснений явления.
3. Вывод (дедукция): Формулировка экспериментов, которые проверят гипотезы (т.е. подтвердят их, если они верны, и опровергнут их, если они ложны).
4. Проверка: Процедуры, с помощью которых проверяются гипотезы и собираются данные.
5. Оценка: Интерпретация данных и формулировка теории — абдуктивный довод, который представляет результаты эксперимента в качестве наиболее разумного объяснения данного явления.

В контексте теории информации множество наблюдений будет набором данных, и мы можем строить модели, наблюдая закономерности в этом наборе данных. Наука нацелена ​​на построение истинных моделей нашей реальности. В этом смысле ее можно считать семантической авантюрой.

Лауреат премии Тьюринга Джим Грей назвал развивающуюся дисциплину электронной науки (e-science) четвертой парадигмой науки, управляемой данными (другие парадигмы — эмпирическая, теоретическая и вычислительная). Таким образом, процесс автоматического построения теории на основе данных является частью методологии науки и, следовательно, философии информации (Adriaans & Zantinge 1996; Bell, Hey & Szalay 2009; Hey, Tansley, and Tolle 2009). Многие хорошо известные алгоритмы обучения — такие как индукция по дереву решений, метод опорных векторов, нормализованное информационное расстояние и нейронные сети — используют основанные на энтропии информационные меры для извлечения значимых и полезных моделей из больших баз данных. Само название дисциплины «открытие знаний в базах данных» (ОЗБД) свидетельствует об амбициях программы исследования Больших данных. Мы цитируем:

Большая часть текущих исследований концентрируется на вопросе выбора оптимальной вычислительной модели для имеющегося набора данных. Теория колмогоровской сложности является интересной методологической основой, позволяющей изучать обучение и построение теорий как формы сжатия данных. Интуиция такова: самая короткая теория, которая все еще объясняет данные, также является лучшей моделью для обобщения наблюдений. В этом контексте ключевое различие пролегает между оптимизацией однокомпонентного или двухкомпонентного кода: 

• Оптимизация однокомпонентного кода: методологические аспекты теории колмогоровской сложности станут понятны, если следовать за её определением. Мы начнем с правильно сформированного набора данных $y$ и выберем подходящую универсальную машину $U_j$. Выражение $U_j(\overline{T_i}x)= y$ является истинным предложением, что дает нам информацию о $у$. Первый шаг в развитии теории измерения — навязать всю выразительность инструктивной или процедурной частям предложения путем ограничения до предложений, которые описывают вычисления на пустом вводе:
  $$U_j(\overline{T_i}\emptyset)= y$$      
  Это ограничение необходимо для доказательства инвариантности. Исходя из этого, в принципе бесконечного, класса предложений мы можем измерить длину при представлении в виде программы. Мы выбираем те (а их может быть более одного) предложения вида $\overline{T_i}$, которые являются самыми короткими. Длина $\mathit{l}(\overline{T_i})$ такого кратчайшего описания является мерой информационного содержания $y$. Она является асимптотической в том смысле, что, когда длина набора данных y растет до бесконечности, информационное содержание, присваиваемое выбором другой машины Тьюринга, в пределе никогда не будет меняться больше, чем на константу. Колмогоровская сложность измеряет информационное содержание набора данных в терминах кратчайшего описания множества инструкций, которые произведут этот набор данных на универсальном вычислительном устройстве.   
• Оптимизация двухкомпонентного кода: Обратите внимание, что, ограничиваясь программами с пустым вводом и сосредоточив внимание на длине программ вместо их содержания, мы приобретаем качество инвариантности для нашей меры, но при этом теряем много выразительности. Игнорируется информация в реальной программе, которая производит набор данных. Вот почему последующие исследования были сосредоточены на методах, позволяющих сделать явной объяснительную силу, скрытую в колмогоровской мере сложности.

Интерпретация закона Байеса является одним из возможных подходов. Если мы объединим понятие Шеннона об оптимальном коде с законом Байеса, мы получим грубую теорию об оптимальном выборе модели. Пусть $\mathcal{H}$ будет набором гипотез, а $x$ пусть будет набором данных. Используя закон Байеса, мы получим оптимальную вычислительную модель при заданном распределении следующего вида:

$$\begin{aligned} M_{\textit{map}}(x) = \textit{argmax}_{M \in \mathcal{H}} \frac{P(M) P(x\mid M)}{P(x)} \end{aligned}$$

Это выражение эквивалентно оптимизации следующего вида:

$$\begin{aligned}  \textit{argmin}_{M \in \mathcal{H}} - \log P(M) - \log P(x\mid M) \end{aligned}$$

В приведённом выражении $- \log P(x\mid M)$ можно интерпретировать как длину оптимального кода модели в смысле Шеннона, а $- \log P(x\mid M)$ как длину оптимального кода данных для модели, т.е. данных, интерпретируемых с помощью модели. Эта идея приняла каноничный вид в так называемом принципе МДО:

Принцип минимальной длины описания (МДО). Лучшая теория для объяснения набора данных — та, которая минимизирует вычисленную в битах сумму описания теории (код модели) и набора данных, закодированных в теории (код данных для модели). 

Принцип МДО часто называют современной версией бритвы Оккама, хотя в своей первоначальной формулировке бритва Оккама является онтологическим принципом и имеет мало общего со сжатием данных. Во многих случаях МДО является валидным эвристическим инструментом, и математические свойства cопутствующей теории были тщательно изучены (Grünwald 2007). Тем не менее МДО, бритва Оккама и двухкомпонентная оптимизация кода были предметом серьезных споров в последние десятилетия (см., например, Domingos 1998; McAllister 2003).

Философские следствия из работ, начатых Соломоновым, Колмогоровым и Хайтиным в 60-х годах ХХ века, фундаментальны и разнообразны. Например, универсальное распределение $m$, предложенное Соломоновым, кодифицирует все возможные математические знания и, будучи обновленным на основе эмпирических наблюдений, по сути сведется к оптимальной научной модели нашего мира.

Выбор универсальной машины Тьюринга можно рассматривать как выбор множества систематических ошибок для нашей методологии. Если несколько упростить вопрос, существует две школы, занимающие противоположные позиции по нему:

• Бедная машина: выберите маленькую универсальную машину Тьюринга. Если машина небольшая, она также общая и универсальна, так как в ней нет места для кодирования каких-либо систематических ошибок. Более того, ограничение на маленькие машины приводит к сравнительно небольшим издержкам при эмуляции одной машины на другой, поэтому получаемая версия колмогоровской сложности дает измерение с меньшим асимптотическим запасом. Хаттер напрямую защищает выбор «естественных» небольших машин (Hutter 2005; Rathmanner & Hutter 2011), однако Ли и Витани (Li and Vitányi 2008) также предлагают использовать маленькие модели.
  
• Богатая машина: выберите большую машину, которая явным образом отражает имеющиеся у вас сведения о мире. Для Соломонова, автора концепции алгоритмической сложности, выбор универсальной машины Тьюринга является выбором универсального априори (prior). Он защищает эволюционный подход к обучению, при котором агент постоянно адаптируется в соответствии с тем, что уже открыл. Выбор вашей эталонной машины Тьюринга единственным образом характеризует вашу априорную информацию (Solomonoff 1997).

Оба подхода имеют свою ценность. Для строгих математических доказательств подход бедной машинычасто является лучшим. Для практических применений, имеющих дело с конечными наборами данных, подход богатых моделей часто дает куда лучшие результаты, поскольку бедная машина должна будет «заново изобретать колесо» каждый раз, когда сжимает набор данных. Это обстоятетльство приводит к выводу, что Колмогоровская сложность по своей сути уже содержит теорию о научных систематических ошибках и как таковая предполагает методологию, в которой класс допустимых универсальных моделей должен быть явно сформулирован и обусловлен априори. В последние десятилетия выдвигалось несколько предложений по определению формальной единицы измерения, позволившей бы оценить количество структурной (или модельной) информации в наборе данных.

• Эстетическая мера (Birkhoff 1950)
• Утонченность (Koppel 1987; Antunes et al. 2006; Antunes & Fortnow 2003)
• Логическая глубина (Bennet 1988)
• Эффективная сложность (Gell-Mann, Lloyd 2003)
• Значимая информация (Vitányi 2006)
• Саморазличие (Wolpert & Macready 2007)
• Вычислительная глубина (Antunes et al. 2006)
• Фактичность (Adriaans 2008)

Как правило, в исследовании доминируют три интуиции: строка «интересна», когда

• в ее создание вовлечено определенное количество вычислений (утончённость, вычислительная глубина);
• при оптимизации двухкомпонентного кода существует баланс между кодом модели и кодом данных (эффективная сложность, фактичность);
• в ней есть внутренние фазовые переходы (саморазличие).

Такие модели выбраковывают как случаи с максимальной энтропией, так и с низким содержанием информации. Точная связь между указанными интуициями неясна. В последние годы проблема значимой информации интенсивно исследовалась, однако стремление сформулировать универсальный метод выбора модели, который был бы основан на методах сжатия, кажется ошибочным:

Наблюдение: мера значимой информации, основанная на оптимизации двухкомпонентного кода, никогда не может быть инвариантна в смысле колмогоровской сложности (Bloem et al. 2015).   

Судя по всему, описанное имеет место, даже если мы ограничимся более слабыми вычислительными моделями — такими как всюду определенные функции, — однако должны быть проведены дополнительные исследования. Похоже, что для данного подхода нет никакого априорного математического обоснования, хотя оптимизация двухчастного кода продолжает быть допустимым подходом в рамках эмпирической установки наборов данных, созданных на основе повторяющихся наблюдений. К явлениям, которые могут быть связаны с теорией структурной информации и которые в настоящее время плохо поняты, можно отнести фазовые переходы в трудности проблем выполнимости, связанные с их сложностью (Simon & Dubois 1989; Crawford & Auton 1993), а также фазовые переходы в выразительности машин Тьюринга, связаны с их сложностью (Crutchfield & Young 1989, 1990; Langton 1990; Dufort & Lumsden 1994).  

Детерминизм и термодинамика

Многие основные понятия теории информации были разработаны в XIX веке в контексте новой науки — термодинамики. Существует разумно обоснованное понимание взаимосвязи между колмогоровской сложностью и информацией Шеннона (Li & Vitányi 2008; Grünwald & Vitányi 2008; Cover & Thomas 2006), однако объединение понятия энтропии в термодинамике и информации Шеннона — Колмогорова является весьма неполным, за исключением отдельных догадок ad hoc (Harremoës & Topsøe 2008; Bais & Farmer 2008). Фредкин и Тоффоли (Fredkin и Toffoli 1982) предложили так называемые бильярдные компьютеры для изучения обратимых систем в термодинамике (Durand-Lose 2002). Возможные теоретические модели с высокой вероятностью могут быть подтверждены осуществимыми экспериментами (например, адиабатическое расширение Джоуля, см. Adriaans 2008).

Возникающие в этой связи вопросы таковы:

• Чем является вычислительный процесс с термодинамической точки зрения?
• Может ли термодинамическая теория вычислений служить теорией неравновесной динамики?
• Нужна ли для физического описания нашей вселенной выразительность действительных чисел?

Эти проблемы кажутся трудными потому, что 150 лет исследований в области термодинамики все еще оставляют множество концептуальных неясностей в основе самой теории термодинамики.

Вещественные числа недоступны для нас в конечных вычислительных процессах, однако они играют важную роль, когда мы анализируем термодинамические процессы. Наиболее элегантные модели физических систем основаны на функциях в непрерывных пространствах. В таких моделях почти все точки пространства несут бесконечное количество информации. Тем не менее краеугольным камнем термодинамики является положение, что конечное количество пространства имеет конечную энтропию. Основываясь же на теории квантовой информации, нет причины предполагать, что выразительность действительных чисел никогда не используется в самой природе на этом уровне. Описываемая проблема связана с вопросами, изучаемыми философией математики (интуиционистский vs. более платонический взгляд на природу математических объектов). Этот вопрос является центральным и в некоторых философских дискуссиях о природе вычислений и информации (Putnam 1988; Searle 1990), а также связан с понятием фазовых переходов в описании природы (например, термодинамика vs. статистическая механика) и с идеей уровней абстракции (Floridi 2002).

В последнее десятилетие был достигнут определенный прогресс в анализе этих вопросов. Ключевая идея заключается в том, что взаимодействие между временем и вычислительными процессами может быть понято на абстрактно-математическом уровне, не обремененное каким бы то ни было предполагаемым физическим применением (Adriaans & van Emde Boas 2011). Основополагающим является понимание того, что детерминированные программы не генерируют новую информацию. Следовательно, детерминированные вычислительные модели физических систем никогда не смогут объяснить рост информации или энтропии в природе:

Наблюдение. Учитывая фундаментальную теорему Адрианса и ван Эмде Боаса (of Adriaans and van Emde Boas 2011), а также предположение о том, что квантовая физика и есть по сути стохастическое описание структуры нашей реальности, предположение Лапласа о том, что вселенная может быть описана как детерминированный компьютер, неверно.

С этой точки зрения математические модели термодинамики, в основном представляющие собой дифференциальные уравнения в пространствах действительных чисел, похоже, работают на недостаточно выразительном уровне. Более сложные математические модели, учитывающие квантовые эффекты, могли бы решить некоторые концептуальные трудности. На субатомном уровне природа представляется вероятностной по своей сути. Если вероятностные квантовые эффекты играют роль в поведении реальных бильярдных шаров, тогда дискуссия о том, увеличивается ли энтропия в абстрактном, состоящем из идеальных шаров газе кажется несколько академической. Есть основания полагать, что стохастические явления на квантовом уровне выступают источником вероятности в макроскопическом масштабе (Albrecht & Phillips 2014). С этой точки зрения вселенная является постоянным источником буквально астрономических объемов информации на любом масштабе.

Логическая и семантическая информация

Как логический, так и вычислительный подходы к пониманию информации берут начало в «лингвистическом повороте», характерном для философских исследований начала ХХ века; первоначальные исследовательские вопросы прослеживаются в работах Фреге (1997). Как видно из работ таких исследователей, как Поппер, Карнап, Соломонов, Колмогоров, Хайтин, Риссанен, Коппель, Шмиронубер, Ли, Витани и Хаттер, стремление количественно оценить информацию в наборах истинных предложений — это по сути семантическая исследовательская программа. Фактически, теория информации Шеннона — единственный современный подход, который прямым образом заявляет о своем несемантическом характере.

В то же время можно разработать количественные версии семантических теорий.

Лежащая в основании алгоритмической теории сложности интуиция о том, что интенсионал или значение объекта может быть вычислением, первоначально была сформулирована Фреге (1997). Выражения «$1 + 4$» и «$2 + 3$» имеют одинаковое экстенсионал (объем понятия, Bedeutung), «$5$», но разный интенсионал (содержание понятия, Sinn). Тем самым один математический объект может иметь бесконечное число различных значений. Существуют непрозрачные контексты, в которых такое различие необходимо. Рассмотрим предложение «Джон знает, что $\log_2 2^2 = 2$». Очевидно, релевантным является тот факт, что $\log_2 2^2$ представляет конкретное вычисление. Если же подставить его результат, предложение «Джон знает, что $2 = 2$» будет иметь другое значение. 

Данн (Dunn 2001, 2008) указал, что анализ информации в логике неразрывно связан с понятиями интенсионала и экстенсионала. Различие между ними предвосхищено уже в «Логике Пор-Рояля» (1662) и трудах Милля (1843), Буля (Boole 1847) и Пирса (Peirce 1868), но систематически было введено в логику усилиями Фреге (1997). В сегодняшнем смысле экстенсионалом предиката, к примеру, «$X$ является бакалавром», будет просто множество бакалавров в нашей области определения. Интенсионал же связан со значением предиката и и позволяет нам вывести из того факта, что «Джон является холостяком», факты о том, что «Джон — мужчина» и «Джон не женат». Очевидно, что это явление связано как с интерпретацией модальных операторов через возможные миры, так и с понятием информации. Холостяк по необходимости также является мужчиной, т.е. в каждом возможном мире, в котором Джон является холостяком, он также является мужчиной, откуда следует: если кто-то предоставляет мне информацию о том, что Джон холостяк, я «бесплатно» получаю информацию, что он мужчина и не женат.

Интерпретация модальных операторов через возможные миры (Крипке 1974) связана с понятием «описание состояния», введенным Карнапом (2007). Описание состояния — это соединение, которое содержит каждое атомарное предложение или его отрицание ровно один раз (см. раздел 4.3). Стремление определить хорошую меру вероятности для описаний состояний было одной из причин, по которым Соломонов (Solomonoff 1960, 1997) разработал алгоритмическую теорию информации. Из этой перспективы колмогоровская сложность с ее разделением типов данных (программ, данных, машин) и акцентом на истинных предложениях, описывающих следствия процессов, является в своей основе семантической теорией. Это сразу же становится понятным, если мы оценим выражение:

$$U_j(\overline{T_i}x)= y$$

Как уже было разъяснено в разделе 5.2.1, выражение $U_j(\overline{T_i}x)$ обозначает результат эмуляции вычисления $T_i(x)$ на $U_j$ после прочтения саморазграничивающего описания $\overline{T_i}$ машины $T_j$. Данное выражение можно интерпретировать как фрагмент семантической информации в контексте информационной карты следующим образом:        

• Универсальная машина Тьюринга $U_j$ — это контекст, в котором происходит вычисление. В модальной интерпретации вычислительной семантики его можно интерпретировать как возможный вычислительный мир.
• Последовательности символов $\overline{T_i}x$ и $y$ являются правильно сформированными данными.
• Последовательность $\overline{T_i}$ является саморазграничивающим описанием программы и может быть интерпретирована как фрагмент правильно сформированных инструктивных данных.
• Последовательность $\overline{T_i}x$ является интенсионалом. Последовательность же $y$ — соответствующим экстенсионалом.
• Выражение $U_j(\overline{T_i}x)= y$ устанавливает, что результатом программы $\overline{T_i}x$ в мире $U_j$ является $у$. Это истинное предложение.

Логическую структуру предложения $U_j(\overline{T_i}x)= y$ можно сравнить со следующим истинным предложением:   

Mutatis mutandis,‹7› можно разработать следующую интерпретацию: $U_j$ можно счесть контекстом, в котором, к примеру, кодифицирована систематическая ошибка проводимых с Земли научных наблюдений, $y$ — это экстенсионал, Венера, а $\overline{T_i}x$ — интенсионал, «яркая звезда, которую вы можете увидеть утром в восточной части неба». Интенсионал состоит из $T_i$, которым может выступать некоторая общая программа проведения астрономических наблюдений (например, инструктивные данные), и $x$, предоставляющего правильно сформированные данные о том, где искать (яркая звезда утром на восточном небе).

Такой подход предполагает возможное объединение ориентированных на истину теорий информации и вычислительных подходов — если говорить об этом в терминах информационной карты. Мы обозначим некоторые исследовательские вопросы:

• Чем является хорошая логическая система (или множество систем), формализующая наши представления об отношениях между такими понятиями, как «знание», «вера» и «быть информированным о чем-либо». Свои варианты ответа предлагали такие авторы, как Дрецке (Dretske 1981), Ван Бентем (van Benthem 2006; van Benthem & de Rooij 2003), Флориди (Floridi 2003, 2011) и другие. Тщательное отображение этих концепций на наш сегодняшнем ландшафте известных (структурных, модальных) логик позволит прояснить сильные и слабые стороны предлагаемых вариантов.
• Неясно, в чем заключается видовое отличие (в аристотелевском смысле), отделяющее данные об окружающей среде от других данных. Например, если некто использует гальку на пляже, чтобы подсчитать количество наблюдаемых дельфинов, неосведомленный прохожий может оказаться не в состоянии решить, является ли это скопление камней данными об окружающей среде или нет.
• Категория инструктивных данных кажется слишком узкой, поскольку ограничивает нас конкретной интерпретацией того, что такое вычисления. По большей части, эквивалентные по Тьюрингу вычислительные парадигмы не являются инструктивными; впрочем, можно отстаивать и мнение, что такими данными являются сами программы для машин Тьюринга.
• Неясно, как мы справимся с онтологической двойственностью, присущей самореференциальным аспектам Тьюринг-полных систем: машины Тьюринга работают с данными, которые в то же время действуют как репрезентации программ, т.е. являются и инструктивными, и не-инструктивными.
• Неясно, как теория, определяющая информацию исключительно в терминах истинных утверждений, поможет разобраться с фундаментальными проблемами квантовой физики. Как в подобной теории непоследовательная логическая модель, — в которой кот Шредингера одновременно и мертв, и жив, — может содержать какую-либо информацию?

Значение и вычисление

Со времен Декарта идея о том, что воспринимаемый нами полный значения мир может быть сведен к физическим процессам, была преобладающей темой в западной философии. Шествуя сквозь историю, соответствующая философская саморефлексия четко следует этапам технических разработок: является ли человеческий разум автоматом, является ли разум машиной Тьюринга и, наконец, является ли разум квантовым компьютером? Здесь не место подробно обсуждать эти вопросы, однако соответствующая проблема актуальна в философии информации:

Открытая проблема: Может ли значение быть сведено к вычислениям?

Этот вопрос переплетается с более общими вопросами философии, и ответ на него требует выбора между более позитивистским или более герменевтическим подходом к философии — с вытекающими следствиями для теории познания, метафизики, эстетики и этики. Ответ также влияет на непосредственные практические решения, которые мы ежедневно принимаем. Должны ли действия врача основываться на доказательной медицине или понятии caritas (милосердие)? Является ли пациент сознательным человеком, который хочет вести осмысленную жизнь или он в конечном счете просто система, которую нужно починить?

Идея о том, что значение по своей сути является вычислительным явлением, может показаться радикальной, однако существует множество обсуждений и теорий в науке, философии и культуре, которые косвенно предполагают подобный взгляд. В популярной культуре, например, есть выдающаяся коллекция фильмов и книг, где злые компьютеры осознают себя (2001, «Космическая Одиссея»), индивидуумы загружают свое сознание в компьютер (1992, «Газонокосильщик») и сражаться в виртуальных реальностях (1999, «Матрица»). В философии показательна позиция Бострома (Bostrom 2003), который отстаивает мнение, что мы, вполне вероятно, уже живем в компьютерной симуляции. Спорить о плюсах и минусах редукции значения до уровня вычислений можно по-разному. Мы даем обзор возможных аргументов для каждой из двух крайних позиций:

• Значение является эмерджентным аспектом вычислений: Наука воплощает нашу лучшую попытку разработать достоверное объективное теоретическое описание вселенной, основанное на интерсубъективно проверяемых повторных наблюдениях. Наука утверждает, что наша реальность на малом масштабе состоит из элементарных частиц, поведение которых описывается точными математическими моделями. На элементарном уровне эти частицы взаимодействуют и обмениваются информацией. Эти процессы по своему существу вычислительные. На этом самом базовом уровне описания для субъективного понятия значения нет места. Нет оснований отрицать, что мы как люди переживаем полный значения мир, но это обстоятельство само по себе должно быть эмерджентным аспектом природы. На фундаментальном уровне ничего подобного не существует. Мы можем описать нашу вселенную как большой квантовый компьютер. Мы можем оценить содержание накопителя информации о нашей Вселенной — равное $10^92$ бит — и посчитать, сколько вычислительных шагов она совершила с момента Большого взрыва — около $10^123$ (Lloyd 2000; Lloyd & Ng 2004). Как человеческие существа, мы — всего лишь подсистемы вселенной с оценочной сложностью примерно $10^30$ бит. Это может оказаться невозможным технически, но, судя по всему, не существует теоретического возражения против принципиальной возможности создать точную копию человека: либо в виде непосредственной физической копии, либо в виде симуляции на компьютере. Такой «искусственный» человек будет переживать полный значения мир, но его опыт будет эмерджентным явлением этого мира.
• Значение онтологически укоренено в нашем индивидуальном восприятии мира и, следовательно, нередуцируемо: Причина, по которой научные теории исключают большинство семантических аспектов нашего мира, обусловлена ​​самой природой методологии науки как таковой. Суть значения и связанных с ним эмоций заключается в том, что они коренятся в нашем индивидуальном восприятии мира. Сосредоточившись на повторных наблюдениях схожих событий разными наблюдателями, научная методология исключает возможность анализа концепции значения априори. Эмпирическая научная методология ценна тем, что она позволяет нам абстрагироваться от индивидуальных различий сознательных наблюдателей, однако нет никаких причин сводить нашу онтологию к явлениям, изучаемым эмпирической наукой. Разрозненные отдельные события и наблюдения по определению не доступны для экспериментального анализа, и, похоже, это служит линией разграничения между естественными и гуманитарными науками. В таких дисциплинах, как история, литература, изобразительное искусство и этика, мы преимущественно анализируем отдельные события и отдельные объекты. Чем ближе они к нашему индивидуальному существованию, тем больше они значат для нас. Нет сомнений, что такие предложения, как «Герника — шедевр, показывающий зверства войны» или «Маккинрой сыграл такой вдохновенный матч, что он заслуживал победы», произнесенные в правильном контексте выражают значимую информацию. Позиция, что это информационное содержание в конечном счете следует понимать с точки зрения вычислительных процессов, кажется слишком радикальной, чтобы быть жизнеспособной.

Кроме того, такая дисциплина, как физика, — которая до недавнего времени игнорировала около 68% энергии во вселенной и 27% материи, у которой нет единой теории элементарных сил, и которая объясняет лишь фундаментальные аспекты нашего мира посредством математических моделей, лишённых какой-либо интуитивной основы, — на данный момент не сходится к единой модели, способной выступить адекватным фундаментом для редукционистской метафизики.

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

Ясно, что в качестве концептуальной модели вычисления играют важную роль во многих научных дисциплинах — от когнитинвых наук (Chater & Vitányi 2003) до биологии и физики (Lloyd & Ng 2004; Verlinde 2011, 2017). Извлечение значимых моделей из наборов данных при помощи вычислений является движущей силой революции больших данных (Adriaans & Zantinge 1996; Bell, Hey & Szalay 2009; Hey, Tansley, & Tolle 2009).

Исследовательский вопрос «Как мы можем сформировать значимые (осмысленные) данные из больших наборов данных с помощью вычислений?» является фундаментальной метапроблемой науки в XXI веке и как таковой — частью философии информации, однако в редукционистском взгляде нет строгой необходимости.

Заключение

Первая из областей, которые могут извлечь выгоду из философии информации, — это, конечно, сама философия. Понятие информации потенциально оказывает влияние почти на все основные философские дисциплины: начиная от логики и теории познания и заканчивая онтологией или даже этикой и эстетикой (см. введение выше). Философия науки и философия информации с их интересом к проблеме индукции и формирования теорий, вероятно, тоже могли бы лишь выиграть от более тесного сотрудничества (см. раздел 4.1). Понятие информации играет важную роль в истории философии, и эту роль в целом ещё предстоит осмыслить (см. раздел 2).

Археологи, лингвисты, физики, астрономы — все они имеют дело с информацией. Первое, что должен сделать ученый, прежде чем сформулировать теорию, — это собрать информацию. Возможностей для применения сколько угодно. Глубинный анализ данных и обработка чрезвычайно больших наборов данных, похоже, важны практически для каждой эмпирической дисциплины в XXI веке.

В биологии было обнаружено, что информация необходима для организации самой жизни и для размножения сложных организмов. Одна из основных проблем заключается в том, что современные модели не могут достаточно хорошо объяснить сложность жизни. Валиант начал исследовательскую программу, изучающую эволюцию как форму вычислительного обучения (Valiant 2009), чтобы объяснить упомянутое несоответствие. Ааронсон (Aaronson 2013) однозначно высказался за более тесное сотрудничество между теорией сложности и философией. 

До недавнего времени общее мнение заключалось в том, что разные понятия информации суть более или менее изолированные, однако в последние годы был достигнут значительный прогресс в понимании взаимосвязи между ними. Например, Кавер и Томас (Cover and Thomas 2006) видят идеальное соответствие между колмогоровской сложностью и информацией Шеннона. Аналогичные наблюдения были сделаны Грюнвальдом и Витаньи (Grünwald and Vitányi 2008). Также были изучены связи, существующие между теорией термодинамики и теорией информации (Bais and Farmer 2008; Harremoës & Topsøe 2008), благодаря которым становится ясно: связи между физикой и теорией информации гораздо сложнее, чем можно предположить, исходя просто из ad hoc сходства между формальным подходом к энтропии и к определениею информации (Gell-Mann & Lloyd 2003; Verlinde 2011, 2017). В настоящее время квантовые вычисления еще не развиты до такой степени, когда они будут эффективнее классических вычислений, но этот предел может быть преодолен в ближайшие годы. С точки зрения философии многие концептуальные проблемы квантовой физики и теории информации, по-видимому, сливаются в одну область смежных вопросов:

• Какова связь между информацией и вычислением?
• Являются ли вычисления в реальном мире принципиально недетерминированными?
• Какова связь между символьной обработкой на макроскопическом масштабе и миром квантовой физики?
• Какова хорошая модель квантового вычисления и как мы контролируем его мощность?
• Существует ли информация за пределами мира квантов?

Понятие информации заняло центральное место в лоне естественных наук и общественной жизни. Информационные технологии играют ключевую роль в том, как мы организуем свою жизнь. Оно также стало основной категорией в естественных и гуманитарных науках. Философия информации — как историческая, так и систематическая дисциплина — предлагает новый взгляд на старые философские проблемы, а также дает начало некоторым новым исследовательским областям.

Библиография

• Аквинский Ф. Сумма теологии. Т. I – V. М.: Либроком, Signum Veritatis, Издатель Савин С.А., 2005–2016.
• Аристотель. Соч.: В 4 т. М.: Мысль, 1976. Т. 1, с. 371–448.
• Беркли Дж. Алкифрон, или Мелкий философ. Работы разных лет. СПб.: Алетейя, 1996.
• Бернулли Д. Гидродинамика, или записки о силах и движениях жидкостей. Л.: Изд. АН СССР, 1950.
• Больцман Л.Э. О механическом смысле второго начала теории теплоты //Избранные труды. М.: Издательство «Наука», 1984. С. 9–30.
• Бостром Н. А не живем ли мы в «Матрице»? Доказательство методом моделирования // Прими красную таблетку: Наука, философия и религия в «Матрице» / под ред. Глена Йеффета. М.: Ультра.Культура, 2003.
• Галилей. Пробирных дел мастер. М.: Наука, 1987.
• Гиббс Дж. В. Термодинамические работы. М., 1950.
• Декарт Р. Размышления о первой философии, в коих доказывается существование Бога и различие между человеческой душой и телом // Соч: В 2 т. М.: Мысль, 1989. Т. 2. С. 3–72.
  
• Декарт Р. Рассуждение о методе, чтобы верно направлять свой разум и отыскивать истину в науках // Соч: В 2 т. М.: Мысль, 1989. Т. 1. С. 250–296.
• Дефо Д. Жизнь и удивительные приключения Робинзона Крузо. М.; Л.: Издательство ACADEMIA, 1935.
  
• Дойл К. А. Приключение знатного холостяка. М.: Эксмо-пресс, 2016.
• Ибн-Туфейль. Повесть о Хайе, сыне Якзана. М.: Книга, 1988
• Кант И. Критика чистого разума. СПб.: тип. М. М. Стасюлевича, 1907.
• Карнап Р. Значение и необходимость. Исследование по семантике и модальной логике. М.: ЛКИ, 2007.
• Колмогоров А. Н. Три подхода к определению понятия «количество информации // Проблемы передачи информации. 1965. Т. 1. № 1. С. 3–11.
• Крипке С. А. 1) Теорема полноты в модальной логике; 2) Неразрешимость одноместного модального исчисления предикатов; 3) Семантический анализ модальной логики, ч. 1—2 // Фейс Р. Модальная логика. М., 1974. С. 223—323.
• Крипке С. Тождество и необходимость // Новое в зарубежной лингвистике. Вып. XIII. М., 1982.
• Куайн У. Две догмы эмпиризма. М.: Логос, Праксис, 2000
• Лаплас П. С. Опыт философии теории вероятностей // Вероятность и математическая статистика: Энциклопедия / Гл. ред. Ю. В. Прохоров. М.: Большая Российская энциклопедия, 1999. С. 834—869.
• Левин Л. А. Законы сохранения (невозрастания) информации и вопросы обоснования теории вероятностей // Проблемы передачи информации. Т. 10. № 3. 1974. С. 30–35.
• Левин Л. А. Универсальные задачи перебора // Проблемы передачи информации. Т. 9. № 3. 1973. С. 115–116.
• Локк Дж. Опыт о человеческом разумении. Кн. 1–4 // Соч.: В 3 т. М.: Мысль, 1985. Т. 1.
• Милль Дж. С. Система логики силлогистической и индуктивной. М.: ЛЕНАНД, 2011.
• Остен Дж. Эмма. М.: АСТ, 2015.
• Поппер К. Логика и рост научного знания (избранные работы). М.: Прогресс, 1983.
• Уайтхед А., Рассел Б. Основания математики: В 3 т. Самара: Самарский университет, 2005—2006.
• Фон Нейман Дж. Математические основы квантовой механики. М.: Наука, 1964.
• Фреге Г. Избранные работы. М., 1997.
• Хартли Р.В.Л. Передача информации. // Теория информации и ее приложения. М.: Физматгиз, 1959.
• Юм Д. Исследование о человеческом разумении // Соч.: В 2 т. М.: Мысль, 1996. Т. 2.
• Юм Д. Трактат о человеческой природе // Соч.: В 2 т.  М.: Мысль, 1996. Т. 1.

• Aaronson, Scott, 2013, “Why Philosophers Should Care About Computational Complexity”, in Computability: Turing, Gödel, Church, and Beyond, Brian Jack Copeland, Carl J. Posy, and Oron Shagrir (eds.), Cambridge, MA: The MIT Press. [Aaronson 2013 preprint available online]
• Abramsky, Samson and Achim Jung, 1994, “Domain theory”, in Handbook of Logic in Computer Science (vol. 3): Semantic Structure, Samson Abramsky, Dov M. Gabbay, and Thomas S. E. Maibaum (eds.),. Oxford University Press. pp. 1–168.
• Adams, Fred and João Antonio de Moraes, 2016, “Is There a Philosophy of Information?”, Topoi, 35(1): 161–171. doi:10.1007/s11245-014-9252-9
• Adriaans, Pieter, 2007, “Learning as Data Compression”, in Computation and Logic in the Real World, S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (eds.), (Lecture Notes in Computer Science: Volume 4497), Berlin, Heidelberg: Springer Berlin Heidelberg, 11–24. doi:10.1007/978-3-540-73001-9_2
• –––, 2008, “Between Order and Chaos: The Quest for Meaningful Information”, Theory of Computing Systems (Special Issue: Computation and Logic in the Real World; Guest Editors: S. Barry Cooper, Elvira Mayordomo and Andrea Sorbi), 45(4): 650–674. doi:10.1007/s00224-009-9173-y
• Adriaans, Pieter and Peter van Emde Boas, 2011, “Computation, Information, and the Arrow of Time”, in Computability in Context: Computation and Logic in the Real World, by S Barry Cooper and Andrea Sorbi (eds), London: Imperial College Press, 1–17. doi:10.1142/9781848162778_0001
• Adriaans, Pieter and Johan van Benthem, 2008a, “Introduction: Information Is What Information Does”, in Adriaans & van Benthem 2008b: 3–26. doi:10.1016/B978-0-444-51726-5.50006-6
• ––– (eds.), 2008b, Philosophy of Information, (Handbook of the Philosophy of Science 8), Amsterdam: Elsevier. doi:10.1016/C2009-0-16481-4
• Adriaans, Pieter and Paul M.B. Vitányi, 2009, “Approximation of the Two-Part MDL Code”, IEEE Transactions on Information Theory, 55(1): 444–457. doi:10.1109/TIT.2008.2008152
• Adriaans, Pieter and Dolf Zantinge, 1996, Data Mining, Harlow, England: Addison-Wesley.
• Agrawal, Manindra, Neeraj Kayal, and Nitin Saxena, 2004, “PRIMES Is in P”, Annals of Mathematics, 160(2): 781–793. doi:10.4007/annals.2004.160.781
• Albrecht, Andreas and Daniel Phillips, 2014, “Origin of Probabilities and Their Application to the Multiverse”, Physical Review D, 90(12): 123514. doi:10.1103/PhysRevD.90. 123514
• Antunes, Luís and Lance Fortnow, 2003, “Sophistication Revisited”, in Proceedings of the 30th International Colloquium on Automata, Languages and Programming (Lecture Notes in Computer Science: Volume 2719), Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger (eds.), Berlin: Springer, pp. 267–277. doi:10.1007/3-540-45061-0_23
• Antunes, Luis, Lance Fortnow, Dieter van Melkebeek, and N.V. Vinodchandran, 2006, “Computational Depth: Concept and Applications”, Theoretical Computer Science, 354(3): 391–404. doi:10.1016/j.tcs.2005.11.033
• Arbuthnot, John, 1692, Of the Laws of Chance, or, a method of Calculation of the Hazards of Game, Plainly demonstrated, And applied to Games as present most in Use, translation of Huygens’De Ratiociniis in Ludo Aleae, 1657.
• Austen, Jane, 1815, Emma, London: Richard Bentley and Son.
• Bar-Hillel, Yehoshua and Rudolf Carnap, 1953, “Semantic Information”, The British Journal for the Philosophy of Science, 4(14): 147–157. doi:10.1093/bjps/IV.14.147
• Bais, F. Alexander and J. Doyne Farmer, 2008, “The Physics of Information”, Adriaans and van Benthem 2008b: 609–683. doi:10.1016/B978-0-444-51726-5.50020-0
• Barron, Andrew, Jorma Rissanen, and Bin Yu, 1998, “The Minimum Description Length Principle in Coding and Modeling”, IEEE Transactions on Information Theory, 44(6): 2743–2760. doi:10.1109/18.720554
• Barwise, Jon and John Perry, 1983, Situations and Attitudes, Cambridge, MA: MIT Press.
• Bell, Gordon, Tony Hey, and Alex Szalay, 2009, “Computer Science: Beyond the Data Deluge”, Science, 323(5919): 1297–1298. doi:10.1126/science.1170411
• Bennett, C. H., 1988, “Logical Depth and Physical Complexity”, in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey, Oxford: Oxford University Press, pp. 227–257.
• Bernoulli, Danielis, 1738, Hydrodynamica, Argentorati: sumptibus Johannis Reinholdi Dulseckeri. [Bernoulli 1738 available online]
• Birkhoff, George David, 1950, Collected Mathematical Papers, New York: American Mathematical Society.
• Bloem, Peter, Steven de Rooij, and Pieter Adriaans, 2015, “Two Problems for Sophistication”, in Algorithmic Learning Theory, (Lecture Notes in Computer Science 9355), Kamalika Chaudhuri, Claudio Gentile, and Sandra Zilles (eds.), Cham: Springer International Publishing, 379–394. doi:10.1007/978-3-319-24486-0_25
• Boole, George, 1847, Mathematical Analysis of Logic: Being an Essay towards a Calculus of Deductive Reasoning, Cambridge: Macmillan, Barclay, & Macmillan. [Boole 1847 available online].
• –––, 1854, An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities, London: Walton and Maberly.
• Bott, R. and J. Milnor, 1958, “On the Parallelizability of the Spheres”, Bulletin of the American Mathematical Society, 64(3): 87–89. doi:10.1090/S0002-9904-1958-10166-4
• Bovens, Luc and Stephan Hartmann, 2003, Bayesian Epistemology, Oxford: Oxford University Press. doi:10.1093/0199269750.001.0001
• Brenner, Joseph E., 2008, Logic in Reality, Dordrecht: Springer Netherlands. doi:10.1007/978-1-4020-8375-4
• Briggs, Henry, 1624, Arithmetica Logarithmica, London: Gulielmus Iones.
• Capurro, Rafael, 1978, Information. Ein Beitrag zur etymologischen und ideengeschichtlichen Begründung des Informationsbegriffs (Information: A contribution to the foundation of the concept of information based on its etymology and in the history of ideas), Munich, Germany: Saur. [Capurro 1978 available online].
• –––, 2009, “Past, Present, and Future of the Concept of Information”, TripleC: Communication, Capitalism & Critique, 7(2): 125–141. doi:10.31269/triplec.v7i2.113
• Capurro, Rafael and Birger Hjørland, 2003, “The Concept of Information”, in Blaise Cronin (ed.), Annual Review of Information Science and Technology (ARIST), 37: 343–411 (Chapter 8). doi:10.1002/aris.1440370109
• Capurro, Rafael and John Holgate (eds.), 2011, Messages and Messengers: Angeletics as an Approach to the Phenomenology of Communication (Von Boten Und Botschaften, (Schriftenreihe Des International Center for Information Ethics 5), München: Fink.
• Carnap, Rudolf, 1928, Scheinprobleme in der Philosophie (Pseudoproblems of Philosophy), Berlin: Weltkreis-Verlag.
• –––, 1945, “The Two Concepts of Probability: The Problem of Probability”, Philosophy and Phenomenological Research, 5(4): 513–532. doi:10.2307/2102817
• –––, 1950, Logical Foundations of Probability, Chicago: The University of Chicago Press.
• Chaitin, Gregory J., 1969, “On the Length of Programs for Computing Finite Binary Sequences: Statistical Considerations”, Journal of the ACM, 16(1): 145–159. doi:10.1145/321495.321506
• –––, 1987, Algorithmic Information Theory, Cambridge: Cambridge University Press. doi:10.1017/CBO9780511608858
• Chater, Nick and Paul Vitányi, 2003, “Simplicity: A Unifying Principle in Cognitive Science?”, Trends in Cognitive Sciences, 7(1): 19–22. doi:10.1016/S1364-6613(02)00005-0
• Cilibrasi, Rudi and Paul M.B. Vitanyi, 2005, “Clustering by Compression”, IEEE Transactions on Information Theory, 51(4): 1523–1545. doi:10.1109/TIT.2005.844059
• Clausius, R., 1850, “Ueber die bewegende Kraft der Wärme und die Gesetze, welche sich daraus für die Wärmelehre selbst ableiten lassen”, Annalen der Physik und Chemie, 155(3): 368–397. doi:10.1002/andp.18501550306
• Cover, Thomas M. and Joy A. Thomas, 2006, Elements of Information Theory, second edition, New York: John Wiley & Sons.
• Crawford, James M. and Larry D. Auton, 1993, “Experimental Results on the Crossover Point in Satisfiability Problems”, Proceedings of the Eleventh National Conference on Artificial Intelligence, AAAI Press, pp. 21–27. [Crawford & Auton 1993 available online]
• Crutchfield, James P. and Karl Young, 1989, “Inferring Statistical Complexity”, Physical Review Letters, 63(2): 105–108. doi:10.1103/PhysRevLett.63.105
• –––, 1990, “Computation at the Onset of Chaos”, in Entropy, Complexity, and the Physics of Information, W. Zurek, editor, SFI Studies in the Sciences of Complexity, VIII, Reading, MA: Addison-Wesley, pp. 223–269. [Crutchfield & Young 1990 available online]
• D’Alfonso, Simon, 2012, “Towards a Framework for Semantic Information”, Ph.D. Thesis, Department of Philosophy, School of Historical and Philosophical Studies, The University of Melbourne. D’Alfonso 2012 available online
• Davis, Martin, 2006, “Why There Is No Such Discipline as Hypercomputation”, Applied Mathematics and Computation, 178(1): 4–7. doi:10.1016/j.amc.2005.09.066
• De Leo, Stefano, 1996, “Quaternions and Special Relativity”, Journal of Mathematical Physics, 37(6): 2955–2968. doi:10.1063/1.531548
• Dershowitz, Nachum and Yuri Gurevich, 2008, “A Natural Axiomatization of Computability and Proof of Church’s Thesis”, Bulletin of Symbolic Logic, 14(3): 299–350. doi:10.2178/bsl/1231081370
• Devlin, Keith and Duska Rosenberg, 2008, “Information in the Study of Human Interaction”, Adriaans and van Benthem 2008b: 685–709. doi:10.1016/B978-0-444-51726-5.50021-2
• Dictionnaire du Moyen Français (1330–1500), 2015, “Information”, in Dictionnaire du Moyen Français (1330–1500), volume 16, 313–315. [Dictionnaire du Moyen Français available online]
• Domingos, Pedro, 1998, “Occam’s Two Razors: The Sharp and the Blunt”, in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD–98), New York: AAAI Press, pp. 37–43. [Domingos 1998 available online]
• Downey, Rodney G. and Denis R. Hirschfeldt, 2010, Algorithmic Randomness and Complexity, (Theory and Applications of Computability), New York: Springer New York. doi:10.1007/978-0-387-68441-3
• Dretske, Fred, 1981, Knowledge and the Flow of Information, Cambridge, MA: The MIT Press.
• Dufort, Paul A. and Charles J. Lumsden, 1994, “The Complexity and Entropy of Turing Machines”, in Proceedings Workshop on Physics and Computation. PhysComp ’94, Dallas, TX: IEEE Computer Society Press, 227–232. doi:10.1109/PHYCMP.1994.363677
• Dunn, Jon Michael, 2001, “The Concept of Information and the Development of Modern Logic”, in Zwischen traditioneller und moderner Logik: Nichtklassiche Ansatze (Non-classical Approaches in the Transition from Traditional to Modern Logic), Werner Stelzner and Manfred Stöckler (eds.), Paderborn: Mentis, 423–447.
• –––, 2008, “Information in Computer Science”, in Adriaans and van Benthem 2008b: 581–608. doi:10.1016/B978-0-444-51726-5.50019-4
• Dijksterhuis, E. J., 1986, The Mechanization of the World Picture: Pythagoras to Newton, Princeton, NJ: Princeton University Press.
• Duns Scotus, John [1265/66–1308 CE], Opera Omnia (The Wadding edition), Luke Wadding (ed.), Lyon, 1639; reprinted Hildesheim: Georg Olms Verlagsbuchhandlung, 1968.
• Durand-Lose, Jérôme, 2002, “Computing Inside the Billiard Ball Model”, in Collision-Based Computing, Andrew Adamatzky (ed.), London: Springer London, 135–160. doi:10.1007/978-1-4471-0129-1_6
• Edwards, Paul, 1967, The Encyclopedia of Philosophy, 8 volumes, New York: Macmillan Publishing Company.
• Fayyad, Usama, Gregory Piatetsky-Shapiro, and Padhraic Smyth, 1996, “From Data Mining to Knowledge Discovery in Databases”, AI Magazine, 17(3): 37–37.
• Fisher, R. A., 1925, “Theory of Statistical Estimation”, Mathematical Proceedings of the Cambridge Philosophical Society, 22(05): 700–725. doi:10.1017/S0305004100009580
• Floridi, Luciano, 1999, “Information Ethics: On the Philosophical Foundation of Computer Ethics”, Ethics and Information Technology, 1(1): 33–52. doi:10.1023/A:1010018611096
• –––, 2002, “What Is the Philosophy of Information?” Metaphilosophy, 33(1–2): 123–145. doi:10.1111/1467-9973.00221
• ––– (ed.), 2003, The Blackwell Guide to the Philosophy of Computing and Information, Oxford: Blackwell. doi:10.1002/9780470757017
• –––, 2010, “The Philosophy of Information as a Conceptual Framework”, Knowledge, Technology & Policy, 23(1–2): 253–281. doi:10.1007/s12130-010-9112-x
• –––, 2011, The Philosophy of Information, Oxford: Oxford University Press. doi:10.1093/acprof:oso/9780199232383.001.0001
• Fredkin, Edward and Tommaso Toffoli, 1982, “Conservative Logic”, International Journal of Theoretical Physics, 21(3–4): 219–253. doi:10.1007/BF01857727
• Furey, C., 2015, “Charge Quantization from a Number Operator”, Physics Letters B, 742(March): 195–199. doi:10.1016/j.physletb.2015.01.023
• Garey, Michael R. and David S. Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, (A Series of Books in the Mathematical Sciences), San Francisco: W. H. Freeman.
• Gell-Mann, Murray and Seth Lloyd, 2003, “Effective Computing”. SFI Working Paper 03-12-068, Santa Fe, NM: Santa Fe Institute. [Gell-Mann & Lloyd 2003 available online]
• Godefroy, Frédéric G., 1881, Dictionnaire de l’ancienne langue française et de tous ses dialectes du 9e au 15e siècle, Paris: F. Vieweg.
• Gödel, Kurt, 1931, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”, Monatshefte für Mathematik und Physik, 38–38(1): 173–198. doi:10.1007/BF01700692
• Goodstein, R. L., 1957, “The Definition of Number”, The Mathematical Gazette, 41(337): 180–186. doi:10.2307/3609188
• Grünwald, Peter D., 2007, The Minimum Description Length Principle, Cambridge, MA: MIT Press.
• Grünwald, Peter D. and Paul M.B. Vitányi, 2008, “Algorithmic Information Theory”, in Adriaans and van Benthem 2008b: 281–317. doi:10.1016/B978-0-444-51726-5.50013-3
• Groot, Adrianus Dingeman de, 1961 [1969], Methodology: Foundations of Inference and Research in the Behavioral Sciences (Methodologie: grondslagen van onderzoek en denken in de gedragswetenschappen), The Hague: Mouton.
• Harremoës, Peter and Flemming Topsøe, 2008, “The Quantitative Theory of Information”, in Adriaans and van Benthem 2008b: 171–216. doi:10.1016/B978-0-444-51726-5.50011-X
• Hazard, Paul, 1935, La Crise de La Conscience Européenne (1680–1715), Paris: Boivin.
• Hey, Anthony J. G., Stewart Tansley, and Kristin Tolle (eds.), 2009, The Fourth Paradigm: Data-Intensive Scientific Discovery, Redmond, WA: Microsoft Research. [Hey et al. 2009 available online]
• Hintikka, Jaakko, 1962, Knowledge and Belief: An Introduction to the Logic of the Two Notions, (Contemporary Philosophy), Ithaca, NY: Cornell University Press.
• –––, 1973, Logic, Language Games and Information: Kantian Themes in the Philosophy of Logic, Oxford: Clarendon Press.
• Hutter, Marcus, 2005, Universal Artificial Intellegence: Sequential Decisions Based on Algorithmic Probability, (Texts in Theoretical Computer Science, an EATCS Series), Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/b138233
• –––, 2007a, “On Universal Prediction and Bayesian Confirmation”, Theoretical Computer Science, 384(1): 33–48. doi:10.1016/j.tcs.2007.05.016
• –––, 2007b, “Algorithmic Information Theory: a brief non-technical guide to the field”,Scholarpedia, 2(3): art. 2519. doi:10.4249/scholarpedia.2519
• –––, 2010, “A Complete Theory of Everything (will be subjective)”, Algorithms, 3(4): 329–350. doi:10.3390/a3040329
• Hutter, Marcus, John W. Lloyd, Kee Siong Ng, and William T.B. Uther, 2013, “Probabilities on Sentences in an Expressive Logic”, Journal of Applied Logic, special issue: Combining Probability and Logic: Papers from Progic 2011, Jeffrey Helzner (ed.), 11(4): 386–420. doi:10.1016/j.jal.2013.03.003.
• Kahn, David, 1967, The Code-Breakers, The Comprehensive History of Secret Communication from Ancient Times to the Internet, New York: Scribner.
• Kervaire, Michel A., 1958, “Non-Parallelizability of the n-Sphere for n > 7”, Proceedings of the National Academy of Sciences of the United States of America, 44(3): 280–283. doi:10.1073/pnas.44.3.280
• al-Khwārizmī, Muḥammad ibn Mūsā, ca. 820 CE, Hisab al-jabr w’al-muqabala, Kitab al-Jabr wa-l-Muqabala (The Compendious Book on Calculation by Completion and Balancing), Translated by Frederic Rosen, London: Murray, 1831. [al-Khwarizmi translation available online]
• Koppel, Moshe, 1987, “Complexity, Depth, and Sophistication”, Complex Systems, 1(6): 1087–1091. [Koppel 1987 available online]
• Kuipers, Theo A.F. (ed.), 2007a, General Philosophy of Science: Focal Issues, Amsterdam: Elsevier Science Publishers.
• –––, 2007b, “Explanation in Philosophy of Science”, in Kuipers 2007a.
• Langton, Chris G., 1990, “Computation at the Edge of Chaos: Phase Transitions and Emergent Computation”, Physica D: Nonlinear Phenomena, 42(1–3): 12–37. doi:10.1016/0167-2789(90)90064-V
• Lenski, Wolfgang, 2010, “Information: A Conceptual Investigation”, Information 2010, 1(2): 74–118. doi:10.3390/info1020074
• Levin, Leonid A. 1984, “Randomness Conservation Inequalities; Information and Independence in Mathematical Theories”, Information and Control, 61(1): 15–37. doi:10.1016/S0019-9958(84)80060-1
• Li, Ming and Paul Vitányi, 2008, An Introduction to Kolmogorov Complexity and Its Applications, (Texts in Computer Science), New York: Springer New York. doi:10.1007/978-0-387-49820-1
• Lloyd, Seth, 2000, “Ultimate Physical Limits to Computation”, Nature, 406(6799): 1047–1054. doi:10.1038/35023282
• Lloyd, Seth and Y. Jack Ng, 2004, “Black Hole Computers”, Scientific American, 291(5): 52–61. doi:10.1038/scientificamerican1104-52
• McAllister, James W., 2003, “Effective Complexity as a Measure of Information Content”, Philosophy of Science, 70(2): 302–307. doi:10.1086/375469
• Montague, Richard, 2008, “Universal Grammar”, Theoria, 36(3): 373–398. doi:10.1111/j.1755-2567.1970.tb00434.x
• Mugur-Schächter, Mioara, 2003, “Quantum Mechanics Versus a Method of Relativized Conceptualization”, in Quantum Mechanics, Mathematics, Cognition and Action, Mioara Mugur-Schächter and Alwyn van der Merwe (eds.), Dordrecht: Springer Netherlands, 109–307. doi:10.1007/0-306-48144-8_7
• Napier, John, 1614, Mirifici Logarithmorum Canonis Descriptio (The Description of the Wonderful Canon of Logarithms), Edinburgh: Andre Hart. Translated and annotated by Ian Bruce, www.17centurymaths.com. [Napier 1614 [Bruce translation] available online].
• Nielsen, Michael A. and Isaac L. Chuang, 2000, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press.
• Nies, André, 2009, Computability and Randomness, Oxford: Oxford University Press. doi:10.1093/acprof:oso/9780199230761.001.0001
• Nyquist, H., 1924, “Certain Factors Affecting Telegraph Speed”, Bell System Technical Journal, 3(2): 324–346. doi:10.1002/j.1538-7305.1924.tb01361.x
• Ong, Walter J., 1958, Ramus, Method, and the Decay of Dialogue, From the Art of Discourse to the Art of Reason, Cambridge MA: Harvard University Press.
• Parikh, Rohit and Ramaswamy Ramanujam, 2003, “A Knowledge Based Semantics of Messages”, Journal of Logic, Language and Information, 12(4): 453–467. doi:10.1023/A:1025007018583
• Peirce, Charles S., 1868, “Upon Logical Comprehension and Extension”, Proceedings of the American Academy of Arts and Sciences, 7: 416–432. doi:10.2307/20179572
• –––, 1886 [1993], “ Letter Peirce to A. Marquand”, Reprinted in Writings of Charles S. Peirce: A Chronological Edition, Volume 5: 1884–1886, Indianapolis: Indiana University Press, pp. 424–427. See also Arthur W. Burks, 1978, “Book Review: ‘The New Elements of Mathematics’ by Charles S. Peirce, Carolyn Eisele (editor)”, Bulletin of the American Mathematical Society, 84(5): 913–919. doi:10.1090/S0002-9904-1978-14533-9
• Popper, Karl, 1934, The Logic of Scientific Discovery, (Logik der Forschung), English translation 1959, London: Hutchison. Reprinted 1977.
• Putnam, Hilary, 1988, Representation and reality, Cambridge, MA: The MIT Press.
• Quine, W.V.O., 1951, “Main Trends in Recent Philosophy: Two Dogmas of Empiricism”, The Philosophical Review, 60(1): 20–43. Reprinted in his 1953 From a Logical Point of View, Cambridge, MA: Harvard University Press. doi:10.2307/2181906
• Rathmanner, Samuel and Marcus Hutter, 2011, “A Philosophical Treatise of Universal Induction”, Entropy, 13(6): 1076–1136. doi:10.3390/e13061076
• Rédei, Miklós and Michael Stöltzner (eds.), 2001, John von Neumann and the Foundations of Quantum Physics, (Vienna Circle Institute Yearbook, 8), Dordrecht: Kluwer.
• Rényi, Alfréd, 1961, “On Measures of Entropy and Information”, in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, Berkeley, CA: The Regents of the University of California, pp. 547–561. [Rényi 1961 available online]
• Rissanen, J., 1978, “Modeling by Shortest Data Description”, Automatica, 14(5): 465–471. doi:10.1016/0005-1098(78)90005-5
• –––, 1989, Stochastic Complexity in Statistical Inquiry, (World Scientific Series in Computer Science, 15), Singapore: World Scientific.
• Rooy, Robert van, 2004, “Signalling Games Select Horn Strategies”, Linguistics and Philosophy, 27(4): 493–527. doi:10.1023/B:LING.0000024403.88733.3f
• Schmandt-Besserat, Denise, 1992, Before Writing (Volume I: From Counting to Cuneiform), Austin, TX: University of Texas Press.
• Schmidhuber, Jüurgen, 1997a, “Low-Complexity Art”, Leonardo, 30(2): 97–103. doi:10.2307/1576418
• –––, 1997b, “A Computer Scientist’s View of Life, the Universe, and Everything”, in Foundations of Computer Science, (Lecture Notes in Computer Science, 1337), Christian Freksa, Matthias Jantzen, and Rüdiger Valk (eds.), Berlin, Heidelberg: Springer Berlin Heidelberg, 201–208. doi:10.1007/BFb0052088
• Schnelle, H., 1976, “Information”, in Joachim Ritter (ed.), Historisches Wörterbuch der Philosophie, IV [Historical dictionary of philosophy, IV] (pp. 116–117). Stuttgart, Germany: Schwabe.
• Searle, John R., 1990, “Is the Brain a Digital Computer?”, Proceedings and Addresses of the American Philosophical Association, 64(3): 21–37. doi:10.2307/3130074
• Seiffert, Helmut, 1968, Information über die Information [Information about information] Munich: Beck.
• Shannon, Claude E., 1948, “A Mathematical Theory of Communication”, Bell System Technical Journal, 27(3): 379–423 & 27(4): 623–656. doi:10.1002/j.1538-7305.1948.tb01338.x & doi:10.1002/j.1538-7305.1948.tb00917.x
• Shannon, Claude E. and Warren Weaver, 1949, The Mathematical Theory of Communication, Urbana, IL: University of Illinois Press.
• Shor, Peter W., 1997, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing, 26(5): 1484–1509. doi:10.1137/S0097539795293172
• Simon, J.C. and Olivier Dubois, 1989, “Number of Solutions of Satisfiability Instances – Applications to Knowledge Bases”, International Journal of Pattern Recognition and Artificial Intelligence, 3(1): 53–65. doi:10.1142/S0218001489000061
• Simondon, Gilbert, 1989, L’individuation Psychique et Collective: À La Lumière des Notions de Forme, Information, Potentiel et Métastabilité (L’Invention Philosophique), Paris: Aubier.
• Singh, Simon, 1999, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, New York: Anchor Books.
• Solomonoff, R. J., 1960, “A Preliminary Report on a General Theory of Inductive Inference”. Report ZTB-138, Cambridge, MA: Zator. [Solomonoff 1960 available online]
• –––, 1964a, “A Formal Theory of Inductive Inference. Part I”, Information and Control, 7(1): 1–22. doi:10.1016/S0019-9958(64)90223-2
• –––, 1964b, “A Formal Theory of Inductive Inference. Part II”, Information and Control, 7(2): 224–254. doi:10.1016/S0019-9958(64)90131-7
• –––, 1997, “The Discovery of Algorithmic Probability”, Journal of Computer and System Sciences, 55(1): 73–88. doi:10.1006/jcss.1997.1500
• Stalnaker, Richard, 1984, Inquiry, Cambridge, MA: MIT Press.
• Stifel, Michael, 1544, Arithmetica integra, Nuremberg: Johan Petreium.
• Tarski, Alfred, 1944, “The Semantic Conception of Truth: And the Foundations of Semantics”, Philosophy and Phenomenological Research, 4(3): 341–376. doi:10.2307/2102968
• Tsallis, Constantino, 1988, “Possible Generalization of Boltzmann-Gibbs Statistics”, Journal of Statistical Physics, 52(1–2): 479–487. doi:10.1007/BF01016429
• Turing, A. M., 1937, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, s2-42(1): 230–265. doi:10.1112/plms/s2-42.1.230
• Valiant, Leslie G., 2009, “Evolvability”, Journal of the ACM, 56(1): Article 3. doi:10.1145/1462153.1462156
• van Benthem, Johan F.A.K., 1990, “Kunstmatige Intelligentie: Een Voortzetting van de Filosofie met Andere Middelen”, Algemeen Nederlands Tijdschrift voor Wijsbegeerte, 82: 83–100.
• –––, 2006, “Epistemic Logic and Epistemology: The State of Their Affairs”, Philosophical Studies, 128(1): 49–76. doi:10.1007/s11098-005-4052-0
• van Benthem, Johan and Robert van Rooy, 2003, “Connecting the Different Faces of Information”, Journal of Logic, Language and Information, 12(4): 375–379. doi:10.1023/A:1025026116766
• van Peursen, Cornelis Anthonie, 1987, “Christian Wolff’s Philosophy of Contingent Reality”, Journal of the History of Philosophy, 25(1): 69–82. doi:10.1353/hph.1987.0005
• van Rooij, Robert, 2003, “Questioning to resolve decision problems”, Linguistics and Philosophy, 26: 727–763.
• Vereshchagin, Nikolai K. and Paul M.B. Vitányi, 2004, “Kolmogorov’s Structure Functions and Model Selection”, IEEE Transactions on Information Theory, 50(12): 3265–3290. doi:10.1109/TIT.2004.838346
• Verlinde, Erik, 2011, “On the Origin of Gravity and the Laws of Newton”, Journal of High Energy Physics, 2011(4). doi:10.1007/JHEP04(2011)029
• –––, 2017, “Emergent Gravity and the Dark Universe”, SciPost Physics, 2(3): 016. doi:10.21468/SciPostPhys.2.3.016
• Vigo, Ronaldo, 2011, “Representational Information: A New General Notion and Measure of Information”, Information Sciences, 181(21): 4847–4859. doi:10.1016/j.ins.2011.05.020
• –––, 2012, “Complexity over Uncertainty in Generalized Representational Information Theory (GRIT): A Structure-Sensitive General Theory of Information”, Information, 4(1): 1–30. doi:10.3390/info4010001
• Vitányi, Paul M., 2006, “Meaningful Information”, IEEE Transactions on Information Theory, 52(10): 4617–4626. doi:10.1109/TIT.2006.881729 [Vitányi 2006 available online].
• Vogel, Cornelia Johanna de, 1968, Plato: De filosoof van het transcendente, Baarn: Het Wereldvenster.
• Wallace, C. S., 2005, Statistical and Inductive Inference by Minimum Message Length, Berlin: Springer. doi:10.1007/0-387-27656-4
• Wheeler, John Archibald, 1990, “Information, Physics, Quantum: The Search for Links”, in Complexity, Entropy and the Physics of Information, Wojciech H. Zurek (ed.), Boulder, CO: Westview Press, 309–336. [Wheeler 1990 available online]
• Wilkins, John, 1668, “An Essay towards a Real Character, and a Philosophical Language”, London. [Wilkins 1668 available online]
• Windelband, Wilhelm, 1903, Lehrbuch der Geschichte der Philosophie, Tübingen: J.C.B. Mohr.
• Wolff, J. Gerard, 2006, Unifying Computing and Cognition, Menai Bridge: CognitionResearch.org.uk.
• Wolfram, Stephen, 2002, A New Kind of Science, Champaign, IL: Wolfram Media.
• Wolpert, David H. and William Macready, 2007, “Using Self-Dissimilarity to Quantify Complexity”, Complexity, 12(3): 77–85. doi:10.1002/cplx.20165
• Wu, Kun, 2010, “The Basic Theory of the Philosophy of Information”, in Proceedings of the 4th International Conference on the Foundations of Information Science, Beijing, China, Pp. 21–24.
• –––, 2016, “The Interaction and Convergence of the Philosophy and Science of Information”,Philosophies, 1(3): 228–244. doi:10.3390/philosophies1030228
• Zuse, Konrad, 1969, Rechnender Raum, Braunschweig: Friedrich Vieweg & Sohn. Translated as Calculating Space, MIT Technical Translation AZT-70-164-GEMIT, MIT (Proj. MAC), Cambridge, MA, Feb. 1970. English revised by A. German and H. Zenil 2012. [Zuse 1969 [2012] available online]