Тьюринг. Компьютерное исчисление - Рафаэль Лаос-Бельтра

π = 4(1 - 1/3 + 1/5 - 1/7 + ... + (-1)k • 1/(2k+1))

Однако не существует алгоритма, с помощью которого компьютер записал бы все десятичные числа других существующих чисел с бесконечной последовательностью знаков после запятой. Еще один пример невычислимой задачи — определение траектории электрона, движущегося из точки А в точку В. Простой опыт, с помощью которого можно доказать, что человеческий мозг способен практически мгновенно определить невычислимость задачи, состоит в том, чтобы попробовать найти два четных числа, сумма которых была бы нечетной. Через пару секунд, после нескольких попыток вычислений в уме, мы придем к выводу, что эта задача не имеет ответа, но невозможно написать программу для компьютера, способную прийти к такому же выводу. И дело здесь не в умениях программиста или длине программного кода.

В вычислимой задаче, например написать все десятичные значения числа π, некоторые аспекты могут показаться любопытными, например то, что количество команд программы, генерирующей десятичные знаки числа π, будет короче, чем сама генерируемая последовательность:

3,141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609...

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

КАК РАБОТАЕТ КВАНТОВЫЙ КОМПЬЮТЕР

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

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

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

РИС.1

Также нужно уточнить, что двоичная система счисления (база два) оперирует двумя возможными символами, 0 или 1, а десятичная система (база десять) — десятью возможными символами (0, 1, 2,..., 9). Число в каждой системе счисления представляет собой комбинацию символов. Так как двоичная система является внутренним языком компьютеров, преобразование чисел из одной системы в другую является обычной практикой. Для перевода двоичного числа в десятичный вид необходимо представить это число как сумму произведений последовательных степеней основания двоичной системы счисления (2) на соответствующие цифры в разрядах двоичного числа справа налево. Так, если в двоичной системе перед нами число 1011, мы действуем следующим образом: первый знак 1 справа умножаем на 2° (нулевая степень любого числа равна единице), следующий знак 1 умножаем на 20 знак 0 — на 22, знак 1 — на 23. Теперь вычислим сумму полученного выражения 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20. Результат будет эквивалентным десятичным числом, в нашем случае — 11. На практике если двоичные числа состоят из четырех разрядов, результаты, полученные с помощью описанного метода, можно занести в таблицу.