Чтение онлайн

на главную

Жанры

Тени разума. В поисках науки о сознании
Шрифт:

1– > 0 1R, 0 0– > 4 0R, 0 1– > 0 1R, 1 0– > 2 1R, 1 1– > X, 2 0– > 3 1R, 2 1– > 0R, 3 0– > 55 1R, 3 1– > 0R, 4 0– > 4 0R, 4 1– > 5 1R, 5 0– > 4 0R, 51 -> 6 1R, 6 0– > 4 0R, 6 1– > 7 1R, 7 0– > 4 0R, 7 1– > 8 1R, 8 0– > 4 0R, 8 1– > 9 1R, 9 0– > 10 0R, 9 1– > 0R, 10 0– > 11 1R, 10 1– > 0R, 11 0– > 12 1R, 11 1– > 12 0R, 12 0– > 13 1R, 12 1– > 13 0R, 13 0– > 14 1R, 13 1– > 14 0R, 14 0– > 15 1R, 14 1– > 1 0R, 15 0– > 0 0R, 15 1– > 0R, 16 0– > 17 0L, 16 1– > 16 1L, 17 0– > 17 0L, 17 1– > 18 1L, 18 0– > 17 0L, 18 1– > 19 1L, 19 0– > 17 0L, 191 -> 20 1L, 20 0– > 17 0L, 20 1– > 21 1L, 21 0– > 17 0L, 21 1– > 22 1L, 22 0– > 22 0L, 22 1– > 23 1L, 23 0– > 22 0L, 23 1– > 24 1L, 24 0– > 22 0L, 24 1– > 25 1L, 25 0– > 22 0L, 251 -> 26 1L, 26 0– > 22 0L, 26 1– > 27 1L, 27 0– > 32 1R, 27 1– > 28 1L, 28 0– > 33 0R, 28 1– > 29 1L, 29 0– > 33 0R, 29 1– > 30 1L, 30 0– > 33 0R, 30 1– > 31 1L, 31 0– > 33 0R, 31 1– > 11 0R, 32 0– > 34 0L, 32 1– > 32 1R, 33 0– > 35 0R, 33 1– > 33 1R, 34 0– > 36 0R, 34 1– > 34 0R, 35 0– > 37 1R, 35 1– > 35 0R, 36 0– > 36 0R, 36 1– > 38 1R, 37 0– > 37 0R, 37 1– > 39 1R, 38 0– > 36 0R, 38 1– > 40 1R, 39 0– > 37 0R, 39 1– > 41 1R, 40 0– > 36 0R, 40 1– > 42 1R, 41 0– > 37 0R, 41 1– > 43 1R, 42 0– > 36 0R, 42 1– > 44 1R, 43 0– > 37 0R, 43 1– > 45 1R, 44 0– > 36 0R, 44 1– > 46 1R, 45 0– > 37 0R, 45 1– > 47 1R, 46 0– > 48 0R, 46 1– > 46 1R, 47 0– > 49 0R, 47 1– > 47 1R, 48 0– > 48 0R, 48 1– > 49 0R, 49 0– > 48 1R, 49 1– > 50 1R, 50 0– > 48 1R, 50 1– > 51 1R, 51 0– > 48 1R, 51 1– > 52 1R, 52 0– > 48 1R, 52 1– > 53 1R, 53 0– > 54 1R, 53 1– > 53 1R, 54 0– > 16 0L, 54 1– > 0R, 55 0– > 53 1R.

Теперь

мы готовы точно определить предельную длину предписания K, получаемого путем вышеприведенного построения, как функцию от длины алгоритма A. Сравним эту «длину» со «степенью сложности», определенной в §2.6 (в конце комментария к возражению Q8). Для некоторой конкретной машины Тьюринга T m(например, той, что выполняет вычисление A) эта величина равна количеству знаков в двоичном представлении числа m. Для некоторого конкретного машинного действия T m( n) (например, выполнения предписания K) эта величина равна количеству двоичных цифр в большем из чисел тип. Обозначим через и количество двоичных цифр в aи k'соответственно, где

A = T aи K= T k'(= C k).

Поскольку алгоритм Aсодержит, как минимум, 2 N– 1 команд (учитывая, что первую команду мы исключили) и поскольку для каждой команды требуется, по крайней мере, три двоичные цифры, общее число двоичных цифр в номере его машины Тьюринга а непременно должно удовлетворять условию

>= 6 N– 6.

В вышеприведенном дополнительном списке команд для Kесть 105 мест (справа от стрелок), где к имеющемуся там числу следует прибавить N. Все получаемые при этом числа не превышают N+ 55, а потому их расширенные двоичные представления содержат не более 2 log 2( N+ 55) цифр, в результате чего общее количество двоичных цифр, необходимых для дополнительного определения внутренних состояний, не превышает 210 log 2( N+ 55).

Сюда нужно добавить цифры, необходимые для добавочных символов 0, 1, Rи L, что составляет еще 527 цифр (включая одну возможную добавочную «команду-пустышку» и учитывая, что мы можем исключить шесть символов 0по правилу, согласно которому 0 0можно представить в виде 0). Таким образом, для определения предписания Kтребуется больше двоичных цифр, чем для определения алгоритма A, однако разница между этими двумя величинами не превышает 527 + 210 log 2( N+ 55):

< + 527 + 210 log 2( N+ 55).

Применив полученное выше соотношение >= 6 N– 6, получим (учитывая, что 210 log 26 > 542)

< - 15 + 210 log 2( + 336).

Затем найдем степень сложности конкретного вычисления C k( k), получаемого посредством этой процедуры. Вспомним, что степень сложности машины T m( n) определяется как количество двоичных цифр в большем из двух чисел m, n. В данной ситуации C k= T k, так что число двоичных цифр в числе « m» этого вычисления равно . Для того чтобы определить, сколько двоичных цифр содержит число « n» этого вычисления, рассмотрим ленту, содержащую вычисление C k( k). Эта лента начинается с последовательности символов 111110, за которой следует двоичное выражение числа k', и завершается последовательностью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней цифры) следует читать как двоичное число; эта операция дает нам номер « n», который присваивается ленте машины, выполняющей вычисление T m( n). То есть число двоичных цифр в данном конкретном номере « n» равно + 13, и, следовательно, число + 13 совпадает также со степенью сложности ту вычисления C k( k), благодаря чему мы можем записать = + 13 < — 2 + 210 log 2( + 336), или проще:

< + 210 log 2( + 336).

Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодирования машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм - исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание -исчисления Черча можно найти в НРК, конец главы 2; см. также [ 52 ].) Предположим, например, что алгоритм Aопределяется некоторым -оператором A, выполняющим действие над другими операторами Pи Q, что выражается в виде операции ( AP) Q. Оператором Pздесь представлено вычисление C p, а оператором Q— число q. Далее, оператор Aдолжен удовлетворять известному требованию, согласно которому для любых Pи Qдолжно быть истинным следующее утверждение:

Если завершается операция ( AP) Q, то операция PQне завершается.

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

K = x.[( Ax) x],

т.е. KY= ( AY) Yдля любого оператора Y. Затем рассмотрим -операцию

KK

Очевидно, что эта операция не завершается, поскольку KK= ( AK) K, а завершение последней операции означало бы, что операция KKне завершается по причине принятой нами природы оператора A. Более того, оператор Aне способен установить этот факт, потому что операция ( AK) Kне завершается. Если мы полагаем, что оператор Aобладает требуемым свойством, то мы также должны предположить, что операция KKне завершается.

Отметим, что данная процедура дает значительную экономию. Если записать операцию KKв виде

KK = y.( yy)( x.[( Ax) x]),

то становится ясно, что число символов в записи операции KKвсего на 16 больше аналогичного числа символов для алгоритма A(если пренебречь точками, которые в любом случае избыточны)!

Строго говоря, это не совсем законно, поскольку в выражении для оператора Aможет также появиться и символ « x», и с этим нам придется что-то делать. Можно усмотреть сложность и в том, что генерируемое такой процедурой незавершающееся вычисление нельзя считать операцией над натуральными числами (поскольку вторая Kв записи KK«числом» не является). Вообще говоря, -исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выразить в виде операции -исчисления. По этим и подобным причинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.

Поделиться:
Популярные книги

Штурм Земли

Семенов Павел
8. Пробуждение Системы
Фантастика:
боевая фантастика
постапокалипсис
рпг
5.00
рейтинг книги
Штурм Земли

Чехов. Книга 3

Гоблин (MeXXanik)
3. Адвокат Чехов
Фантастика:
альтернативная история
5.00
рейтинг книги
Чехов. Книга 3

Кодекс Охотника. Книга XXI

Винокуров Юрий
21. Кодекс Охотника
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Кодекс Охотника. Книга XXI

Последний попаданец 11. Финал. Часть 1

Зубов Константин
11. Последний попаданец
Фантастика:
фэнтези
юмористическое фэнтези
рпг
5.00
рейтинг книги
Последний попаданец 11. Финал. Часть 1

Право налево

Зика Натаэль
Любовные романы:
современные любовные романы
8.38
рейтинг книги
Право налево

Комбинация

Ланцов Михаил Алексеевич
2. Сын Петра
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Комбинация

Прометей: Неандерталец

Рави Ивар
4. Прометей
Фантастика:
героическая фантастика
альтернативная история
7.88
рейтинг книги
Прометей: Неандерталец

Идеальный мир для Лекаря 16

Сапфир Олег
16. Лекарь
Фантастика:
боевая фантастика
юмористическая фантастика
аниме
5.00
рейтинг книги
Идеальный мир для Лекаря 16

Двойня для босса. Стерильные чувства

Лесневская Вероника
Любовные романы:
современные любовные романы
6.90
рейтинг книги
Двойня для босса. Стерильные чувства

Деспот

Шагаева Наталья
Любовные романы:
современные любовные романы
эро литература
5.00
рейтинг книги
Деспот

На границе империй. Том 7. Часть 2

INDIGO
8. Фортуна дама переменчивая
Фантастика:
космическая фантастика
попаданцы
6.13
рейтинг книги
На границе империй. Том 7. Часть 2

Возвышение Меркурия. Книга 13

Кронос Александр
13. Меркурий
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Возвышение Меркурия. Книга 13

Ну привет, заучка...

Зайцева Мария
Любовные романы:
эро литература
короткие любовные романы
8.30
рейтинг книги
Ну привет, заучка...

Титан империи 6

Артемов Александр Александрович
6. Титан Империи
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Титан империи 6