Совместимость: Как контролировать искусственный интеллект

Текст
4
Отзывы
Читать фрагмент
Отметить прочитанной
Как читать книгу после покупки
Шрифт:Меньше АаБольше Аа

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

РОБОТ. Добро пожаловать домой! Хотите пиццу с ананасами?

ВЫ. Нет, пора бы знать, что я больше люблю обычную.

РОБОТ. Хорошо, обычная пицца уже готовится!

ВЫ. Нет уж, мне больше хочется пиццу с сосисками.

РОБОТ. Прошу прощения! Пожалуйста, вот пицца с сосисками!

ВЫ. Вообще-то, лучше уж с ананасами, чем с сосисками.

РОБОТ. Это мой промах, вот вам с ананасами!

ВЫ. Я ведь уже сказал, что мне больше нравится обычная пицца, а не с ананасами.

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

Рациональность на двоих

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

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


Чтобы прояснить, зачем нам нужна теория игр, рассмотрим простой пример: Алиса и Боб играют во дворе в футбол (рис. 3). Алиса готовится пробить пенальти, Боб стоит на воротах. Алиса собирается направить мяч справа или слева от Боба. Поскольку она правша, для нее проще и надежнее бить вправо от Боба. У Алисы мощный удар, и Боб знает, что должен броситься в одну либо в другую сторону – у него не будет времени подождать и узнать, куда летит мяч. Боб мог бы рассуждать так: «У Алисы больше шансов забить гол, если она пробьет справа от меня, поскольку она правша, значит, это она и выберет, и мне нужно броситься вправо». Однако Алиса не дурочка, она может представить этот ход рассуждений Боба и тогда пробьет влево. Поскольку Боб тоже не дурак и поймет, что замыслила Алиса, то бросится влево. Но Алиса умна и способна представить, что Боб думает именно так… В общем, вы поняли. Иными совами, если у Алисы есть рациональный выбор, Боб тоже может его обнаружить, предвосхитить и помешать Алисе забить гол, так что выбор, в принципе, не может быть рациональным.

Еще в 1713 г. – опять-таки в ходе анализа азартных игр – был найден выход из этого затруднительного положения[34]. Хитрость состоит в том, чтобы выбирать не какое-либо действие, а рандомизированную стратегию. Например, Алиса может выбрать стратегию «бить правее Боба с вероятностью 55 % и левее с вероятностью 45 %». Боб может выбрать «кидаться вправо с вероятностью 60 % и влево с вероятностью 40 %». Каждый мысленно бросает монету с соответствующей тенденцией перед каждым действием, чтобы не отклониться от своих намерений. Действуя непредсказуемо, Алиса и Боб избегают ограничений, описанных в предыдущем абзаце. Даже если Боб выяснит, в чем состоит рандомизированная стратегия Алисы, он бессилен справиться с ней, если у него нет «хрустального шара».

Следующий вопрос: какими должны быть вероятности? Рационален ли выбор Алисы, 55 % на 45 %? Конкретные значения зависят от того, насколько выше точность Алисы при ударе направо от Боба, насколько успешно Боб берет мяч, когда кидается вправо, и т. д. (Полный анализ см. в сносках[35].) Общий критерий, впрочем, очень прост:

1. Стратегия Алисы – лучшая, которую она может выбрать при условии, что Боб неподвижен.

2. Стратегия Боба – лучшая, которую он может выбрать при условии, что Алиса неподвижна.

Если выполняются оба условия, мы говорим, что стратегии находятся в равновесии. Такого рода равновесие называется равновесием Нэша в честь Джона Нэша, который в 1950 г. в возрасте 22 лет доказал, что оно существует для любого числа агентов с любыми рациональными предпочтениями, независимо от правил игры. После нескольких десятилетий борьбы с шизофренией Нэш выздоровел и в 1994 г. получил за эту работу Нобелевскую премию за достижения в экономических науках.

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

Что еще хуже, бывают ситуации, когда равновесие Нэша может приводить к крайне нежелательным результатам. Одним из таких случаев является знаменитая «дилемма заключенного», название которой дал в 1950 г. научный руководитель Нэша Альберт Таккер[36]. Игра представляет собой абстрактную модель печально распространенных в реальном мире ситуаций, когда взаимодействие было бы лучше во всех смыслах, но люди тем не менее выбирают взаимное уничтожение.

Вот как работает «дилемма заключенного». Алиса и Боб подозреваются в преступлении и оказываются в одиночном заключении. У каждого есть выбор: признать вину и заложить подельника или отказаться давать показания[37]. Если оба откажутся, то будут обвинены в менее серьезном преступлении и отсидят два года; если оба сознаются, то получат более серьезное обвинение и сядут на 10 лет; если один сознается, а второй запирается, то сознавшийся выходит на свободу, а второй садится на 20 лет.

Итак, Алиса размышляет: «Если Боб решит признаться, то и мне следует признаваться (10 лет лучше, чем 20); если он планирует запираться, то мне лучше заговорить (выйти на свободу лучше, чем провести два года в тюрьме); так или иначе, нужно признаваться». Боб мыслит так же. В результате оба дают признательные показания и сидят 10 лет, тогда как, совместно отказавшись признавать вину, они могли бы отсидеть только два года. Проблема в том, что совместный отказ не является равновесием Нэша, потому что у каждого есть стимул предать другого и освободиться путем признания.

 

Заметьте, что Алиса могла бы рассуждать следующим образом: «Как бы я ни мыслила, Боб тоже будет размышлять. В конце концов мы выберем одно и то же. Поскольку совместный отказ лучше совместного признания, нам нужно молчать». Эта разновидность рассуждения признает, что, будучи рациональными агентами, Алиса и Боб сделают согласующийся выбор, а не два независимых. Это лишь один из многих подходов, опробованных в теории игр в попытке получить менее удручающие решения «дилеммы заключенного»[38].

Другой знаменитый пример нежелательного равновесия – трагедия общих ресурсов, впервые проанализированная в 1833 г. английским экономистом Уильямом Ллойдом[39], хотя дал ей название и привлек к ней внимание всего мира эколог Гаррет Хардин в 1968 г.[40] Проблема возникает, если несколько человек могут использовать ограниченный и медленно восполняемый ресурс – например, общее пастбище или рыбный пруд. В отсутствие любых социальных или юридических ограничений единственное равновесие Нэша для эгоистичных (неальтруистичных) агентов заключается в том, чтобы каждый потреблял как можно больше, что вело бы к быстрому исчерпанию ресурса. Идеальное решение, при котором все пользуются ресурсом так, чтобы общее потребление было устойчивым, не является равновесием, поскольку у каждого индивида есть стимул хитрить и брать больше справедливой доли – перекладывая издержки на других. На практике, конечно, люди предпринимают меры во избежание этой ситуации, создавая такие механизмы, как квоты и наказания или схемы ценообразования. Они могут это сделать, потому что не ограничены в решении о том, сколько потреблять; кроме того, они имеют возможность принять решение осуществлять коммуникацию. Расширяя проблему принятия решения подобным образом, мы находим выходы, лучшие для каждого.

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

Компьютеры

Рациональное определение интеллектуальности – первый компонент в создании интеллектуальных машин. Вторым компонентом является машина, в которой это определение может быть реализовано. По причинам, которые скоро станут очевидными, эта машина – компьютер. Это могло бы быть нечто другое, например мы могли бы попытаться сделать интеллектуальные машины на основе сложных химических реакций или путем захвата биологических клеток[41], но устройства, созданные для вычислений, начиная с самых первых механических калькуляторов всегда казались своим изобретателям естественным вместилищем разума.

Мы сегодня настолько привыкли к компьютерам, что едва замечаем их невероятные возможности. Если у вас есть десктоп, ноутбук или смартфон, посмотрите на него: маленькая коробочка с возможностью набора символов. Одним лишь набором вы можете создавать программы, превращающие коробочку в нечто другое, например, способное волшебным образом синтезировать движущиеся изображения океанских кораблей, сталкивающихся с айсбергами, или других планет, населенных великанами. Набираете еще что-то, и коробочка переводит английский текст на китайский язык; еще что-то – она слушает и говорит, еще – побеждает чемпиона мира по шахматам.

Способность осуществлять любой процесс, который приходит вам в голову, называется универсальностью. Эту концепцию ввел Алан Тьюринг в 1936 г.[42] Универсальность означает, что нам не нужны отдельные машины для вычислений, машинного перевода, шахмат, распознавания речи или анимации: все это делает одна машина. Ваш ноутбук, в сущности, подобен огромным серверам крупнейших IT-компаний – даже тех, которые оборудованы причудливыми специализированными тензорными процессорами для машинного обучения. Он также по сути идентичен всем компьютерным устройствам, которые еще будут изобретены. Ноутбук может выполнять те же самые задачи при условии, что ему хватает памяти; это лишь занимает намного больше времени.

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

В истории математики новые типы объектов возникают довольно редко. Математика началась с чисел на заре письменной истории. Затем, около 2000 г. до н. э., древние египтяне и вавилоняне стали работать с геометрическими объектами (точками, линиями, углами, областями и т. д.). Китайские математики в течение I тыс. до н. э. ввели матрицы, тогда как группы математических объектов появились лишь в XIX в. Новые объекты Тьюринга – машины и программы – возможно, самые мощные математические объекты в истории. Ирония заключается в том, что сфера математики по большей части не сумела этого признать и с 1940-х гг. и до настоящего времени компьютеры и вычисления остаются в большинстве крупнейших университетов вотчиной инженерных факультетов.

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

Центральным для компьютерной науки является понятие алгоритма – точно определенного метода вычисления чего-либо. Сейчас алгоритмы являются привычным элементом повседневной жизни. Алгоритм вычисления квадратного корня в карманном калькуляторе получает на входе число и выдает на выходе квадратный корень этого числа; алгоритм игры в шахматы принимает позицию на доске и выдает ход; алгоритм поиска маршрута получает стартовое местоположение, целевую точку и карту улиц и выдает более быстрый путь из отправной точки к цели. Алгоритмы можно описывать на английском языке или в виде математической записи, но, чтобы они были выполнены, их нужно закодировать в виде программ на языке программирования. Сложные алгоритмы можно построить, используя простые в качестве кирпичей, так называемые подпрограммы, – например, машина с автопилотом может использовать алгоритм поиска маршрута как подпрограмму, благодаря чему будет знать, куда ехать. Так, слой за слоем, строятся бесконечно сложные программные системы.

Аппаратная часть компьютера также важна, поскольку более быстрые компьютеры с большей памятью позволяют быстрее выполнять алгоритм и включать больше информации. Прогресс в этой сфере хорошо известен, но по-прежнему не укладывается в голове. Первый коммерческий программируемый электронный компьютер, Ferranti Mark I, мог выполнять около 1000 (103) команд в секунду и имел примерно 1000 байт основной памяти. Самый быстрый компьютер начала 2019 г., Summit, Национальной лаборатории Ок-Ридж в Теннесси выполняет около 1018 команд в секунду (в 1000 трлн раз быстрее) и имеет 2,5 × 1017 байт памяти (в 250 трлн раз больше). Этот прогресс стал результатом совершенствования электронных устройств и развития стоящей за ними физики, что позволило добиться колоссальной степени миниатюризации.

Хотя сравнение компьютера и головного мозга, в общем, лишено смысла, замечу, что показатели Summit слегка превосходят емкость человеческого мозга, который, как было сказано, имеет порядка 1015 синапсов и «цикл» примерно в 0,01 секунды с теоретическим максимумом около 1017 «операций» в секунду. Самым существенным различием является потребление энергии: Summit использует примерно в миллион раз больше энергии.

Предполагается, что закон Мура, эмпирическое наблюдение, что количество электронных компонентов чипа удваивается каждые два года, продолжит выполняться примерно до 2025 г., хотя и немного медленнее. Сколько-то лет скорости ограничены большим количеством тепла, выделяемого при быстрых переключениях кремниевых транзисторов; более того, невозможно значительно уменьшить размеры цепей, поскольку провода и соединения (на 2019 г.) уже не превышают длины в 25 атомов и толщины от пяти до десяти атомов. После 2025 г. нам придется использовать более экзотические физические явления, в том числе устройства отрицательной емкости[43], одноатомные транзисторы, графеновые нанотрубки и фотонику, чтобы поддержать действие закона Мура (или того, что придет ему на смену).

 

Вместо того чтобы просто ускорять компьютеры общего назначения, есть другая возможность – строить специализированные устройства, ориентированные на выполнение лишь одного класса вычислений. Например, тензорные процессоры (TPU) Google разработаны для расчетов, необходимых для определенных алгоритмов машинного обучения. Один TPU-модуль (версии 2018 г.) выполняет порядка 1017 вычислений в секунду – почти столько же, сколько машина Summit, – но использует примерно в 100 раз меньше энергии и имеет в 100 раз меньший размер. Даже если технология чипов, на которой это основано, останется в общем неизменной, машины этого типа можно попросту делать все больше и больше, чтобы обеспечить ИИ-системы огромной вычислительной мощностью.

Квантовые вычисления отличаются принципиально. Они используют необычные свойства волновых функций квантовой механики для получения потрясающего результата: в два раза увеличив количество квантового оборудования, вы можете более чем в два раза увеличить объем вычислений! Очень приблизительно это можно описать так[44]. Предположим, у вас есть крохотное физическое устройство, хранящее квантовый бит, или кубит. Кубит имеет два возможных состояния, 0 и 1. Если в классической физике кубитное устройство должно находиться в одном из двух состояний, в квантовой физике волновая функция, несущая информацию о кубите, сообщает, что он одновременно находится в обоих состояниях. Если у вас есть два кубита, то имеются четыре возможных совместных состояния: 00, 01, 10 и 11. Если волновая функция когерентно запутана между двумя кубитами, что означает, что никакие другие физические процессы не искажают картину, то два кубита находятся во всех четырех состояниях одновременно. Более того, если два кубита включены в квантовую цепь, выполняющую какое-то вычисление, то это вычисление выполняется всеми четырьмя состояниями одновременно. При наличии трех кубитов вы получаете восемь состояний, обрабатываемых одновременно, и т. д. В силу определенных физических ограничений объем выполняемой работы меньше, чем геометрическая прогрессия количества кубитов[45], но мы знаем, что существуют важные задачи, в решении которых квантовые вычисления, по всей видимости, более эффективны, чем любой классический компьютер.

К 2019 г. созданы экспериментальные прототипы маленького квантового процессора, оперирующего несколькими десятками кубитов, но пока нет интересных вычислительных задач, в которых квантовый процессор оказывается быстрее классического компьютера. Главной проблемой является декогерентность – такие процессы, как тепловой шум, разрушающие когерентность многокубитной волновой функции. Специалисты по квантовым вычислениям надеются решить проблему декогерентности путем создания цепи исправления ошибок, чтобы любая ошибка, возникающая в ходе вычислений, быстро обнаруживалась и исправлялась с использованием своего рода процесса голосования. К сожалению, системы исправления ошибок требуют намного больше кубитов для выполнения той же работы; если квантовая машина с несколькими сотнями идеальных кубитов была бы очень мощной по сравнению с существующими классическими компьютерами, нам, вероятно, потребуется несколько миллионов кубитов, исправляющих ошибки, чтобы практически осуществить эти вычисления. Переход от нескольких десятков к нескольким миллионам кубитов займет несколько лет. Если нам в конце концов удастся решить такую задачу, это полностью изменит наши возможности в использовании вычислений по методу «грубой силы»[46]. Вместо того чтобы ждать настоящих концептуальных прорывов в области ИИ, мы, возможно, сумеем использовать мощность квантовых вычислений, чтобы обойти ряд барьеров, с которыми сталкиваются нынешние «неинтеллектуальные» алгоритмы.

Ограничения вычислений

Даже в 1950-х гг. компьютер описывался в популярной печати как «супермозг», который мыслит «быстрее Эйнштейна». Можем ли мы теперь наконец сказать, что компьютеры обладают огромными возможностями человеческого мозга? Нет. Обращать внимание исключительно на вычислительную мощность – значит очень сильно заблуждаться. Одна лишь скорость не подарит нам ИИ. Выполнение неверного алгоритма на более быстром компьютере не делает алгоритм лучше; это всего лишь означает, что вы быстрее получаете неправильный ответ. (Причем чем больше данных, тем больше возможностей для неправильных ответов!) Главное следствие ускорения машин – это сокращение времени эксперимента, что позволяет исследованиям быстрее идти вперед. Создание ИИ задерживает не аппаратная, а программная часть. Мы еще не знаем, как делать машину по-настоящему интеллектуальной – даже если бы она была размером со Вселенную.

Предположим, однако, что нам удалось создать правильное программное обеспечение для ИИ. Налагает ли физика какие-либо ограничения на возможную мощность компьютера? Помешают ли нам эти ограничения получить достаточную вычислительную мощность, чтобы создать настоящий ИИ? Как представляется, ответы на эти вопросы: да, пределы существуют, и нет, отсутствует даже тень вероятности, что эти пределы не позволят нам создать настоящий ИИ. Физик МТИ Сет Ллойд оценил ограничения компьютера размером с ноутбук, исходя из квантовой теории и энтропии[47]. Результаты заставили бы даже Карла Сагана удивленно поднять брови: 1051 операций в секунду и 1030 байт памяти, или приблизительно в миллиард триллионов триллионов раз выше скорость и в 4 трлн раз больше память, чем у Summit – компьютера, который, как было указано, превосходит мощностью человеческий мозг. Таким образом, заявив, что ум человека способен определить верхнюю границу физически достижимой вычислительной мощности в нашей Вселенной[48], нужно, по крайней мере, пояснить эту мысль.

Помимо ограничений, налагаемых физическими законами, существуют пределы возможностей компьютеров, о которых можно узнать из работ специалистов по компьютерам. Сам Тьюринг доказал, что некоторые задачи не решаемы никаким компьютером: задача хорошо поставлена, у нее есть решение, но невозможен алгоритм, который всегда находил бы ответ. Он привел пример так называемой проблемы остановки: может ли алгоритм решить, что данная программа имеет «бесконечный цикл», который не позволит ей когда-либо закончиться?[49]

Предложенное Тьюрингом доказательство того, что никакой алгоритм не может решить проблему остановки[50], невероятно важно для основ математики, но, как представляется, никак не связано с вопросом о том, могут ли компьютеры быть интеллектуальными. Одна из причин этого утверждения заключается в том, что то же базовое ограничение, судя по всему, применимо и к мозгу человека. Предложив человеческому мозгу создать точную модель себя, моделирующего себя, моделирующего себя и т. д., вы загоняете себя в тупик. Лично меня никогда не беспокоило то, что я на это не способен.

Таким образом, сосредоточение на решаемых задачах вроде бы не налагает никаких ограничений на ИИ. Оказывается, однако, что решаемая – не значит простая. Специалисты в области компьютерных наук много размышляют о сложности задач, то есть о том, какой объем вычислений необходим, чтобы решить задачу самым эффективным методом. Вот простая задача: найдите в списке из 1000 чисел наибольшее. Если на проверку любого числа требуется одна секунда, то решение этой задачи очевидным методом – проверять каждое число по очереди, запоминая наибольшее, – потребует 1000 секунд. Возможен ли более быстрый метод? Нет, потому что, если метод не проверит какое-нибудь число из списка, это число может оказаться наибольшим и метод потерпит неудачу. Итак, время поиска самого большого элемента пропорционально длине списка. Специалист по компьютерам сказал бы, что эта задача имеет линейную сложность, что означает, что она очень проста; затем он попробовал бы найти что-нибудь более интересное.

Теоретиков-компьютерщиков восхищает факт, что многие задачи, как представляется[51], в худшем случае имеют экспоненциальную сложность. Из этого следует, что, во-первых, все алгоритмы решения этих задач, о которых нам известно, требуют экспоненциального времени – а именно, количество времени растет по экспоненте с размером входных данных; во-вторых, все теоретики в области компьютерных наук совершенно уверены, что более эффективных алгоритмов не существует.

Экспоненциальный рост трудности означает, что задачи могут быть решаемыми в теории (то есть они, безусловно, разрешимы), но иногда неразрешимыми на практике; мы называем такие задачи неразрешимыми. Примером служит задача принятия решения, можно ли раскрасить данную карту только тремя цветами так, чтобы никакие два соседних участка не были одного цвета. (Хорошо известно, что раскрашивание четырьмя цветами всегда возможно.) Если участков миллионы, может оказаться, что бывают случаи (не все, но некоторые), требующие порядка 21000 этапов вычислений для поиска ответа, на что потребуется около 10275 лет работы суперкомпьютера Summit или 10242 лет ноутбука Сета Ллойда, созданного на пределах законов физики.

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

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

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

34Первое упоминание о рандомизированной стратегии в играх: Pierre Rémond de Montmort, Essay d’analyse sur les jeux de hazard, 2nd ed. (Chez Jacques Quillau, 1713). В книге упоминается некий монсеньор де Вальдграв в качестве автора оптимального рандомизированного решения для карточной игры Ле Гер. Сведения о личности Вальдграва раскрываются в статье: David Bellhouse, “The problem of Waldegrave,” Electronic Journal for History of Probability and Statistics 3 (2007).
35Задача полностью определяется, если задать вероятность того, что Алиса забивает гол в каждом из следующих четырех случаев: если она бьет вправо от Боба, и Боб бросается вправо или влево, и если она бьет влево от Боба, и он бросается вправо или влево. В данном случае эти вероятности составляют 25, 70, 65 % и 10 % соответственно. Предположим, что стратегия Алисы – бить вправо от Боба с вероятностью p и влево с вероятностью 1 – p, тогда как Боб бросается вправо с вероятностью q и влево с вероятностью 1 – q. Выигрыш Алисы: UA = 0,25 pq + 0,70 p (1 − q) + 0,65 (1 − p)q + 0,10 (1 − p) (1 − q), Боба: UB = −UA. В равновесии ∂UA/∂p = 0 and ∂UB/∂q = 0, что дает p = 0,55 и q = 0,60.
36Исходную задачу теории игр предложили Меррил Флуд и Мелвин Дрешер в RAND Corporation. Такер увидел матрицу выигрышей, зайдя к ним в кабинет, и предложил сопроводить ее «историей».
37Специалисты теории игр обычно говорят, что Алиса и Боб смогли сотрудничать друг с другом (отказались давать показания) или предать подельника. Мне эти определения кажутся вводящими в заблуждение, поскольку «сотрудничество друг с другом» не тот выбор, который каждый агент может сделать индивидуально, а также из-за влияния общепринятого выражения «сотрудничать с полицией», когда за сотрудничество можно получить более легкий приговор и т. д.
38Интересное решение на основе доверия для дилеммы заключенного и других игр см.: Joshua Letchford, Vincent Conitzer, and Kamal Jain, “An ‘ethical’ game-theoretic solution concept for two-player perfect-information games,” in Proceedings of the 4th International Workshop on Web and Internet Economics, ed. Christos Papadimitriou and Shuzhong Zhang (Springer, 2008).
39Источник трагедии общих ресурсов: William Forster Lloyd, Two Lectures on the Checks to Population (Oxford University, 1833).
40Современное рассмотрение темы в контексте глобальной экологии: Garrett Hardin, “The tragedy of the commons,” Science 162 (1968): 1243–48.
41Весьма вероятно, что, даже если бы мы попытались создать интеллектуальные машины на основе химических реакций или биологических клеток, объединения этих элементов оказались бы реализацией машины Тьюринга нетрадиционным способом. Вопрос о том, является ли объект универсальным компьютером, никак не связан с вопросом о том, из чего он сделан.
42Эпохальная статья Тьюринга дает определение понятию, в настоящее время известному как машина Тьюринга, основополагающему в компьютерной науке. Entscheidungsproblem, или проблема принятия решения, в названии статьи есть проблема выбора следования в логике первого порядка: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 2nd ser., 42 (1936): 230–65.
43Хорошее исследование отрицательной емкости от одного из ее изобретателей: Sayeef Salahuddin, “Review of negative capacitance transistors”, in International Symposium on VLSI Technology, Systems and Application (IEEE Press, 2016).
44Намного лучшее объяснение квантовых вычислений см. в кн.: Scott Aaronson, Quantum Computing since Democritus (Cambridge University Press, 2013).
45Статья, проводящая четкое различие с точки зрения теории сложности между классическими и квантовыми вычислениями: Ethan Bernstein and Umesh Vazirani, “Quantum complexity theory,” SIAM Journal on Computing 26 (1997): 1411–73.
46Следующая статья известного физика представляет собой хороший обзор современного состояния теоретического понимания и технологии квантовых вычислений: John Preskill, “Quantum computing in the NISQ era and beyond,” arXiv:1801.00862 (2018).
47О максимальной вычислительной способности килограммового объекта: Seth Lloyd, “Ultimate physical limits to computation,” Nature 406 (2000): 1047–54.
48Пример предположения, что люди могут представлять собой вершину физически достижимой разумности, см. в статье: Kevin Kelly, “The myth of a superhuman AI,” Wired, April 25, 2017: «Мы склонны верить, что предел далеко от нас, далеко “впереди” нас, как мы “впереди” муравья… Что доказывает, что не мы являемся этим пределом?»
49Если вам интересно, можно ли решить проблему остановки простой хитростью: очевидный метод просто выполнять программу, чтобы узнать, завершится ли она, не работает, потому что необязательно имеет конец. Вы можете прождать миллион лет, но так и не узнать, застряла программа в бесконечном цикле или ей просто нужно время.
50Доказательство того, что проблема остановки неразрешима, очень изящно. Вопрос: возможна ли программа проверки циклов LoopChecker (Р, Х), которая для любой программы Р и любого входа Х верно определяет за конечный промежуток времени, остановится ли Р, примененная к Х, выдав результат, или будет выполняться вечно? Допустим, программа LoopChecker существует. Напишем программу Q, использующую LoopChecker как подпрограмму с самой Q и Х в качестве входа и выполняющую противоположное тому, что предсказывает LoopChecker (Q, Х). Тогда, если LoopChecker сообщает, что Q остановится, Q не останавливается, и наоборот. Таким образом, предположение, что LoopChecker существует, приводит к противоречию, следовательно, LoopChecker не существует.
51Я говорю «как представляется», потому что на сегодняшний день утверждение, что класс неполиномиальных задач требует сверхполиномиального времени (принятое обозначение: P ≠ NP), остается недоказанным. После почти 50 лет исследований, однако, почти все математики и специалисты в области компьютерных наук убеждены в его истинности.
Купите 3 книги одновременно и выберите четвёртую в подарок!

Чтобы воспользоваться акцией, добавьте нужные книги в корзину. Сделать это можно на странице каждой книги, либо в общем списке:

  1. Нажмите на многоточие
    рядом с книгой
  2. Выберите пункт
    «Добавить в корзину»