М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 42
Текст из файла (страница 42)
Исполнение программной строки заключается в следующем: внутреннее состояние машины переходит в д', на место символа х на ленту записывается символ х', головка смещается влево, вправо или остается на месте в зависимости от того, равно з минус единице, единице или нулю соответственно.
Единственное исключение из этого правила возникает в случае, когда головка указывает на самую левую ячейку и при этом з = — 1; в этом случае гояовка остается на месте. Теперь, когда мы знаем, что такое машина Тьюринга, посмотрим, как с ее помощью можно вычислить какую-либо простую функцию. Рассмотрим следующий пример.
В начале работы машины нв ленте записано двоичное число х (а 168 Глава 3. Введение в информатику за ним — пробелы). Кроме начального состояния д, и заключительного состояния 4ь машина имеет три внутренних состояния дм дз и дз. Программа состоит из следующих строк (номера слева приведены только для удобства ссылок и не являются составной частью программы): 1: (д„>, д~, ~>, +Ц 2: (дмО,днЬ,+1) 3: (д„1,д„Ь,+Ц 4: (~д,ь,о,ь,— Ц 6: (?з,ь,д„Ь,-1) 6: (чэ, ~>, Чз, ~>, +1) 7:. (аз Ь,дь 1 О) Какую функцию вычисляет эта программа? Вначале машина находится в состоянии д, и в крайней левой ячейке, так что выполняется строка номер 1, т. е.
(д„~>, дм Р, +1), в результате чего головка сдвигается вправо, содержимое ленты не меняется, а внутреннее состояние меняется на дм Программные строки 2, 3, 4 обеспечивают следующее поведение машины: если машина находится в состоянии д~, то головка сдвигается вправо, когда она видит О (строка 2) или 1 (строка 3), при этом содержимое ленты заменяется на пробелы, пока головка не дойдет до ячейки, в которой уже стоит пробел; в этот момент головка сдвигается на один шаг влево, а внутреннее состояние меняется на дэ (строка 4). Теперь выполнение строки 5 приводит к тому, что головка сдвигается влево, а содержимое ленты не меняется, пока под головкой находится пробел.
Так продолжается пока головка не дойдет до исходного положения; в этот момент машина читает символ >, внутреннее состояние меняется на оз, и головка сдвигается на один шаг вправо (строка 6). Строка 7 завершает программу: машина просто печатает на ленте число 1 и останавливается. Наш анализ показывает, что эта программа вычисляет постоянную функцию Дх) = 1.
Другими словами, независимо от того, какое число перед началом работы было записано на ленте, на выходе оказывается записанным число 1. Вообще машину Тьюринга можно рассматривать как устройство, вычисляющее функции из множества целых неотрицательных чисел в множество целых неотрицательных чисел; исходное состояние ленты является записью аргумента функции, а конечное — записью значения функции на этом аргументе.
Кажется, что мы всего лишь вычислили простую функцию очень сложным способом. Можно ли с помощью машины Тьюринга вычислять более сложные функции? Возможно ли, например, сконструировать машину, которая по заданным числам х и у, записанным на ленте через пробел, вычисляет (записывает на ленте) их сумму? И вообще, какой класс функций можно вычислить с помощью машины Тьюринга? Оказывается, что модель вычислений, основанная на машине Тьюринга, может быть использована для вычисления очень многих функций. Например, с ее помощью можно выполнять все основные арифметические операции, проводить поиск в тексте, представленном как последовательность битов на ленте, 3.1.
Вычислительные модели 169 и выполнять мною других интересных операций. Удивительно, что на машине Тьюринга можыо имитировать все действия, производимые современным компьютером! В самом деле, согласно тезису, выдвинутому независимо Черчем и Тьюриыгом, на машине Тьюринга можно вычислить все функции, вычислимые с помощью алгоритма. Это утверждение известно как теэис Черна-Тьюринга: Класс функций, вычислимых на и!атаине Тьюринга, в тпочностпи совпадает с классом функций, которые естественно рассматприватпь как вычислимые с помощью алгоритпма. Тезис Черча-Тьюринга утверждает эквивглентность строгого математического понятия — функции, вычислимой на машине Тьюринга и интуитивного понятия — вычислимой с помощью алгоритма функции.
Важность этого тезиса в том, что он делает возможным изучение реальных алгоритмов (поыятие алгоритма было до 1936 г. было довольно неопределеныым) строгими математическими методами. Чтобы понять, почему это важно, полезно посмотреть ыа определение непрертивной функции из математического анализа. Любой ребенок скажет, что линия, нарисованная на бумаге, непрерывна, но далеко не очевидыо, квк оформить это интуитивное понятие в строгое определение. Математики Х1Х века посвятили много времени спорам о достоинствах различных определений непрерывности, пока не было принято современное определение.
Когда даются определения фундаментальных понятий, таких как непрерывность или вычислимость, важно, чтобы выбранные определения обеспечивали максимальное соответствие между интуитивным понятием и точным математическим определением. С этой точки зрения тезис Черча-Тьюринга — это просто утверждение о том, что понятие машины Тьюринга обеспечивает хорошую основу информатики, подводя строгую базу под интуитивное понятие алгоритма. Априори не очевидно, что любая функция, которую мы интуитивно рассматриваем как вычислимую с помощью алгоритма, может быть вычислена на машине Тьюринга. Черч, Тьюринг и многие другие ученые посвятили много времени сбору аргументов в пользу тезиса Черча-Тьюринга, и за 60 лет не было найдено ни одного аргумента против этого тезиса. Тем не менее не исключено, что в будущем мы найдем в природе процесс, вычисляющий функцию, которую нельзя вычислить с помощью машины Тьюринга.
Было бы чудесно, если бы такой процесс действительыо был обнаружен, поскольку тогда мы смогли бы выполнить вычисления, которые невозможно было сделать до этого. Разумеется, при этом нам пришлось бы переработать определение вычислимости, а с ним и информатику. Упражнение 3.1 (невычислимые процессы в природе). Как можно установить, что какой-то природный процесс вычисляет функцию, невычислимую машиной Тьюринга? Упражнение 3.2 (тьюринговы номера). Покажите, что одноленточные машины Тьюрингат можно пронумеровать числами 1, 2, 3,..., однозначно определяющими соответствующую машину. Мы будем называть это число тпьюрин- т Это нвшииы, которые были описаны выше. — Прим. род. 170 Глава 3.
Введение в информатику гоеым номером соответствующей машины Тьюринга. (Указание. Каждое натуральное число может быть разложено единственным образом на простые множители в виде р~'р~"...рь', где р; — различные простые числа и ам...,аь— целые неотрицательные числа.) В последующих главах мы увцвим, что квантовые компьютеры также подчиняются тезису Черча — Тьюринга. Другими словами, квантовые компьютеры могут вычислять тот же класс функций, что и машины Тьюринга. Оказывается, что разница между квантовыми компъютерами и машинами Тьюринга состоит в эффективности вычислений: существуют функции, которые на квантовом компьютере можно вычислить гораздо эффективнее, чем на классическом вычислительном устройстве, таком. как машина Тьюринга.
Полное доказательство того, что на машине Тьюринга можно смоделировать все обычные конструкции языков программирования, выходит за рамки этой книги (см. раздел «История и дополнительная литература» в конце главы). Описывая алгоритмы, мы не будем в явном виде записывать программу для соответствующей машины Тьюринга. Обычно будем пользоваться псевдокодом гораздо более высокого уровня, полагаясь на тезис Черча-Тьюринга в том отношении, что этот псевдокод можно перевести в описание машины Тьюринга.
Мы не будем давать формального описания псевдокода. Вы можете его рассматривать как формализованную версию английского языка или как неформальную версию языка программирования наподобие С + + или Бейсика. Псевдокод позволяет удобным образом записывать алгоритмы, не вдаваясь в мелкие подробности, которые были бы нужны при описании машины Тьюринга. Пример использования псевдокода можно найти во вставке 3.2; далее в книге псевдокод будет использоваться также для описания квантовых алгоритмов. Есть много вариантов машины Тьюринга. Можно представить себе машины Тьюринга с лентами различных типов. Например, можно рассматривать ленту, бесконечную в обе стороны, или же ленту, имеющую более, чем одно измерение.
Пока невозможно физически осмысленным образом изменить описание машины Тьюринга так, чтобы при этом расширился класс функций, вычислимых на такой машине. В качестве примера рассмотрим миоголенточную машину Тьюринга. Для простоты ограничимся двухленточным случаем (обобщение на большее число лент очевидно). Подобно стандартной машине Тьюринга, двухленточная машина Тьюринга имеет конечное число внутренних состояний йм..., о„„начальное состояние д, и заключительное состояние оь. У этой машины есть две ленты, на каждой из которых записаны символы из некоторого конечного алфавита Г. Как и ранее, нам будет удобно считать, что алфавит состоит из четырех символов О, 1, 6 и ~>, где ~> обозначает край каждой из лент. Машина снабжена двумя головками, по одной для каждой ленты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
