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

при любом n. Таким образом, действие предписания K сводится к тому, чтобы взять число n (записанное в пятеричном выражении) и однократно его скопировать, при этом два n разделяются последовательностью 111110 (та же последовательность начинает и завершает всю последовательность отметок на ленте). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алгоритм A.

Явную модификацию алгоритма A, дающую такое предписание K, можно произвести следующим образом. Сначала находим в определении A начальную команду 01 → X и отмечаем для себя, что это в действительности за «X». Мы подставим это выражение вместо «X» в спецификации, представленной ниже. Один технический момент: следует, помимо прочего, положить, чтобы алгоритм A был составлен таким образом, чтобы машина, после активации команды 01 → X, никогда больше не перешла во внутреннее состояние 0 алгоритма A. Это требование ни в коей мере не влечет за собой каких-либо существенных ограничений на форму алгоритма[19]. (Нуль можно использовать только в командах-пустышках.)

Затем при определении алгоритма A необходимо установить общее число N внутренних состояний (включая и состояние 0, т.е. максимальное число внутренних состояний A будет равно N - 1). Если в определении A нет завершающей команды вида (N - 1)1 → Y, то в конце следует добавить команду-пустышку (N - 1)1 → 00R. Наконец, удалим из определения A команду 01 → X и добавим ее к приводимому ниже списку машинных команд, а каждый номер внутреннего состояния, фигурирующий в этом списке, увеличим на N (символом ∅ обозначено результирующее внутреннее состояние 0, а символом «X» в записи «11 → X» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 01 → N1R, N0 → (N + 4)0R.)

∅1 → 01R, 00 → 40R, 01 → 01R, 10 → 21R, 11 → X, 20 → 31R, 21 → ∅0R, 30 → 551R, 31 → ∅0R, 40 → 40R, 41 → 51R, 50 → 40R, 51 → 61R, 60 → 40R, 61 → 71R, 70 → 40R, 71 → 81R, 80 → 40R, 81 → 91R, 90 → 100R, 91 → ∅0R, 100 → 111R, 101 → ∅0R, 110 → 121R, 111 → 120R, 120 → 131R, 121 → 130R, 130 → 141R, 131 → 140R, 140 → 151R, 141 → 10R, 150 → 00R, 151 → ∅0R, 160 → 170L, 161 → 161L, 170 → 170L, 171 → 181L, 180 → 170L, 181 → 191L, 190 → 170L, 191 → 201L, 200 → 170L, 201 → 211L, 210 → 170L, 211 → 221L, 220 → 220L, 221 → 231L, 230 → 220L, 231 → 241L, 240 → 220L, 241 → 251L, 250 → 220L, 251 → 261L, 260 → 220L, 261 → 271L, 270 → 321R, 271 → 281L, 280 → 330R, 281 → 291L, 290 → 330R, 291 → 301L, 300 → 330R, 301 → 311L, 310 → 330R, 311 → 110R, 320 → 340L, 321 → 321R, 330 → 350R, 331 → 331R, 340 → 360R, 341 → 340R, 350 → 371R, 351 → 350R, 360 → 360R, 361 → 381R, 370 → 370R, 371 → 391R, 380 → 360R, 381 → 401R, 390 → 370R, 391 → 411R, 400 → 360R, 401 → 421R, 410 → 370R, 411 → 431R, 420 → 360R, 421 → 441R, 430 → 370R, 431 → 451R, 440 → 360R, 441 → 461R, 450 → 370R, 451 → 471R, 460 → 480R, 461 → 461R, 470 → 490R, 471 → 471R, 480 → 480R, 481 → 490R, 490 → 481R, 491 → 501R, 500 → 481R, 501 → 511R, 510 → 481R, 511 → 521R, 520 → 481R, 521 → 531R, 530 → 541R, 531 → 531R, 540 → 160L, 541 → ∅0R, 550 → 531R.

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

A = T_a и K = T_k'(= C_k).