Сильный ИИ и китайская комната Серла

⇐ ПредыдущаяСтр 3 из 58Следующая ⇒

Существует точка зрения, называемая сильный ИИ , которая занимает весьма радикальную позицию по этим вопросам[30]. Согласно теории сильного ИИ , не только вышеупомянутые устройства будут разумны и наделены интеллектом — свойства разума могут быть присущи логическим действиям любого вычислительного устройства, даже простейших из них, механических, одним из которых является, например, термостат[31]. Основная идея заключается в том, что умственная деятельность — это просто выполнение некоторой хорошо определенной последовательности операций, часто называемой алгоритмом . Далее я уточню это понятие. А пока нам будет достаточно определить алгоритм как своего рода вычислительную процедуру. В случае термостата алгоритм чрезвычайно прост: устройство фиксирует повышение или понижение температуры по отношению к заданной величине и размыкает или замыкает цепь, соответственно. Алгоритм, соответствующий более-менее нетривиальной деятельности головного мозга, должен быть гораздо более сложноструктурированным, но — согласно концепции сильного ИИ — это будет все же алгоритм. Он будет очень значительно отличаться от простейшего алгоритма термостата по степени сложности, но не обязательно будет иметь принципиальные отличия. Таким образом, с точки зрения сильного ИИ , существенная разница между деятельностью человеческого мозга (включая все проявления сознания) и работой термостата состоит единственно в этой самой усложненности (или, возможно, «структуре более высокого порядка», или «способности обращения к самому себе», или в любом другом свойстве, которое можно приписать алгоритму), имеющей место в первом случае.

И, что более важно, все свойства ума — мышление, способность чувствовать, интеллект, понимание, сознание — должны рассматриваться, согласно этому подходу, просто как разные аспекты сложной деятельности; иными словами, они есть не более, чем свойства алгоритма , выполняемого мозгом. Достоинства любого конкретного алгоритма заключаются в его «технических характеристиках», таких как точность результатов, область применимости, экономичность и скорость выполнения. Алгоритм, нацеленный на подражание тому, что, как предполагается, действует в мозге человека, должен быть невообразимо сложным. Но если такой алгоритм для мозга существует — а это как раз то, что с уверенностью утверждают поборники идеи сильного ИИ , — то он в принципе мог бы быть запущен на компьютере. В сущности, он мог бы выполняться на любом современном компьютере общего назначения, если бы не имеющиеся ограничения по скорости и пространству для хранения данных. (Обоснование этого замечания будет дано позднее, когда мы перейдем к рассмотрению универсальной машины Тьюринга.) Предполагается, что такие ограничения будут сняты с появлением в недалеком будущем мощных быстродействующих машин. Тогда такой алгоритм, если он будет открыт, мог бы, вероятно, пройти тест Тьюринга. И как только он будет запущен, считают сторонники сильного ИИ , он будет сам по себе испытывать чувства, обладать сознанием, быть разумом.

Далеко не каждый согласится с тем, что разумные состояния и алгоритмы можно считать идентичными в указанном контексте. Наиболее остро критиковал эту точку зрения американский философ Джон Серл [1980, 1987]. Он приводил в пример ситуации, когда должным образом запрограммированный компьютер проходил упрощенную версию теста Тьюринга, и все же — он подкрепляет эти выводы очень сильными аргументами — «понимание» как свойство интеллекта полностью отсутствовало. Один из таких примеров базируется на компьютерной программе, разработанной Роджером Шенком (Шенк, Абельсон [1977]). Задачей программы была имитация понимания простых историй типа: «Мужчина вошел в ресторан и заказал гамбургер. Когда гамбургер принесли, оказалось, что он сильно подгорел, и рассерженный мужчина выскочил из ресторана, не заплатив по счету и не оставив чаевых». В качестве второго примера можно взять другую историю: «Мужчина вошел в ресторан и заказал гамбургер. Когда его принесли, мужчина остался им очень доволен. И, покидая ресторан, он дал официанту щедрые чаевые перед тем, как заплатить по счету». Чтобы проверить «понимание» этих историй компьютером, его «попросили» определить, съел ли мужчина гамбургер в каждом отдельном случае (факт, который не был упомянут в тексте явным образом). На этот простой вопрос к таким простым историям компьютер может дать ответ, совершенно неотличимый от того, что дал бы англоговорящий человек, а именно: «нет» в первом случае и «да» — во втором. Так что в этом, очень узком, смысле машина уже прошла тест Тьюринга!

Вопрос, к которому мы должны далее обратиться, будет таким: действительно ли подобный положительный результат указывает на истинное понимание, демонстрируемое компьютером — или, возможно, заложенной в него программы? Как аргумент в пользу отрицательного ответа на этот вопрос, Серл предлагает свою концепцию «китайской комнаты». Он сразу же оговаривает, что истории должны рассказываться на китайском, а не на английском языке — совершенно несущественная замена — и что все команды для компьютерного алгоритма в этом конкретном случае должны быть представлены набором (английских) инструкций для работы со счетами, на которые нанесены китайские символы. Проводя мысленный эксперимент, Серл представлял, что он сам выполняет все манипуляции внутри запертой комнаты. Последовательность символов, описывающая истории, и вопросы к ним подаются в комнату через небольшие прорези. Никакой другой информации извне не допускается. В конце, когда все действия выполнены, последовательность, содержащая ответ, выдается из той же прорези наружу. Поскольку все эти операции есть не что иное, как составляющие процедуры выполнения алгоритма по программе Шенка, то эта последовательность должна содержать просто китайские символы, означающие «да» или «нет» и дающие корректный ответ на вопрос, который — как, собственно, и сама история — был изложен по-китайски. При этом Серл недвусмысленно дает понять, что он не знает ни слова по-китайски, и посему не имеет ни малейшего представления о содержании рассказанных историй. Тем не менее, выполнив ряд действий, составляющих алгоритм Шенка (инструкции к которому были даны ему на английском языке), он справился бы с задачей не хуже китайца, способного без труда понять эти истории. Довод Серла — и весьма сильный, по моему мнению, — заключается в том, что простое выполнение подходящего алгоритма еще не говорит о понимании. (Воображаемый) Серл, запертый в китайской комнате, не понимает ни на йоту, о чем идет речь в этих историях!

Против доказательства Серла был выдвинут ряд возражений. Я изложу здесь только те из них, которые — на мой взгляд — имеют серьезное значение. Прежде всего, фраза «не знает ни слова», если рассматривать ее в вышеприведенном контексте, является не вполне корректной. Понимание относится не только к отдельным словам, но и к определенным шаблонам. И при выполнении подобных алгоритмов можно в достаточной степени разобраться в структурах, которые составлены из символов, значение каждого из которых в отдельности останется непонятным. Например, китайский иероглиф, соответствующий «гамбургеру» (если он вообще существует), можно заменить на название какого-нибудь другого блюда, допустим, «чоу мейн»[32]), существенно не изменив при этом содержание истории. Однако, мне все-таки кажется, что настоящий смысл историй (даже если считать такие подстановки незначительными) едва ли «дойдет» до того, кто будет просто скрупулезно выполнять шаг за шагом подобные алгоритмы.

Во-вторых, нужно всегда помнить о том, что выполнение даже сравнительно простой компьютерной программы оказывается в большинстве случаев длительным и трудным процессом, если за него берется человек, манипулирующий символами. (В конце концов, именно по этой причине мы доверяем такие действия компьютерам!) Если бы Серл в самом деле выполнял указанным выше способом алгоритм Шенка, то ему для ответа на совсем простой вопрос понадобились бы дни, месяцы, а то и годы изнурительно однообразной работы — не слишком правдоподобное занятие для философа! Однако, это не представляется мне таким уж серьезным возражением, поскольку здесь мы рассматриваем вопрос в принципе и не касаемся технических деталей. Больше затруднений вызывает предположение о наличии компьютерной программы, способной сравниться с человеческим мозгом и, тем самым, безупречно пройти тест Тьюринга. Любая подобная программа должна быть невероятно сложной. Нетрудно вообразить, что действие такой программы, необходимое для нахождения ответа даже на сравнительно простой вопрос теста Тьюринга, состояло бы из столь большого количества шагов, что ни для одного человеческого существа выполнение соответствующего алгоритма за период, равный средней продолжительности жизни, было бы невозможным. Так ли это на самом деле — трудно сказать, не имея подобной программы в своем распоряжении[33]. Но, в любом случае, вопрос о чрезвычайной сложности (программы), по-моему, игнорировать нельзя. Понятно, что мы говорим о принципиальной стороне дела; и все же мне не кажется таким уж невероятным существование некоторой «критической» степени сложности алгоритма, которой необходимо достигнуть, чтобы алгоритм начал обладать качествами разума. Возможно, это критическое значение так велико, что ни один алгоритм, имеющий столь сложную структуру, не может быть выполнен вручную ни одним человеческим существом, как то предлагает Серл.

Сам Серл в качестве контраргумента к последнему возражению предлагает заменить фигурирующего ранее «жильца» (самого себя) китайской комнаты — целой командой не понимающих китайский язык манипуляторов символами. Чтобы сделать это число достаточно большим, он даже допускает возможность замены своей комнаты всей Индией, где все население (кроме понимающих китайский!) будет производить действия над символами. Хотя с практической точки зрения это было бы безумием, принципиально это далеко не абсурдная модель, которая не вносит существенных изменений в первоначальные выводы: те, кто манипулирует символами, по-прежнему не понимают содержание историй, вопреки утверждениям сторонников сильного ИИ о том, что простое выполнение подходящего алгоритма вызвало бы возникновение присущего интеллекту свойства «понимания». Однако, теперь это возражение оттесняется на задний план другим, кажущимся серьезнее: что, если эти индийцы более похожи на отдельные нейроны в человеческом мозгу, чем на этот мозг в целом? Никто никогда не будет ожидать от нейронов, чье возбуждение, по-видимому, является центральным механизмом умственной деятельности, чтобы они сами понимали, о чем думает их «хозяин» — так почему же индийцы должны понимать китайские истории? Серл парирует это возражение, указывая на явную абсурдность представления об Индии как реальной стране, понимающей некую историю, в то время как все ее население не имеет о ней ни малейшего понятия. Страна, говорит он, как и термостат или автомобиль, не «занимается» пониманием — это прерогатива индивидуумов, проживающих на ее территории.

Этот аргумент выглядит значительно слабее предыдущего. Я думаю, что доказательство Серла наиболее убедительно в случае одного исполнителя алгоритма, где мы должны ограничиться алгоритмом, чья степень сложности допускает его выполнение за время, не превышающее нормальную продолжительность человеческой жизни. Я не рассматриваю этот аргумент как непреложное свидетельство того, что не существует никакого бестелесного «понимания», ассоциируемого с процессом выполнения алгоритма людьми, чье присутствие никак не влияет на их собственное сознание. Однако, я бы скорее согласился с Серлем, что эта возможность представляется, мягко говоря, малоправдоподобной. Мне сдается, что довод Серла весьма убедителен, хотя и не является решающим. Он с очевидностью демонстрирует, что алгоритм такой степени сложности, которой обладает компьютерная программа Шенка, не может иметь какого бы то ни было понимания выполняемых задач; также из него предположительно следует (и не более того), что ни один алгоритм, независимо от сложности его структуры, не может сам по себе воплощать настоящее понимание — вопреки утверждениям поборников сильного ИИ .

Существуют, на мой взгляд, и иные очень серьезные проблемы, связанные с сильным ИИ . Согласно этой точке зрения, единственное, что имеет значение — это алгоритм. И совершенно неважно, кто приводит его в действие: человеческий мозг, электронный компьютер, целое государство индийцев, механическое устройство из колесиков и шестеренок или система водопроводных труб. В рамках этой теории существенным для воплощения заданного «состояния разума» является сама логическая структура алгоритма, а его физическая реализация никакой роли не играет. Но, как указывает Серл, это может привести к определенной форме дуализма. Дуализм — это философское мировоззрение, апологетом которого был в высшей степени влиятельный философ и математик XVII века Рене Декарт, утверждавший, что существуют две различные субстанции: «разумная субстанция» и обычная материя. Влияют ли они друг на друга, и если да, то каким образом — это уже отдельный вопрос. Ключевое положение этой точки зрения заключается в гипотезе о том, что «разумная субстанция» не может состоять из материи обычной и способна существовать независимо от нее. «Разумная субстанция» в представлениях сильного ИИ — это логическая структура алгоритма. Как я отмечал выше, ее физическое воплощение не имеет никакого значения. Алгоритм обладает неким бесплотным существованием, никак не связанным с конкретной физической реализацией. Насколько серьезно мы должны воспринимать такой вид существования — вопрос, к которому мне придется вернуться в следующей главе. Он представляет собой часть более глобального вопроса о платонистической реальности абстрактных математических объектов.

Пока же я обойду эту общую тему стороной и отмечу только, что сторонники сильного ИИ , по-видимому, принимают всерьез возможность подобного существования в случае алгоритмов, полагая, что те являются самой «сущностью» их мыслей, чувств, понимания и сознательного восприятия. В связи с этим Серл указал на примечательный в своей ироничности факт: теория сильного ИИ может привести к крайней форме дуализма — к той точке зрения, к которой сторонники сильного ИИ менее всего хотели бы иметь отношение!

Эта дилемма просматривается в рассуждениях, предложенных Дугласом Хофштадтером [1981] — убежденным сторонником сильного ИИ — в диалоге с названием «Беседа с мозгом Эйнштейна» . Хофштадтер выставляет на обозрение книгу, имеющую абсурдно большие размеры и содержащую, по его утверждению, полное описание мозга Альберта Эйнштейна. Идея такова: на любой вопрос, который кто-либо пожелал бы задать Эйнштейну, можно получить ответ в точности такой, каким был бы ответ живого Эйнштейна, если просто листать книгу и тщательно следовать всем приведенным в ней инструкциям. Конечно же, слово «просто» здесь совершенно неуместно, как то особо оговаривает сам Хофштадтер. Ведь смысл его утверждения иной: принципиально эта книга полностью эквивалентна (в операционалистском смысле теста Тьюринга) до смешного медленной «версии» настоящего Эйнштейна. Тем самым, если следовать положениям теории сильного ИИ , эта книга должна была бы думать, чувствовать, понимать и осознавать в точности так, как это делал бы сам Эйнштейн, только невероятно медленно (так что для этого «книго -Эйнштейна» внешний мир казался бы мелькающим перед ним с огромной скоростью). И естественно, что книга, представляющая из себя частную реализацию алгоритмизованной «сущности» Эйнштейна, была бы как раз-таки самим Эйнштейном.

Но тут возникает другая трудность. Книгу могут не открыть ни разу — или же, напротив, над ней будут корпеть многочисленные студенты и искатели истины. Как книга «поймет» разницу между этими двумя крайностями? Возможно, книгу даже не понадобится открывать, если в ход будет пущено считывание информации при помощи рентгеновской томографии или какое-нибудь другое технологическое чудо-средство. Осознает ли Эйнштейн, что книга изучается подобным образом? Будет ли он знать о двух попытках найти с его помощью ответ на один и тот же вопрос, если он был задан дважды, разными людьми и в разное время? Или это вызовет две разделенные по времени копии одного и того же состояния осознания? Возможно, акт осознавания будет иметь место только в случае изменений, произошедших с книгой? В конце концов, мы обычно осознаем нечто, когда получаем о нем информацию извне, которая воздействует на наши воспоминания и, естественно, несколько изменяет состояние нашего ума. Если это так, то означает ли это, что именно (соответствующие) изменения алгоритмов (здесь я рассматриваю хранилище информации как часть алгоритма) должны приниматься за события, происходящие в процессе умственной деятельности — а не само выполнение (хотя, быть может, и оно тоже) алгоритмов? Или же «книго-Эйнштейн» способен полностью осознавать себя даже в том случае, когда его никто не будет изучать и ничто не потревожит? Хофштадтер затрагивает некоторые из этих вопросов, но на большинство из них он даже не пытается по-настоящему ответить или хотя бы подробно разобраться с ними.

Что значит «запустить алгоритм» или «реализовать его физически»? Будет ли изменение алгоритма как-нибудь отличаться от его замены на другой алгоритм? И как же все это, черт побери, связано с нашими чувствами и осознаванием?! Читатель (если только он не принадлежит к лагерю сторонников сильного ИИ ) может удивиться, видя сколько времени я уделяю такой заведомо абсурдной идее. Но я-то, и в самом деле, не считаю ее изначально абсурдной — только лишь неверной! Некоторые рассуждения, на которые опирается теория сильного ИИ , я считаю достаточно убедительными и попытаюсь обосновать свое мнение ниже. В некоторых идеях — если их модифицировать подходящим образом — есть, на мой взгляд, определенная привлекательность, которую я также постараюсь передать.

Более того: как мне кажется, те самые контраргументы, которые приводит Серл, в свою очередь тоже содержат ряд серьезных головоломок и кажущихся нелепостей — хотя, в какой-то степени, я с ним и согласен!

Серл в ходе своих рассуждений неявным образом признает, что сегодняшние электронные компьютеры, снабженные значительно увеличенными быстродействием и размерами устройств хранения информации с высокой скоростью обмена данными (и, возможно, параллельным выполнением операций), вполне могли бы в обозримом будущем успешно пройти тест Тьюринга. Он готов признать утверждение сторонников сильного ИИ (и многих других «научных» точек зрения), что мы «просто конкретные экземпляры реализации некоторого числа компьютерных программ». Более того, он соглашается и с тем, что: «Конечно, наш мозг является цифровым компьютером. Поскольку всё есть цифровые компьютеры, то и мозг — тоже[34]» Серл полагает, что разница между действием человеческого мозга (который может иметь разум) и электронным компьютером (который, как он утверждает, такого свойства не имеет), когда они выполняют один и тот же алгоритм, состоит исключительно в материальной конструкции того и другого. Он заявляет — правда, не давая этому никакого обоснования — что биологические объекты (мозг) могут обладать «ментальностью» и «семантикой», которые он считает основополагающими для умственной деятельности, тогда как компьютеры — нет. Само по себе, как мне кажется, это не может указать направление развития некой полезной научной теории интеллекта. Что уж такого особенного есть в биологических системах — если не принимать в расчет их «исторический» путь развития (и того, что мы оказались как раз такими системами), — что могло бы выделить их в качестве объектов, которым позволено «дорасти» до ментальности или семантики? Это заявление подозрительно напоминает мне догматическое утверждение, причем не менее догматического свойства, чем утверждения сторонников сильного ИИ о том, что, просто выполняя алгоритм, можно вызвать состояние осознанного восприятия!

По-моему, Серл, как и многие другие, были введены в заблуждение компьютерщиками. А тех, в свою очередь, сбили с толку физики. (Но это не вина физиков. Даже они не в состоянии знать все обо всем!) Вера в то, что «все на свете является цифровыми компьютерами», кажется общераспространенной. И я намерен показать в этой книге, что это совсем не обязательно так.

«Железо» и «софт»

На компьютерном жаргоне слово «железо» используется для обозначения всех устройств и элементов, из которых состоит компьютер (печатные платы, транзисторы, провода, накопители на магнитных дисках, и т. п.), включая также полное руководство по сборке. Аналогичным образом термин «софт» относится к различным программам, которые могут выполняться на компьютере. Одним из замечательных открытий Тьюринга было то, что, по существу, любая машина с начинкой из «железа», характеризуемого определенной степенью сложности и гибкости, эквивалентна любой другой машине с такими параметрами. Эквивалентность двух машин (скажем, А и В) здесь должна пониматься в смысле точного соответствия действий А — при соответствующем заложенном в нее программном обеспечении — действиям В, и наоборот. Я употребляю здесь слово «точный» по отношению к конечным результатам, получающимся при введении в машины произвольных начальных данных (после того, как уже было введено преобразующее программное обеспечение), а не в смысле равенства времени, затраченного каждой машиной на получение ответа. Кроме этого, я допускаю для обеих машин возможность получения доступа к дополнительным (и, в принципе, неограниченным) внешним запасам чистых «черновиков» — магнитным пленкам, дискам, барабанам или иным носителям информации, — если какая-либо из них начинает испытывать нехватку в пространстве для хранения промежуточных результатов вычислений. Вообще говоря, разница между машинами А и В в затрачиваемом на выполнение некоторого задания времени может оказаться весьма серьезной. Вполне возможно, например, что машина А будет выполнять определенную задачу в тысячу раз быстрее, чем В. Равным образом может статься, что для другого задания время его выполнения машиной В окажется в тысячу раз меньше, чем машиной А. Более того, эти конкретные показатели могут в значительной степени зависеть от выбора используемых для конвертации программ. Но в рамках этой дискуссии нет нужды рассматривать такие практические аспекты, как способность выполнять вычисления за определенное время, поскольку наши рассуждения носят по большей части «принципиальный» характер. В следующем разделе я конкретизирую содержание тех концепций, которые затрагиваются здесь: машины А и В являют собой примеры того, что называют универсальными машинами Тьюринга .

В сущности, все современные общеупотребительные компьютеры — это универсальные машины Тьюринга. Тем самым все такие компьютеры будут эквивалентны друг другу в вышеупомянутом смысле: различия между ними будут заключаться единственно в программном обеспечении, при условии, что нас не волнует разница в скорости выполнения операции и возможные ограничения пространства для хранения данных. Но современные технологии сделали компьютеры способными работать так быстро и с такими огромными объемами памяти, что для большей части «повседневных» задач ни один из этих практических аспектов не накладывает серьезных ограничений на спектр решаемых такими компьютерами задач[35] — так что эта эффективная эквивалентность, введенная на теоретическом уровне, просматривается и на практике. Кажется, что технология превратила совершенно абстрактные когда-то академические дискуссии об идеальных вычислительных устройствах — в устройства реальные, и непосредственно влияющие на нашу жизнь!

Насколько я могу понять, одним из наиболее важных положений, на которых базируется философия сильного ИИ , является именно эта эквивалентность между различными физическими вычислительными устройствами. «Железо» расценивается как сравнительно (или вообще) несущественный фактор, в то время как «софт», т. е. программа или алгоритм, считается единственным жизненно важным компонентом. Однако, мне кажется, что существуют и другие, не менее важные «краеугольные камни здания сильного ИИ », которые следуют из физики. Сейчас я попытаюсь дать некоторое представление об их природе.

Что позволяет нам идентифицировать себя как личность? Может быть, в какой-то степени — сами атомы наших тел? Особое сочетания электронов, протонов и других частиц, из которых состоят эти атомы? Есть, по крайней мере, два возражения против этого предположения. Во-первых, вещество тела любого живого существа претерпевает постоянные изменения и обновления. Это справедливо, в частности, для клеток головного мозга, несмотря на то, что после рождения новые клетки уже не образуются. Абсолютное большинство атомов в каждой живой клетке (включая все клетки мозга) — и, конечно же, практически все ткани нашего тела — замещаются новыми по много раз с момента рождения.

Второе возражение приходит из квантовой физики — и, по странной иронии, находится, строго говоря, в прямом противоречии с первым! Согласно квантовой механике (и мы узнаем об этом больше в главе 6) любые два электрона должны быть с необходимостью одинаковыми; и то же самое справедливо в отношении двух произвольно взятых протонов или пары любых других частиц, относящихся к одному типу. То, что подразумевается под этим, отнюдь не ограничивается утверждением об их неразличимости — оно значительно сильнее. Если пришлось бы поменять между собой электрон в человеческом мозге и электрон в кирпиче, то состояние системы осталось бы в точности тем же самым[36] , что и до этого — тем же самым, а не просто неотличимым! Аналогичное правило справедливо и для протонов, и для других разновидностей частиц, а также для целых атомов, молекул и т. п. Если весь материал человеческого тела заместить соответствующими частицами кирпичей из его дома, то, в буквальном смысле, вообще ничего не изменится.

То, что отличает человека от своего дома — это то, в какую структуру организованы составляющие его тела, а не индивидуальные свойства этих составляющих.

Можно привести аналогию из повседневной жизни, не имеющую отношения к квантовой механике, которая бросилась мне в глаза, пока я набирал эти строки, имея в своем распоряжении один из плодов информационной технологии — текстовый редактор. Если я хочу изменить слово, скажем, «болт» на «борт», то могу сделать это просто заменив букву «л» буквой «р»; или же я могу вместо этого напечатать все слово заново. Выбрав последний вариант, я встану перед вопросом: а та ли это теперь буква «б», что была ранее, или я заменил ее идентичной? А как насчет «т»? Даже если я решу просто поменять букву «л» на «р», а не перебивать все слово заново — будет момент, как раз между удалением «л» и появлением «р», когда пустое место «схлопывается» и по всему тексту сверху вниз пройдет волна перестановок, при которых пересчитывается расположение всех букв, включая «т» — а затем перепересчитывается еще раз при вставке на то же место «р». (Ох уж эта дешевизна бездумных вычислений в наши дни!) В любом случае, все буквы, которые я вижу на экране, есть не более чем разрывы на пути следования электронного луча в процессе сканирования всего экрана, происходящего шестьдесят раз в секунду. Если я возьму произвольную букву и заменю ее на такую же — сохранится ли при этом исходное состояние точно таким же или оно будет только лишь неотличимо? Попытка провести смысловое разделение между двумя этими определениями нового состояния (т. е. между «только лишь неотличимое» и «точно такое же») кажется несерьезной. По крайней мере, коль скоро замещающая буква является идентичной, возникает желание назвать это состояние таким же. И то же самое верно и для квантовой механики одинаковых частиц. Поменять одну из частиц на другую, эквивалентную — все равно, что не поменять ничего. Состояние при этом должно считаться тем же самым , что и в начале. (Однако, как станет ясно в главе 6, подобное различие не так уж тривиально в контексте квантовой механики.)

Рассуждения, сделанные выше по поводу непрерывного обновления атомов человеческого тела, надо рассматривать скорее в рамках классической физики, нежели квантовой. В этих рассуждениях используется терминология, которая неявно подразумевает возможность индивидуального существования каждого атома. На этом уровне описания классическая физика вполне адекватна и мы не слишком погрешим против истины, если будем рассматривать атомы в качестве отдельных объектов. При условии, что атомы достаточно хорошо отделены друг от друга в процессе движения, можно было бы говорить об их индивидуальном существовании, поскольку каждый атом допускает в этом случае непрерывное наблюдение за собой. С точки зрения квантовой механики говорить об индивидуальности атомов можно только ради удобства описания, однако на рассматриваемом уровне это вполне допустимо.

Давайте примем, что индивидуальность человека никак не связана с индивидуальностью, которую можно было бы постараться приписать его материальной основе. Вместо этого она должна определяться своего рода конфигурацией составляющих элементов этой основы — их пространственной или, допустим, пространственно-временнбй структурой. (Подробно об этом — далее.) Но сторонники сильного ИИ идут еще дальше. Если информационное содержание такой конфигурации перевести в другую форму, из которой затем можно было бы полностью восстановить оригинал, то, согласно их утверждению, индивидуальность человека осталась бы неизменной. Это похоже на ситуацию с последовательностью букв, которую я только что напечатал и теперь вижу на дисплее моего текстового редактора. Если я уберу их с экрана, то они, тем не менее, сохранятся записанными в виде определенных крошечных изменений электрического заряда, в конфигурации, геометрически никак не соотносящейся с буквами, которые я минуту назад напечатал. И все же в любой момент я могу вернуть их на экран — и вот они, пожалуйста, точь-в-точь такие же, словно и не было никаких преобразований. Если я захочу сохранить написанное, то я могу перевести информацию о последовательности букв в некоторую конфигурацию намагниченных доменов на диске, который я затем выну и выключу машину, аннулируя тем самым все (соответствующие) крошечные изменения заряда в ячейках ее памяти. Тогда завтра я смогу снова вставить диск, восстановить эти смещения и отобразить последовательность букв на экране так, как будто ничего и не случилось. Приверженцам теории сильного ИИ «ясно», что аналогичным образом можно обращаться и с личностью человека. Как и в случае с буквами у меня на экране, скажут они, человеческая индивидуальность ничего не потеряла бы — собственно, с ней вообще ничего бы не произошло, — если ее физическую форму перевести во что-нибудь совершенно иное, скажем, в поля намагниченности железного бруска. Они, кажется, даже готовы поспорить, что сознательное восприятие человека сохранилось бы и в то время, пока «информация» о нем пребывает в другой форме. При таком подходе «человеческое сознание» должно рассматриваться, по сути, как набор программ — «софта», — а его конкретное воплощение в виде материального человеческого существа — как действия этих программ, осуществляемые «железной начинкой» его тела и мозга.

Основанием для подобных заявлений служит, вероятно, убежденность в том, что какую бы материальную форму не принимало «железо» — пусть это будет, например, какое-нибудь электронное устройство, — ему можно будет всегда «задать» вопрос-программу (в духе теста Тьюринга), и ответ на него, в предположении о способности «железа» адекватно вычислять ответы на эти вопросы, будет неотличим от ответа человека, данного им в нормальном психическом состоянии. («Как вы чувствуете себя сегодня утром?» — «О, вполне сносно, хотя мне немного докучает легкая головная боль». — «Значит, вы не чувствуете… э-э… ну, чего-нибудь необычного, связанного с вашей личностью… ничего такого?» — «Нет. А почему вы спрашиваете об этом? Довольно странный, знаете ли, вопрос…» — «То есть вы чувствуете себя тем же самым человеком, что и вчера?» — «Ну конечно!»)

Идея, которую часто обсуждают в связи с этим, носит в фантастической литературе название телепортационной машины[37] . Предполагается использовать ее для транспортировки, допустим, с одной планеты на другую; но будет ли она работать именно таким образом — это как раз и является предметом обсуждения. Вместо того, чтобы перемещаться «обычным» путем — на космическом корабле, — гипотетический путешественник подвергается сканированию с макушки до пят, при котором со всей возможной аккуратностью фиксируется положение и характеристики каждого атома в его теле. Затем вся эта информация передается со скоростью света при помощи любого подходящего электромагнитного сигнала на ту планету, где он хотел бы оказаться. Там эта информация собирается воедино и используется в качестве инструкций для создания точной копии путешественника, со всеми его воспоминаниями, устремлениями, надеждами и самыми глубокими чувствами. По крайней мере, так это должно выглядеть на практике: все детали состояния мозга подробно записываются, затем передаются, и по этим данным происходит реконструирование. Если предположить, что все произошло так, как надо, то оригинал можно «безболезненно» уничтожить. В таком случае возникает вопрос: является ли такой механизм настоящим путешествием с одного места на другое — или же это просто создание дубликата, сопровождающееся убийством оригинала? Будете ли вы готовы воспользоваться таким способом «путешествия» при условии, что он подтвердит свою стопроцентную надежность? Если телепортация не является путешествием, то в чем же заключается принципиальная разница между ней и простым переходом из одной комнаты в другую? А в последнем случае — разве не определяют атомы в один момент времени информацию об их положении в последующие моменты? В конце концов, мы видели, что сохранять «индивидуальность» какого бы то ни было атома — нецелесообразно. Вопрос об индивидуальных характеристиках атома вообще не имеет смысла. Разве произвольная движущаяся структура из атомов не представляет собой своего рода волну информации, распространяющуюся между точками пространства? Тогда есть ли существенная разница между распространением волн, несущих информацию о переходящем из комнаты в комнату человеке, — и тех, что посылаются устройством телепортации?

Допустим, что телепортация действительно «работает» в том смысле, что «сознание» путешественника на самом деле просыпается в его двойнике, находящемся на далекой планете. Что тогда произойдет в том случае, если мы, в нарушение правил игры, не уничтожим оригинал путешественника? Будет ли его «сознание» одновременно в двух разных местах? (Попытайтесь представить свою реакцию на следующее заявление: «Ах, дорогой, похоже, суспензия, которую мы дали тебе перед посадкой в Телепортатор, испортилась раньше срока? Да, вышло не очень удачно, хотя это не так страшно. В любом случае, тебе, наверное, будет приятно услышать, что другой ты — ну-у, то есть, конечно, настоящий ты — прибыл на Венеру в целости и сохранности, поэтому мы можем… э-э… избавиться от тебя здесь — нет, я имею виду… ну, от ненужной больше копии. Разумеется, это пройдет совершенно безболезненно».) Возникает парадоксальная ситуация. Существуют ли в физике законы, делающие телепортацию принципиально невозможной? С другой стороны, возможно, там нет никаких абсолютных запретов на такую «передачу» человека и его сознания, но сам принцип «копирования» предполагает неизбежное уничтожение оригинала? Может быть, сохранение двух дееспособных копий запрещено в принципе? Хотя эти рассуждения носят отстраненный характер, я все же верю, что из них можно извлечь кое-какие полезные сведения о физической природе сознания и индивидуальности. Я вижу в них явное указание на ту существенную роль, которую играет квантовая механика в понимании явлений умственной деятельности. Но я слишком забегаю вперед. К этой теме необходимо будет вернуться после того, как мы изучим структуру квантовой теории в главе 6.

Давайте посмотрим, какое отношение имеет теория сильного ИИ к вопросу о телепортации. Мы предположим, что где-то между двумя планетами располагается ретрансляционная станция, на которой полученная информация некоторое время хранится перед тем, как быть отправленной к месту своего назначения. Для удобства эта информация записывается не в человеческой форме, а в каком-нибудь электронном или магнитном устройстве. Будет ли человеческое «сознание» присутствовать в этом устройстве? Приверженцы сильного ИИ постарались бы убедить вас в том, что это будет именно так. Ведь в конечном счете, сказали бы они вам, на любой вопрос, который мы решили бы задать путешественнику, могло бы, в принципе, ответить и это устройство — если «просто» сымитировать соответствующую функцию его мозга. Устройство располагало бы всей необходимой информацией, и дело стало бы только за вычислениями. А если устройство отвечает на вопросы в точности также, как если бы это был путешественник, то (с точки зрения теста Тьюринга!) оно им и является . В качестве основы для такого вывода здесь опять выступает известное утверждение сторонников сильного ИИ : для явлений, связанных с умственной деятельностью, «железо» не имеет никакого значения. Это утверждение кажется мне неправомочным. Оно, в свою очередь, основывается на представлении о мозге (или разуме) как о цифровом компьютере. И подразумевает, что нет каких-то особых физических процессов, приводящихся в действие, когда человек думает, которые могли бы требовать для своей реализации ту конкретную физическую (биологическую, химическую) структуру, которой обладает мозг.

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

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

Глава 2

Алгоритмы и машины Тьюринга

Основы алгоритмов

Как точно определить понятие алгоритма, или машины Тьюринга, или универсальной машины Тьюринга? Почему эти понятия играют одну из главных ролей в современном представлении о «мыслящем устройстве»? Есть ли какие-нибудь абсолютные ограничения на принципиальные возможности использования алгоритмов? Для того чтобы ответить на эти вопросы, нам придется разобраться в деталях, что представляют собой алгоритм и машины Тьюринга.

В дальнейших рассуждениях я буду иногда прибегать к математическим выражениям. Вероятно, некоторых читателей эти выкладки напугают и даже заставят отложить книгу в сторону. Если вы как раз такой читатель, то я прошу вашего снисхождения и рекомендую вам последовать совету, данному мной в Обращении к читателю вначале книги! Доказательства, которые здесь встретятся, не потребуют владения математическим аппаратом, выходящим за пределы школьного курса, но чтобы в них детально разобраться, все же понадобятся интеллектуальные усилия. На самом деле, большинство рассуждений изложено весьма подробно, и если внимательно им следовать, можно добиться глубокого понимания. Однако, даже беглый просмотр доказательств позволяет ухватить основную идею. С другой стороны, если вы являетесь экспертом в этой области, то я опять вынужден принести свои извинения. Но я осмелюсь предположить, что даже в этом случае вам будет небесполезно ознакомиться с моими рассуждениями, в которых почти наверняка найдется что-то интересное и для вас.

Слово «алгоритм» происходит от имени персидского математика IX века Абу Джафара Мухаммеда ибн Мусы аль-Хорезми, написавшего около 825 года н. э. руководство по математике «Kitab al-jabr wa’l-muqa-bala» , которое оказало значительное влияние на математическую мысль того времени. Современное написание «алгоритм», пришедшее на смену более раннему и точному «алгоризм», своим происхождением обязано, скорее всего, ассоциации со словом «арифметика»[38]. (Примечательно, что и слово «алгебра» происходит от арабского al-jabr , фигурирующего в названии вышеупомянутой книги.)

Примеры алгоритмов были, однако, известны задолго до появления книги аль-Хорезми. Один из наиболее известных — алгоритм Евклида — процедура отыскания наибольшего общего делителя двух чисел, восходит к античности (примерно 300 лет до н. э.). Давайте посмотрим, как он работает. Возьмем для определенности два числа, скажем, 1365 и 3654 . Наибольшим общим делителем двух чисел называется самое большое натуральное число, на которое делится каждое из этих чисел без остатка. Алгоритм Евклида состоит в следующем. Мы берем одно из этих чисел, делим его на другое и вычисляем остаток: так как 1365 входит дважды в 3654 , в остатке получается 3654 ―

2 х 1365 = 924.

Далее мы заменяем наши два исходные числа делителем (1365 ) и полученным остатком (924 ), соответственно, производим с этой парой ту же самую операцию и получаем новый остаток:

1365 — 924 = 441.

Для новой пары чисел — а именно, 924 и 441 , — получаем остаток 42 . Эту процедуру надо повторять до тех пор, пока очередная пара чисел не поделится нацело. Выпишем эту последовательность:

3654:1365

дает в остатке 924

1365:924

дает в остатке 441

924:421

дает в остатке 42

441:42

дает в остатке 21

42:21

дает в остатке 0

Последнее число, на которое мы делим, а именно 21, и есть искомый наибольший общий делитель.

Алгоритм Евклида является систематической процедурой , которая позволяет найти этот делитель. Мы только что применили эту процедуру к двум конкретным числам, но она работает и в самом общем случае с произвольными числами. Для очень больших чисел эта процедура может занять много времени, и будет выполняться тем дольше, чем больше сами числа. Но в каждом конкретном случае выполнение процедуры в конце концов заканчивается, приводя за конечное число шагов к вполне определенному ответу. На каждом этапе мы точно представляем себе действие, которое должно быть выполнено, и точно знаем, когда получен окончательный результат. Более того, всю процедуру можно описать конечным числом терминов, несмотря на то, что она может применяться к любым, сколь угодно большим натуральным числам. («Натуральными числами» называются неотрицательные[39] целые числа 0,1,2,3,4,5,6,7,8,9,10,11….) На самом деле нетрудно изобразить (конечную) блок-схему, описывающую логическую последовательность операций алгоритма Евклида (рис. 2.1).

Рис 2.1

Нужно заметить, что на схеме эта процедура не до конца разбита на простейшие составляющие, поскольку мы неявным образом предположили, что нам уже «известно», как выполнять необходимую базовую операцию получения остатка от деления двух произвольных натуральных чисел А и В . Эта операция, в свою очередь, также алгоритмична и выполняется при помощи хорошо знакомой нам со школы процедуры деления. Эта процедура, на самом деле, сложнее, чем все остальные части алгоритма Евклида, но и она может быть представлена в виде блок-схемы. Основное затруднение здесь возникает из-за использования привычной «десятичной» записи натуральных чисел, что вынуждает нас выписывать все таблицы умножения, учитывать перенос и т. п. Если бы для представления некоторого числа n мы использовали последовательность из n каких-нибудь одинаковых знаков, например, пяти звездочек (*****) для обозначения пятерки, то определение остатка свелось бы к совершенно элементарной алгоритмической операции. Для того чтобы получить остаток от деления А на В , достаточно просто убирать из записи числа А последовательность знаков, представляющих В , до тех пор, пока на некотором этапе оставшееся число знаков в записи А не станет недостаточным для выполнения следующего шага. Эта последовательность знаков и даст требуемый ответ. Например, желая получить остаток от деления 17 на 5, мы просто будем последовательно удалять ***** из *****************, как это показано ниже:

*****************

************

*******

* *,

и в результате получим, очевидно, 2, так как следующее удаление уже станет невозможно. Блок-схема изложенного выше процесса нахождения остатка от деления путем последовательных вычитаний приведена на рис. 2.2.

Рис 2.2

Чтобы придать блок-схеме алгоритма Евклида завершенный вид, мы должны подставить схему отыскания остатка в соответствующий блок справа в центре предыдущей схемы. Такая подстановка одного алгоритма в другой — распространенная в компьютерном программировании процедура. Алгоритм вычисления остатка, изображенный на рис. 2.2, служит примером подпрограммы , иначе говоря, это алгоритм (как правило, уже известный), вызываемый и используемый по мере надобности в ходе выполнения основного алгоритма.

Безусловно, обозначение числа n просто набором из n звездочек чрезвычайно неэффективно, когда речь заходит о больших числах. Именно поэтому обычно используют более компактную запись, например, стандартную (десятичную) систему. Однако оставим в стороне эффективность операций и обозначений и уделим все внимание вопросу о том, какие операции в принципе могут выполняться алгоритмически. Действие, которое поддается алгоритмизации в одной записи, сохранит это свойство и в любой другой. Эти два случая различаются только техническими нюансами и сложностью выполнения алгоритма.

Алгоритм Евклида — это лишь одна из многих, часто классических, алгоритмических процедур, встречающихся в математике повсеместно. Но, вероятно, не лишним будет отметить, что, несмотря на значительный исторический возраст отдельных алгоритмов, точная формулировка универсального определения алгоритма появилась только в двадцатом веке. В 1930-х годах было предложено несколько альтернативных формулировок этого понятия, из которых наиболее емкая и убедительная — и, к тому же, наиболее значимая в историческом плане — опирается на понятие машины Тьюринга. Поэтому нам будет полезно рассмотреть некоторые свойства этих «машин».

Прежде всего следует помнить, что «машина» Тьюринга принадлежит области «абстрактной математики» и ни в коем случае не является физическим объектом. Это понятие было введено в 1935–1936 годах английским математиком и кибернетиком Аланом Тьюрингом, внесшим огромный новаторский вклад в развитие компьютерной науки (Тьюринг [1937]). Тьюринг рассматривал задачу весьма общего характера (известную как проблема алгоритмической разрешимости), которая была поставлена великим немецким математиком Давидом Гильбертом частично в 1900 году на Парижском Конгрессе математиков (так называемая «десятая проблема Гильберта»), и более полно — на международном конгрессе 1928 года в Болонье. Проблема, поставленная Гильбертом, состояла ни больше, ни меньше как в отыскании универсальной алгоритмической процедуры для решения математических задач или, вернее, ответа на вопрос о принципиальной возможности такой процедуры. Кроме того, Гильберт сформулировал программу, целью которой было построение математики на несокрушимом фундаменте из аксиом и правил вывода, установленных раз и навсегда. Но к тому моменту, когда Тьюринг написал свою великую работу, сама идея этой программы уже была опровергнута поразительной теоремой, доказанной в 1931 году блестящим австрийским логиком Куртом Геделем. Мы рассмотрим теорему Геделя и ее значение в четвертой главе. Проблема Гильберта, которую исследовал Тьюринг (Entscheidungsproblem) , не зависит от какого-либо конкретного построения математики в терминах аксиоматической системы. Вопрос формулировался так: существует ли некая универсальная механическая процедура, позволяющая, в принципе, решить все математические задачи (из некоторого вполне определенного класса) одну за другой?

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

Хотя такой взгляд на процесс мышления оказался весьма полезным при разработке Тьюрингом его в высшей степени важной теории, нам совершенно необязательно его придерживаться. Действительно, дав точное определение механической процедуры, Тьюринг тем самым показал, что существуют совершенно четко определенные математические операции, которые никак не могут называться механическими в общепринятом смысле слова. Можно, наверное, усмотреть некую иронию в том, что эта сторона работы Тьюринга позволяет нам теперь косвенным образом выявить его собственную точку зрения на природу мышления. Однако, нас это пока занимать не будет. Прежде всего нам необходимо выяснить, в чем же, собственно, заключается теория Тьюринга.

Концепция Тьюринга

Попробуем представить себе устройство, предназначенное для выполнения некоторой (конечноопределенной) вычислительной процедуры. Каким могло бы быть такое устройство в общем случае? Мы должны быть готовы к некоторой идеализации и не должны обращать внимания на практические аспекты — мы на самом деле рассматриваем математическую идеализацию «машины». Нам нужно устройство, способное принимать дискретное множество различных возможных состояний, число которых конечно (хотя и может быть очень большим). Мы назовем их внутренними состояниями устройства. Однако мы не хотим, чтобы объем выполняемых на этом устройстве вычислений был принципиально ограничен. Вспомним описанный выше алгоритм Евклида. В принципе, не существует предельной величины числа, после которой алгоритм перестает работать. Этот алгоритм, или некая общая вычислительная процедура , будет тем же самым независимо от того, сколь велики числа, к которым он применяется. Естественно, для очень больших чисел выполнение процедуры может занять много времени и может потребоваться огромное количество «черновиков» для выполнения пошаговых вычислений. Но сам по себе алгоритм останется тем же конечным набором инструкций, сколь бы большими ни были эти числа.

Значит, несмотря на конечность числа внутренних состояний, наше устройство должно быть приспособлено для работы с входными данными неограниченного объема. Более того, устройство должно иметь возможность использовать внешнюю память неограниченного объема (наши «черновики») для хранения данных, необходимых для вычислений, а также уметь выдавать окончательное решение любого размера. Поскольку наше устройство имеет только конечное число различных внутренних состояний, мы не можем ожидать, что оно будет «хранить внутри себя» все внешние данные, равно как и результаты своих промежуточных вычислений. Напротив, оно должно обращаться только к тем данным и полученным результатам, с которыми оно работает непосредственно в настоящий момент, и уметь производить над ними требуемые (опять же, в данный момент) операции. Далее, устройство записывает результаты этих операций — возможно, в отведенной для этого внешней памяти — и переходит к следующему шагу. Именно неограниченные объемы входных данных, вычислений и окончательного результата говорят о том, что мы имеем дело с идеализированным математическим объектом, который не может быть реализован на практике (рис. 2.3).

Рис. 2.3. Точная машина Тьюринга требует бесконечной ленты!

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

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

Тьюринг представлял внешние данные и объем для хранения информации в виде «ленты» с нанесенными на нее метками. Устройство по мере необходимости могло обращаться к этой ленте, «считывать» с нее информацию и перемещать ее вперед или назад в ходе выполнения операций. Помимо этого, устройство могло ставить новые метки на ленту и стирать с нее старые, что позволяло использовать одну и ту же ленту и как внешнюю память (то есть «черновик»), и как источник входных данных. На самом деле, не стоило бы проводить явное различие между этими двумя понятиями, поскольку во многих операциях промежуточные результаты вычислений могут играть роль новых исходных данных. Вспомним, что при использовании алгоритма Евклида мы раз за разом замещали исходные числа (А и В ) результатами, полученными на разных этапах вычислений. Сходным образом та же самая лента может быть использована и для вывода окончательного результата («ответа»). Лента будет двигаться через устройство туда-сюда до тех пор, пока выполняются вычисления. Когда, наконец, все вычисления закончены, устройство останавливается, и результат вычислений отображается на части ленты, лежащей по одну сторону от устройства. Для определенности будем считать, что ответ всегда записывается на части ленты, расположенной слева от устройства, а все исходные числовые данные и условия задачи — на части ленты, расположенной справа от него.

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

В представлении Тьюринга «лента» состоит из бесконечной в обоих направлениях линейной последовательности квадратов. Каждый квадрат либо пуст, либо помечен[40]. Использование помеченных и пустых квадратов означает, что мы допускаем разбиение нашего «окружения» (т. е. ленты) на части и возможность его описания множеством дискретных элементов (в противоположность непрерывному описанию). Это представляется вполне разумным, если мы хотим, чтобы наше устройство работало надежно и совершенно определенным образом. В силу используемой математической идеализации мы допускаем (потенциальную) бесконечность «окружения», однако в каждом конкретном случае входные данные, промежуточные вычисления и окончательный результат всегда должны быть конечными. Таким образом, хотя лента и имеет бесконечную длину, на ней должно быть конечное число непустых квадратов. Другими словами, и с той, и с другой стороны от устройства найдутся квадратики, после которых лента будет абсолютно пустой. Мы обозначим пустые квадраты символом «0 » , а помеченные — символом «1 » , например:

Нам нужно, чтобы устройство «считывало» информацию с ленты. Мы будем считать, что оно считывает по одному квадрату за раз и смещается после этого ровно на один квадрат влево или вправо. При этом мы не утрачиваем общности рассуждений: устройство, которое читает за один раз n квадратов или перемещается на k квадратов, легко моделируется устройством, указанным выше. Передвижение на k квадратов можно построить из к перемещений по одному квадрату, а считывание n квадратов за один прием сводится к запоминанию результатов n однократных считываний.

Что именно может делать такое устройство? Каким образом в самом общем случае могло бы функционировать устройство, названное нами «механическим»? Вспомним, что число внутренних состояний нашего устройства должно быть конечным. Все, что нам надо иметь в виду помимо этого — это то, что поведение нашего устройства полностью определяется его внутренним состоянием и входными данными. Входные данные мы упростили до двух символов — «0 » и «1 » . При заданном начальном состоянии и таких входных данных устройство должно работать совершенно определенным образом: оно переходит в новое состояние (или остается в прежнем), заменяет считанный символ 0 или 1 тем же или другим символом 1 или 0 , передвигается на один квадрат вправо или влево, и наконец, оно решает, продолжить вычисления или же закончить их и остановиться.

Чтобы явно определить операции, производимые нашим устройством, для начала пронумеруем его внутренние состояния, например: 0,1,2,3,4,5. Тогда действия нашего устройства, или машины Тьюринга, полностью определялись бы неким явным списком замен, например:

00 → 00R

01 → 131L

10 → 651R

11 → 10R

20 → 01R .STOP

21 → 661L

30 → 370R

• •

2100 → 31L

• •

2581 → 00R. STOP

2590 → 971R

2591 → 00R. STOP

Выделенная цифра слева от стрелки — это символ на ленте, который устройство в данный момент считывает. Оно заменяет этот символ выделенной цифрой в середине справа от стрелки. R означает, что устройство должно переместиться вдоль ленты на один квадрат вправо , a L соответствует такому же перемещению влево . (Если, в соответствии с исходным представлением Тьюринга, мы полагаем, что движется не устройство, а лента, то R означает перемещение ленты на один квадрат влево , a L — вправо .) Слово STOP означает, что вычисления завершены и устройство должно остановиться. Например, вторая инструкция 01 → 131L говорит о том, что если устройство находится в начальном состоянии 0 и считывает с ленты 1 , то оно должно перейти в состояние 13 , оставить на ленте тот же символ 1 и переместиться по ленте на один квадрат влево. Последняя же инструкция 2591 → 00R .STOP говорит о том, что если устройство находится в состоянии 259 и считывает с ленты 1 , то оно должно вернуться в состояние 0 , стереть с ленты 1 , т. е. записать в текущий квадрат 0 , переместиться по ленте на один квадрат вправо и прекратить вычисления.

Вместо номеров 0, 1, 2, 3, 4, 5…. для обозначения внутренних состояний мы можем — и это более соответствовало бы знаковой системе нанесения меток на ленту — прибегнуть к системе нумерации, построенной только на символах «0» и «1» . Состояние n можно было бы обозначить просто последовательностью из n единиц, но такая запись неэффективна. Вместо этого мы используем двоичную систему счисления, ставшую теперь общепринятой:

0 → 0,

1 → 1,

2 → 10,

3 → 11,

4 → 100,

5 → 101,

6 → 110,

7 → 111,

8 → 1000,

9 → 1001,

10 → 1010,

11 → 1011,

12 → 1100 и т. д.

Здесь последняя цифра справа соответствует «единицам» точно так же, как и в стандартной (десятичной) системе записи, но цифра прямо перед ней показывает число «двоек», а не «десятков». В свою очередь третья цифра справа относится не к «сотням», а к «четверкам»; четвертая — к «восьмеркам», а не к «тысячам» и т. д. При этом разрядность каждой последующей цифры (по мере продвижения влево) дается соответственной степенью двойки: 1, 2, 4 (= 2 х 2), 8 (= 2 х 2 х 2), 16 (= 2х2х2х2), 32 (= 2x2x2х2х2). (В дальнейшем нам будет иногда удобно использовать в качестве основания системы счисления числа, отличные от «2» и «10». Например, запись десятичного числа 64 по основанию «три» даст 2101 , где каждая цифра теперь — некоторая степень тройки:

64 = (2 х З³) + З² + 1; см. главу 4).

Используя двоичную запись для внутренних состояний, можно представить вышеприведенную инструкцию, описывающую машину Тьюринга, следующим образом:

Здесь я к тому же сократил R.STOP до STOP , поскольку мы вправе считать, что L.STOP никогда не происходит, так как результат последнего шага вычислений, будучи частью окончательного ответа, всегда отображается слева от устройства.

Предположим, что наше устройство находится во внутреннем состоянии, представленном бинарной последовательностью 11010010, и процессу вычисления соответствует участок ленты, изображенный на предыдущем рисунке. Пусть мы задаем команду

110100100 → 111L .

Та цифра на ленте, которая в данный момент считывается (в нашем случае цифра «0» ), показана «жирным» символом справа от последовательности нулей и единиц, обозначающих внутреннее состояние.

В частично описанном выше примере машины Тьюринга (который я выбрал более-менее произвольно) считанный «0» был бы тогда замещен на «1» , внутреннее состояние поменялось бы на «11» и устройство переместилось бы на один шаг влево:

Теперь устройство готово к считыванию следующей цифры, снова «0» . Согласно таблице, оно оставляет этот «0» нетронутым, но изменяет свое внутреннее состояние на «100101» и передвигается по ленте назад, т. е. на один шаг вправо. Теперь оно считывает «1» и находит где-то ниже в таблице инструкцию, которая определяет изменение внутреннего состояния и указывает, должна ли быть изменена считанная цифра и в каком направлении по ленте должно дальше двигаться устройство. Таким образом устройство будет действовать до тех пор, пока не достигнет команды STOP . В этой точке — после еще одного шага вправо — раздастся звонок, оповещающий оператора о том, что вычисления завершены.

Мы будем считать, что машина всегда начинает с внутреннего состояния «0» и что вся лента справа от устройства изначально пуста. Все инструкции и данные подаются в устройство с правой стороны. Как упоминалось ранее, эта информация всегда имеет форму конечной строки из нулей и единиц, за которой следует пустая лента (т. е. нули). Когда машина получает команду STOP , результаты вычислений оказываются на ленте слева от считывающего устройства.

Поскольку мы хотели бы иметь возможность вводить в устройство и числовые данные, то нам потребуется некий способ описания обычных чисел (под которыми я здесь имею в виду целые неотрицательные числа 0, 1, 2, 3, 4….) как части входной информации. Для представления числа n можно было бы просто использовать строку из n единиц (хотя при этом могут возникнуть трудности, когда речь зайдет о нуле):

1 → 1,

2 → 11,

3 → 111,

4 → 1111,

5 → 11111 и т. д.

Эта примитивная схема нумерации называется (хотя и довольно нелогично) унарной (единичной) системой. В этом случае символ 0 мог бы использоваться в качестве пробела для разделения двух разных чисел. Наличие такого способа разделения для нас существенно, так как многие алгоритмы оперируют не отдельными числами, а множествами чисел. Например, для выполнения алгоритма Евклида наше устройство должно производить определенные действия над парой чисел А и В . Соответствующая машина Тьюринга может быть легко записана в явном виде. В качестве упражнения заинтересованный читатель может проверить, что нижеследующий набор инструкций действительно описывает машину Тьюринга (которую я буду называть EUC ), выполняющую алгоритм Евклида, если в качестве исходных данных использовать два «унарных» числа, разделенных символом 0 :

00 → 00R

01 → 11L

10 → 101R

11 → 11L

100 → 10100R

101 → 110R

110 → 1000R

111 → 111R

1000 → 1000R

1001 → 1010R

1010 → 1110L

1011 → 1101L

1100 → 1100L

1101 → 11L

1110 → 1110L

1111 → 10001L

10000 → 10010L

10001 → 10001L

10010 → 100R

10011 → 11L

10100 → 00 .STOP

10101 → 10101R

Однако я бы порекомендовал такому читателю начать не с этого упражнения, а с чего-нибудь гораздо более простого, например, с машины Тьюринга UN + 1 , которая просто прибавляет единицу к числу в унарном представлении:

00 → 00R

01 → 11R

10 → 01. STOP

11 → 11R

Чтобы убедиться в том, что UN +1 на самом деле производит такую операцию, давайте мысленно применим ее, скажем, к ленте вида

…00000111100000…,

соответствующей числу четыре. Мы будем полагать, что наше устройство сначала находится где-то слева от последовательности единиц. Находясь в исходном состоянии 0 , оно считывает 0 , в соответствии с первой инструкцией сохраняет его неизмененным, после чего перемещается на шаг вправо, оставаясь во внутреннем состоянии 0 . Оно продолжает последовательно передвигаться вправо до тех пор, пока не встретит первую единицу. После этого вступает в силу вторая инструкция: устройство оставляет единицу как есть и сдвигается на шаг вправо, но уже в состоянии 1 . В соответствии с четвертой инструкцией оно сохраняет внутреннее состояние 1 , равно как и все считываемые единицы, двигаясь вправо до встречи с первым после набора единиц нулем. Тогда начинает действовать третья инструкция, согласно которой устройство заменяет этот нуль на 1 , перемещается на один шаг вправо (вспомним, что команда STOP эквивалентна R.STOP ) и останавливается. Тем самым к последовательности из четырех единиц прибавляется еще одна, превращая — как и требовалось — 4 в 5 .

В качестве несколько более трудного упражнения можно проверить, что машина UN х 2 , определяемая набором инструкций

00 → 00R

01 → 10R

10 → 101L

11 → 11R

100 → 110R

101 → 1000R

110 → 01. STOP

111 → 111R

1000 → 1011L

1001 → 1001R

1010 → 101L

1011 → 1011L

удваивает унарное число, как и должно быть, судя по ее названию.

Чтобы понять, как работает машина EUC , нужно явным образом задать пару подходящих чисел, скажем, 6 и 8 . Как и ранее, изначально машина находится во внутреннем состоянии 0 и расположена слева, а лента выглядит следующим образом:

… 0000011111101111111100000….

После того, как машина Тьюринга после большого числа шагов останавливается, мы получаем ленту с записью вида

…000011000000000000…,

при этом машина располагается справа от ненулевых цифр. Таким образом, найденный наибольший общий делитель равен 2 (как и должно быть).

Исчерпывающее объяснение, почему машина EUC (или UN х 2 ) на самом деле осуществляет действие, для которого она предназначена, включает в себя некоторые тонкости, и разобраться в нем, может быть, даже труднее, чем понять устройство самой машины — довольно обычная ситуация с компьютерными программами! (Чтобы полностью понять, почему алгоритмические процедуры делают то, что от них ожидается, необходима определенная интуиция. А не являются ли интуитивные прозрения сами алгоритмическими? Это один из вопросов, которые будут для нас важны в дальнейшем.) Яне буду пытаться дать здесь такое объяснение для приведенных примеров EUC или UN х 2 . Читатель, шаг за шагом проверив их действие, обнаружит, что я незначительно изменил обычный алгоритм Евклида, чтобы получить более компактную запись в рамках используемой схемы. И все же описание EUC остается достаточно сложным, включая в себя 22 элементарные инструкции для 11 различных внутренних состояний. В основном эти сложности носят чисто организационный характер. Можно отметить, например, что из этих 22 инструкций только 3 в действительности изменяют запись на ленте! (Даже для UN х 2 я использовал 12 инструкций, половина из которых меняют запись на ленте.)

Дата добавления: 2018-08-06; просмотров: 314; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!