Читать онлайн «Новый ум короля: О компьютерах, мышлении и законах физики». Страница 158

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, поскольку она позволяет нам записывать Tn(n) как машину Тьюринга, действующую на n.

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

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

, соответственно.

См. Мандельброт [1986]. Выбранная мною конкретная последовательность коэффициентов увеличения взята из работы Пайтгена и Рихтера [1986], в которой можно познакомиться с большим количеством цветных изображений множества Мандельброта. Другие поразительные иллюстрации можно найти в книге Пайтгена и Заупе [1988].

На самом деле при счете дат имеет место некоторое отступление от этого правила, поскольку нулевой год пропускается.

Насколько мне известно, точка зрения, согласно которой для любого действительно числа должно существовать некое — пусть неэффективное и даже совершенно неопределимое в рамках заданной формальной системы (см. главу 4) — правило, позволяющее определить его n-й знак, является вполне непротиворечивой, хотя и нетрадиционной. Я сильно надеюсь на то, что этот подход действительно непротиворечив, поскольку именно этой точки зрения я сам больше всего хотел бы придерживаться!

В книге использован символ А́леф — первая буква семитских (еврейский, иврит) алфавитов http://ru.wikipedia.org/wiki/Алеф, напоминающий N латыни.

Напомним, что 1020 означает число 100 000000000000000 000, то есть единицу с двадцатью нулями.

Величина е = 2,7182818285… (основание натуральных логарифмов, иррациональное число, по своему значению для математики сравнимое с числом π) определяется как

Слово «топологический» означает, что речь идет о разделе геометрии, — иногда называемом «геометрией резиновой поверхности», — в котором расстояния не имеют никакого значения, а важны только свойства непрерывности объектов.

В оригинале — Tor’Bled-Nam. А что получится, если прочитать наоборот? — Прим. ред.

Первенство обнаружения этого множества до сих пор остается предметом споров (см. Брукс, Мательски [1981], Мандельброт [1989]), но сама возможность таких споров представляет собой дополнительное свидетельство в пользу того, что здесь мы имеем дело скорее с открытием, чем с изобретением.

Частично основанное на более ранних работах Сципионе дель Ферро и Тартальи.

Как сказал выдающийся аргентинский писатель Хорхе Луис Борхес: «…знаменитый поэт в большей степени первооткрыватель, чем изобретатель…».

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

Рассматривая множества, члены которых, в свою очередь, также являются множествами, мы должны тщательно проводить отличия между членами такого множества и членами его членов. Например, допустим, что S — это множество непустых подмножеств некоторого другого множества Т, членами которого являются один апельсин и одно яблоко. Т в таком случае имеет свойство «двойственности», тогда как S обладает свойством «тройственности»: членами S будут множества а) из одного яблока; б) из одного апельсина и в) из одного апельсина и одного яблока — представляющие три члена S. Аналогично, множество, чьим единственным членом является пустое множество, будет иметь свойство «единичности», а не «нулевости» — в него входит один член, а именно пустое множество! При этом само пустое множество не будет иметь, конечно, ни одного члена.

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

Хотя справедливость теоремы Ферма в обшем случае пока не доказана, ее справедливость для некоторых частных случаев, таких как G(0), G(l), G(2), G(3), доказана вплоть до G(125 000). Другими словами, доказано, что куб никакого числа не может быть суммой кубов двух других положительных чисел, четвертая степень числа не может быть суммой четвертых степеней других чисел и т. д. вплоть до степени 125000. (Несколько лет назад теорема Ферма была доказана в обшем виде. См. гл. 2 «Неразрешимость проблемы Гильберта» примечание 51 — Прим. верст. fb2)

Мы можем представить себе лексиграфический способ упорядочивания как обычный способ, используемый для натуральных чисел, только сделанный «по основанию k + 1», где для k + 1 чисел берутся различные символы формальной системы, вместе с новым «нулем», который никогда не используется. (Последняя сложность возникает в связи с тем, что числа, начинающиеся с нуля, и те, где он опущен — равны.) Простое лексикографическое упорядочивание в строчках из девяти символов осуществляется при помощи натуральных чисел, которые могут быть выписаны в стандартной десятичной системе без нуля: 1,2, 3,4…,8,9, 11, 12 19,21,22 99, 111, 112…