«««Назад | Оглавление | Каталог библиотеки | Далее»»»

Прочитано: 79%

ТЕОРЕМА 3

        Пусть Y,..., Y будет как и в (35), и предположим, что L(X )< N. Возьмем полоски битов w,..., w, так чтобы они удовлетворяли:

                         (l(w  ) - 1) < L(X  )                     (37)

        и для каждой 1 < n < m

                       Y   = F(h, w , X   )                        (38)

        ДОКАЗАТЕЛЬСТВО: Определим, что

                    K   = min K  I(X  ) > 2   I(X   )            (39

         Из этого следует, что

                        I(X  ) < 2          I(X  )                 (40)

         Из определения I(X) получим:

                         I(2  X + Y) < I(X)                        (41)

         Поэтому в большинстве случаев 2   - 1  для многих Y в интервале
от 0 до 2   - 1  может удовлетворить:

                       I(2  X    + Y) > 2    I(X   )               (42)

         В соответствие с (39), неравенство (42) удовлетворяется условием
Y = Y  . Поэтому Y    есть номер полосы w в интервале от 0 до 2    ,
удовлетворяющий (42), причем w лежит в данном интервале, 1 < w < 2     .
Мы можем воспроизвести задуманную нами полосу бит w  , если необходимо,
добавив вначале w необходимые нули, так, чтобы длина этой полосы была
равна К  . Тогда (38) удовлетворится.

        Для того, чтобы доказать (37), заметим, что I(X ) не больше, чем количество полос X с L(X ) < N, и что все это не более 2. Теперь пусть n = L(X ) < N. Должна существовать некая программа Р с длиной n, вычисляющая Х. Необходимо условиться, чтобы программирующий язык позволял нам сконструировать некую программу Q, имеющую форму Q = PA, где А есть произвольная полоса, состоящая из N-n бит. Идея состоит в том, что исполняя Q, компьютер должен обращаться лишь к наставлениям в P, и не должен обращаться к А. Таким образом, А может быть в любом из 2 способов, и из этого следует, что

                      I(X  ) > 2                                   (43)

 Мы получаем (37), комбинируя (43) и (40) и I(X  ) < 2  , что и
требовалось доказать.

        Мы видим, что генерирующую функцию F определить достаточно просто. Однако, при любой проверке данного определения мы обнаруживаем, что подсчитать F на практике просто невозможно. Фактически, при существующем положении дел, подсчитать F невозможно вообще. Можно показать, что хотя L(X) есть точно определенная функция, не существует алгоритма, дающего возможность подсчитать L(X) для любого значения Х (Это обсуждается в работе Чайтина 1977). Это означает, что L(X) есть то, что известно как неисчислимая или же "нерекурсивная" функция. Поскольку F определяется при помощи L, не удивительно, что F также не поддается исчислению.
        Интересно, что мы недвусмысленно определяем числа и функции, которые теоретически вычислить невозможно. Однако, мы не будеи рассматривать здесь то, что подразумевалось под этим, поскольку мы можем легко видоизменить наши определения таким образом, чтобы F стала исчислимой. Один из способов - определить большой временной интервал прохождения нашей программы через компьютер, - С. Если поставим условие, что любая программа, укладывающаяся в этот предел, немедленно печатает С и останавливается, то обе функции L и F становятся формально исчислимыми, и все наши заключения, содержащиеся в разделах 5.1, 5.2, 5.3, остаются существенно не затронутыми (Мы должны установить достаточно большой предел времени так, чтобы программа M(X) могла бы завершить свои вычисления).
        И хотя при таком условии F становится исчислимой, все же для того, чтобы вычислить F, необходимо столь большое количество последовательных этапов, что осуществить это на практике становится просто невозможно. Поэтому кто-то может спросить: "В чем смысл рассмотрения F, если эта функция неисчислима?" Если вкратце, то ответ наш будет следующим. Если мы выберем удачный предел врнмени прохождения программы по С, мы можем написать достаточно простую программу, определяющую F (однако не в пределах времени, определяемого нашим лимитом). Эта программа состоит из нескольких простых арифметических операций, повторяющихся вновь и вновь, в соответствии с простым правилом. И теперь предположим, что подробное описание формы содержит низкое информационное содержание. Тогда мы можем использовать Теорему 3, чтобы при помощи ее показать, что последовательные разделы этого описания можно произвести, если прикладывать F к последовательному коду полос w,..., w. Как мы описывали в Разделе 5.2, добавляя сокращенные количества информации в форме полос w, мы можем воспроизвести тщательно разработанныечасти биологических описаний.
        Наш вопрос состоит в том: "Возможно ли, чтобы функция F, обеспеченная столь незначительным информационным содержанием, стала считывать последовательные описания сложных органов и биологических процессов?" Предположив, что F может сделать это, можем заключить, что простое повторение нескольких простых расчетных операций, совершаемое достаточно долгий период времени, несомненно воспроизведет некие сложные структуры, которые можно отыскать в живых организмах. Более того, получая команды, обеспечиваемые w, будут воспроизведены, как нам известно, лишь определенные структуры жизни, и ничто другое. Это, по-видимому, могло бы дать элементарным арифметическим операциям значительное могущество. Хотя мы, строго говоря, можем доказать, что F не обладает этими значительными свойствами, все-таки мы допускаем это, хотя так же серьезно мы оцениваем и последствия, которые могут иметь место, если, фактически, она ими не обладает.

ПРИЛОЖЕНИЕ 2

«««Назад | Оглавление | Каталог библиотеки | Далее»»»