Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики

00101010111010000101000

10111010001010011010010

00010100110100101001001

10100100010110101000101

11010010010101110100101

00011101010010100100111

01010101000011010010101

01011101010010001011010

10000101101010001001101

01010101000101101001010

10010010110101001001011

10101010010101110101001

01001101010100001110100

01001001010111010101001

01011101010100000111010

10010000011010101010010

11101010010101101000100

10001110100000001110100

10100101010101110100101

00100101011101000001010

11101000010001110100000

10101001110100001010011

10100000100010111010001

00001110100001001010011

10100010000101101000101

00101110100010100101101

00100000101101000101010

01001101000101010101110

10010000011101001001010

10101110101010100110100

10001010110100100100101

10100000001011010000010

00110100000100101101000

00000011010010100010111

01001010100011010010100

10101101000001001110100

10101001011010010011101

01000000101011101010000

00110101010001010101101

00101010110101000010101

11010100100101011101010

00100101101010010000101

11010000001110101001000

10110101001010011010101

00010111010100101001011

10101010000010111010101

00000101110100000011101

01010000101011101001010

10110101010000101110101

00010101011101010100100

10111010101010000111010

10000000111010010010000

11010010010001011010101

01010011101000000001011

01001000011010101010100

10111010010000110100100

01010101110100001000111

01000100001110100001101

00000001011010000010010

11101010100101010110100

01000100101110100000100

11101010100110100000101

01011010000100001110100

10000100011101010101010

10011101000010010011101

00010010000111010000101

00101101000010100001110

10101010101011101000100

10011010001001001101010

01010010111010001000101

01110100000001110100010

01001011101001101001001

00001011010101010011010

00101000101110100001101

01000010001011010100110

10101001010010110101010

01101001001010111010011

01001000001011010001010

10100011101001000010101

10100000010011010010001

00101110100100001101010

00001001011101001001010

01101001001010101101001

10100100101001011010011

01001010000010110100100

00011101010010011010101

01000010111010010100001

01110100101010101110101

00010010110100100111010

01010100010111010001001

11010100001011010010011

10100101010101011101001

00011101001010101001011

10100100011101010000010

10101110011010100000101

10100100111010100000010

11101001011010100000101

01101001010010111010100

00100101110100001101010

00100001011010100110101

00010001011010101010010

11101010001010010110100

01010101011101001000010

10110101000101110101001

00101010111010101001001

01110101000111010100011

10101001001001011101010

00111010100101000101110

10100010111010100001001

01110101000111010001010

00101110100101001011101

01001010100101110100101

01010101011010100001010

10101101000010011101000

01010101010111010101000

10101110101010001010111

01000000111010101000100

10111010000001110101010

01000101110101000000110

10100001011010000001110

10010000001011101010001

11010100100010101110101

00110101010100010101101

00000110101010100101010

11010000001001101010101

00100111010100110101010

10010010110101001101001

00100111010000011010101

01010010101101010001001

10100010100101010111010

00001101010101010100101

10100010001110100010101

01010101101000100011101

00001010111010001001000

01110100110100000001001

11010000001001011101000

10001010011101000000100

10111010010101010100101

10100001010101011101000

10010100101110100000100

01011101010100101101000

10001001110100000100101

01110100000010101011010

00010001110011110100001

00000111010000100100111

01000001010010111010000

01010010110100001000101

01110100001000100110100

01000011101011110100001

00100101110100001001001

01110100000001010111010

00010101000110100010010

11101000010000011101000

01001110100010000010111

01010100101101000100000

10111010000101010101110

10000001010101110100010

00010101110100010000101

01110100100000111010100

10010011010000001010111

01000100010010111010101

00001110101001010110100

10101010000110100000101

00110100000001110100000

10010011101001011010010

00101001011010101001101

00010100100101101010100

11010001010100010110011

01010010010111010101001

10100010101010101100110

10100010101011001101001

00010101010111010001000

11101001001010101010110

10010100101000110100100

00001011101000001101010

10010101010110100101010

11010010001000101110100

01010101101010000010101

10100010000011010010001

01011010000100111010100

10101010101110100101101

00100100010101100110100

10010010101011101001101

00100100101011010010110

10010010010010110100101

10100100101000101100110

10010010100101011101000

10101110100100101110011

01001001010100101110011

01001010001010101110100

01000111010000101001011

01001010001011101001010

00101011010001001110100

10100010010111010001001

11010010100100010111001

10100100010001110100010

01110100101001010101110

01101001010000011100110

10101010101101000000011

10100101010010101011101

00100011101001010100101

01110011010000101001001

10011010100000110100000

00111010010101010010101

11001101010001000011010

00000011101000100101010

10111010001000111010101

01010101010110100001001

11010010001001010111010

01010100010011010100000

00101101001001110101000

01010111010010000110101

00000001011010010001110

10100100101110100001101

01000010101011010100010

11101010000101001011101

01000101110101000101010

10111001101010001010110

100001101010001001010

Пытливый читатель, вооруженный эффективным домашним компьютером, быть может захочет проверить, используя данные в тексте предписания и применяя эту последовательность к номерам различных простых машин Тьюринга, что она и в самом деле соответствует универсальной машине Тьюринга! Некоторое уменьшение величины и может быть достигнуто за счет другого определения машины Тьюринга. Например, мы могли бы отказаться от использования команды STOP и вместо этого применять правило остановки после того, как машина повторно возвращается во внутреннее состояние 0 из какого-либо другого внутреннего состояния. Это не дало бы нам значительного выигрыша (а может, и вовсе никакого). Большую пользу принесло бы использование лент с иными, нежели только 0и 1, отметками. В литературе встречаются описания очень компактных на вид машин Тьюринга, но эта компактность обманчива, поскольку она обусловлена чрезмерно сложным кодированием описаний машин Тьюринга вообще.

Напомним, что натуральными мы называем числа 0,1,2,3,4,5,6… Вместо обычной записи ( x ω + y ω = z ω , где х, у, z > 0, ω > 2) мы используем «х + 1», « ω + 3» и т. д., чтобы включить в рассмотрение все натуральные числа, начиная с нуля.

Желающие ознакомиться с вопросами, имеющими отношение к этому знаменитому утверждению и изложенными без излишних технических подробностей, могут обратиться к работе Дэвлина [1988].

Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. — Прим. ред .

Напомним, что простые числа 2, 3, 5, 7, 11, 13, 17… - это такие натуральные числа, которые делятся только на самих себя и на единицу. Ни нуль, ни единица простыми числами не считаются.

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

Фактически, самую трудную часть мы уже выполнили, когда построили универсальную машину Тьюринга U, поскольку она позволяет нам записывать T n ( n ) как машину Тьюринга, действующую на n .

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

В более привычной форме эта запись имела бы вид а = b(с), но эти дополнительные скобки в действительности не нужны, поэтому лучше просто привыкнуть к их отсутствию. Их последовательное использование привело бы к довольно громоздким формулам вида