Классические и квантовые вычисления - Программирование, компьютеры и кибернетика курсовая работа

Физическая реализация квантового компьютера. Вычислимые функции и разрешимые предикаты. Вероятностные алгоритмы, проверка простоты числа. Соотношение между классическим и квантовым вычислением. Базисы для квантовых схем. Универсальная квантовая схема.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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


Факультет: «КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИИ»
«Классические и квантовые вычисления»
В последние годы интерес к тому, что называется "квантовые компьютеры", необычайно возрос. Идея использования возможностей квантовой механики при организации вычислений выглядит все более привлекательной, начаты экспериментальные работы в этой области.
Однако перспективы физической реализации квантовых компьютеров пока совершенно неясны. Скорее всего, это дело нескольких десятилетий. Основные достижения в этой области носят пока чисто математический характер.
Эта книга предназначена для первоначального знакомства с математической теорией квантовых вычислений. Для удобства читателя вначале дается краткое введение в классическую теорию сложности вычислений. Затем подробно излагаются основы теории квантовых вычислений, включая описание основных известных к настоящему времени эффективных квантовых алгоритмов.
Основу книги составили материалы курса "Классическое и квантовое вычисление", прочитанного А. Шенем (классические вычисления) и А. Китаевым (квантовые вычисления) в Высшем колледже математики Независимого Московского университета в весеннем семестре 1998 г. При подготовке книги также использовались материалы курса Physics 229 - Advanced Mathematical Methods of Physics (Quantum computation), который вели Дж. Прескилл (John Preskill) и А. Китаев (при участии А. Ландала (Andrew Landahl)) в Калифорнийском технологическом институте в 1998-1999 уч. г.
Необходимые для чтения этой книги знания невелики. В сущности, достаточно знания линейной алгебры в объеме стандартного университетского курса, элементарной теории вероятностей, элементарной теории чисел и минимальных представлений о теории алгоритмов (например, иметь навыки практического программирования нетривиальных алгоритмов).
сложение по модулю 2 (а также прямая сумма линейных пространств)
пустой символ (пробел) в алфавите машины Тьюринга
сводимость предикатов по Карпу ( сводится к ) (лекция 2)
мультипликативная группа обратимых элементов
( ) -- группа характеров абелевой группы
симплектическая группа над полем размерности (лекция 14)
расширенная симплектическая группа над полем размерности (лекция 14)
группа унитарных операторов на пространстве
специальная унитарная группа на пространстве
специальная ортогональная группа на евклидовом пространстве
пространство, порожденное векторами
пространство линейных функционалов на пространстве
пространство линейных операторов на
пространство линейных отображений из в
квантовый бит (q-бит, пространство )
обратимое копирование бита (Controlled NOT) (лекция 6)
обратимая функция, соответствующая булевой функции (лекция 6)
тождественный оператор на пространстве
унитарный оператор, соответствующий перестановке (лекция 6)
оператор с квантовым управлением (лекция 7)
проектор (оператор проектирования) на подпространство
базисные операторы на пространстве (лекция 14)
преобразование матриц плотности (лекция 14)
оператор, действующий на квантовый регистр (множество q-битов) (лекция 5)
частичный след от оператора по пространству (лекция 9)
норма вектора (лекция 7) или операторная норма оператора (лекция 6)
норма для преобразований матриц плотности (лекция 14)
мощность множества или модуль числа
характеристическая функция множества
представление рационального числа в виде несократимой дроби
условная вероятность (в различных контекстах)
Все компьютеры, начиная от так и не построенной "аналитической машины" Чарльза Бэббиджа1) и кончая Cray'ем, основаны на одних и тех же принципах. С логической точки зрения компьютер состоит из битов (переменных, принимающих значения или ), а программа -- это последовательность операций, каждая из которых использует небольшое число битов. Конечно, новые компьютеры работают быстрее старых, но прогресс в этом направлении имеет предел. Трудно предположить, что размер транзистора или аналогичного элемента будет меньше см (диаметр атома водорода), а рабочая частота -- больше ~Гц (частота атомных переходов). Так что даже суперкомпьютеры будущего не смогут решать вычислительные задачи, имеющие экспоненциальную сложность. Рассмотрим, например, задачу о разложении целого числа на простые множители. Очевидный способ -- это попробовать разделить на числа от до . Если число имеет знаков в двоичной записи, то придется перебрать вариантов. Существует хитроумный алгоритм, решающий ту же задачу примерно за шагов ( ). Даже в этом случае, чтобы разложить на множители число из миллиона знаков, не хватит времени жизни Вселенной. (Возможно, есть и более эффективные алгоритмы, но от экспоненты, по-видимому, избавиться не удастся.)
Существует, однако, другой способ ускорить процесс вычисления для некоторых специальных классов задач. Дело в том, что обычные компьютеры не используют всех возможностей, предоставляемых природой. Это утверждение может показаться слишком очевидным: в природе есть множество процессов, совершенно непохожих на операции с нулями и единицами. Можно попытаться использовать эти процессы для создания аналоговой вычислительной машины. Например, интерференция света может использоваться для вычисления преобразования Фурье. Однако в большинстве случаев выигрыш в скорости не является принципиальным, т.е. слабо зависит от размера устройства. Причина заключается в том, что уравнения классической физики (например, уравнения Максвелла) эффективно решаются на обычном цифровом компьютере. Что значит эффективно? Вычисление интерференционной картины может занять в миллионы раз больше времени, чем реальный эксперимент, потому что скорость света велика, а длина волны мала. Однако с увеличением размера моделируемой физической системы количество необходимых вычислительных операций растет не слишком быстро -- степенным, или, как принято говорить в теории сложности, полиномиальным образом. (Как правило, число операций пропорционально величине , где -- объем, а -- время.) Таким образом, классическая физика слишком "проста" с вычислительной точки зрения.
Квантовая механика устроена в этом смысле гораздо интереснее. Рассмотрим, например, систему из спинов. Каждый спин обладает двумя базисными состояниями ( и ), а вся система имеет базисных состояний (каждая из переменных принимает значение или ). Согласно общим принципам квантовой механики, возможными состояниями системы являются также суперпозиции вида , где -- комплексные числа, называемые амплитудами. Знак суммы здесь нужно понимать чисто формально. Суперпозиция является новым математическим объектом -- вектором в -мерном комплексном пространстве. Квадрат модуля амплитуды, , равен вероятности обнаружить систему в базисном состоянии при измерении значений переменных . (Отметим, что такое измерение разрушает суперпозицию.) Следовательно, должно выполняться условие . Итак, общее состояние системы (т.е. суперпозиция) -- это вектор единичной длины в -мерном комплексном пространстве. Изменение состояния за определенный промежуток времени описывается унитарной матрицей размера . Если промежуток времени очень мал ( , где -- энергия взаимодействия), то эта матрица устроена достаточно просто; каждый из ее элементов можно легко вычислить, зная взаимодействие между спинами. Если же мы хотим узнать изменение состояния системы за большой промежуток времени, то придется перемножать такие матрицы. Для этого требуется экспоненциально большое число операций. В настоящее время неизвестно никакого способа упростить данное вычисление, скорее всего, моделирование квантовой механики является экспоненциально сложной вычислительной задачей. Однако то же самое утверждение можно сформулировать иначе: квантовая система эффективно "решает" сложную вычислительную задачу -- моделирует саму себя.
Можно ли использовать квантовые системы для решения других вычислительных задач? Какова должна быть математическая модель квантового компьютера, в той же степени не зависящая от физической реализации, что и модели классических вычислений2)? Эти вопросы, по-видимому, впервые были поставлены в книге Ю. И. Манина "Вычислимое и невычислимое" (1980 г.). Они обсуждались также в работах Р. Фейнмана и других авторов. В 1985 году Д. Дойч [27] предложил конкретную математическую модель -- квантовую машину Тьюринга, а в 1989 году -- эквивалентную, но более удобную модель -- квантовые схемы [28, 47].
Что такое квантовая схема? Пусть в нашем распоряжении имеется спинов, каждый из которых находится в отдельном ящичке и идеально изолирован от окружающего мира. В каждый момент времени мы можем выбрать, по нашему усмотрению, любые два спина и подействовать на них любой унитарной матрицей . Последовательность таких операций называется квантовой схемой. Каждая операция определяется парой номеров спинов и шестнадцатью комплексными числами, поэтому квантовую схему можно записать на бумаге. Это своего рода программа для квантового компьютера.
Чтобы использовать квантовую схему для вычисления функции3) , нужно уметь вводить входные данные, проделывать вычисления и считывать результат. Ввести в квантовый компьютер последовательность нулей и единиц -- значит приготовить начальное состояние . (Объем входных данных обычно меньше общего количества "ячеек памяти", т.е. спинов, . Оставшиеся ячейки заполняются нулями.) К начальному состоянию применяется квантовая схема, зависящая от решаемой задачи, но не от конкретных входных данных. В итоге возникает квантовое состояние
зависящее от . Теперь нужно считать результат. Предполагаем, что ответ должен содержаться в первых битах строки , т.е. мы ищем такие , что . Для получения ответа производится измерение значений всех спинов. Результатом измерения может быть любая последовательность нулей и единиц , вероятность получить ее равна . Таким образом, квантовый компьютер может, с некоторой вероятностью, дать любой ответ. Квантовая схема является "правильной" для данной функции , если правильный ответ получается с вероятностью, достаточно близкой к единице. Повторив все вычисление несколько раз и выбрав тот ответ, который встречается чаще, можно снизить вероятность ошибки до сколь угодно малой величины.
Мы только что сформулировали (опуская некоторые подробности) математическую модель квантового вычисления. Теперь естественно задать два вопроса.
Для каких задач квантовое вычисление дает выигрыш по сравнению с классическим?
Какую систему можно использовать для физической реализации квантового компьютера? (Это не обязательно должна быть система спинов.)
По поводу первого вопроса сейчас известно следующее. Во-первых, на квантовом компьютере можно моделировать любую квантовую систему за полиномиальное число шагов. Это позволит (при наличии квантового компьютера) предсказывать свойства молекул и кристаллов, проектировать микроскопические электронные устройства размером в несколько десятков ангстрем. (Сейчас такие устройства находятся на пределе технологических возможностей, но в будущем они, вероятно, будут применяться в обычных компьютерах.) Второй пример -- разложение на множители и аналогичные теоретико-числовые задачи, связанные с абелевыми группами. В 1994 году П. Шор (P. Shor) придумал квантовый алгоритм4), позволяющий разложить на простые множители число из знаков за шагов ( ). Этот красивый результат может иметь скорее вредное, чем полезное применение: разлагая числа на множители, можно подбирать ключи к шифрам, подделывать электронные подписи и т.д. (Впрочем, трудности на пути создания квантового компьютера столь велики, что в течение ближайших 10 лет пользователи шифров могут спать спокойно.) Третий пример -- это поиск нужной записи в неупорядоченной базе данных. Здесь выигрыш не столь значителен: для нахождения одной записи из требуется порядка операций на квантовом компьютере вместо операций на классическом. На этом список известных примеров заканчивается -- не потому что квантовые компьютеры бесполезны для других задач, а потому что теория квантовых вычислений пока не разработана. Будем надеяться, что скоро появятся новые математические идеи, которые позволят придумать новые примеры.
Физическая реализация квантового компьютера -- чрезвычайно интересная, но сложная задача. Еще несколько лет назад высказывались сомнения в ее принципиальной разрешимости. Дело в том, что любое унитарное преобразование можно реализовать лишь с некоторой точностью. Кроме того, систему спинов или аналогичную квантовую систему нельзя полностью защитить от возмущений со стороны окружающей среды. Все это должно приводить к погрешностям, которые будут накапливаться в процессе вычисления. Через шагов (где -- точность каждого унитарного преобразования) вероятность ошибки станет порядка единицы. К счастью, эту трудность можно преодолеть, используя квантовые коды, исправляющие ошибки. В 1996 году П. Шор предложил схему коррекции ошибок в процессе квантового вычисления (fault-tolerant quantum computation), которая была вскоре усовершенствована. Окончательный результат состоит в следующем. Существует некоторое пороговое значение точности , такое что при возможно сколь угодно длинное квантовое вычисление. Однако при ошибки накапливаются быстрее, чем их удается исправлять. По разным оценкам, лежит в интервале от до (точное значение зависит от характера возмущений и используемой схемы коррекции ошибок).
Итак, принципиальных препятствий для реализации квантового компьютера нет. Однако задача столь трудна, что ее можно сравнить с задачей об управляемом термоядерном синтезе. В самом деле, необходимо удовлетворить нескольким почти несовместимым требованиям.
Элементы квантового компьютера -- квантовые биты (спины или что-то подобное) -- должны быть изолированы друг от друга и от окружающей среды.
Необходимо иметь возможность избирательного воздействия на пару квантовых битов. (Возможно, потребуется несколько типов воздействия на одну и ту же пару, описываемых различными унитарными операторами.)
Каждый из унитарных операторов должен быть реализован с точностью (см. выше).
Реализуемые операторы должны быть достаточно нетривиальны. Точнее говоря, они должны образовывать полный базис, чтобы любой другой оператор в определенном смысле выражался через них.
В настоящее время существует несколько подходов к проблеме реализации квантового компьютера.
Отдельные атомы или ионы. Это первая и наиболее хорошо разработанная идея, она существует в нескольких вариантах. Для представления квантового бита можно использовать как обычные электронные уровни, так и уровни тонкой и сверхтонкой структуры. Имеется экспериментальная техника, позволяющая удерживать отдельный ион или атом в ловушке из постоянного магнитного или переменного электрического поля в течение длительного времени (порядка 1 часа). Ион можно "охладить" (т.е. погасить колебательное движение) при помощи лазерного луча. Подбирая длительность и частоту лазерных импульсов, можно приготовить произвольную суперпозицию основного и возбужденного состояний. Таким образом, управлять отдельным ионом достаточно легко. В ловушку можно также поместить два или большее число ионов на расстоянии несколько микрон друг от друга и управлять каждым из них в отдельности. Однако организовать взаимодействие между ионами достаточно трудно. Для этой цели предложено использовать коллективные колебательные моды ионов (обычные механические колебания с частотой в несколько мегагерц). Другой способ (для нейтральных атомов): поместить атомы в отдельные электромагнитные резонаторы, связанные друг с другом (пока непонятно, как это реализовать технически). Наконец, третий способ: при помощи нескольких лазерных лучей можно создать периодический потенциал ("оптическую решетку"), удерживающий невозбужденные атомы. При этом возможна ситуация, когда возбужденные атомы могут свободно двигаться. Таким образом, возбуждая на короткое время один из атомов, мы заставляем его взаимодействовать с соседями. Это направление экспериментальной физики сейчас быстро развивается и, по-видимому, имеет большие перспективы.
Ядерный магнитный резонанс. В молекуле с несколькими различными ядерными спинами произвольное унитарное преобразование можно реализовать при помощи последовательности импульсов магнитного поля. Это было проверено экспериментально при комнатной температуре. Однако для приготовления начального состояния необходима температура < K. Помимо трудностей с охлаждением, при такой температуре возрастают нежелательные взаимодействия молекул друг с другом. Кроме того, непонятно, как избирательно воздействовать на данный спин, если в молекуле есть несколько одинаковых спинов.
Системы сверхпроводящих гранул. При сверхнизких температурах единственной степенью свободы микроскопической сверхпроводящей гранулы (диаметром в несколько сотен ангстрем) является ее заряд. Он может изменяться на величину, кратную двум зарядам электрона (поскольку электроны в сверхпроводнике связаны в пары). Меняя внешний электрический потенциал, можно добиться такой ситуации, когда два зарядовых состояния будут иметь почти одинаковую энергию. Эти два состояния можно использовать в качестве базисных состояний квантового бита. Гранулы взаимодействуют между собой посредством джозефсоновских контактов и взаимной электрической емкости. Этим взаимодействием можно управлять. Основная трудность состоит в том, что нужно управлять каждой гранулой в отдельности, причем с высокой точностью. По-видимому, этот подход перспективен, но для его реализации потребуется создание новой технологии.
Анионы. Анионы -- это особые возбуждения в двумерных квантовых системах, в частности, в двумерной электронной жидкости в магнитном поле. Один из авторов (А.К.) считает этот подход наиболее интересным (поскольку он же его и придумал [32]), поэтому опишем его более подробно.
Основной проблемой при создании квантового компьютера является необходимость реализации унитарных преобразований с точностью . Для этого, как правило, требуется контролировать параметры системы с еще большей точностью. Однако можно представить ситуацию, когда высокая точность достигается автоматически, т.е. исправление ошибок происходит на физическом уровне. Примером являются двумерные системы с анионными возбуждениями.
Все частицы в трехмерном пространстве являются либо бозонами, либо фермионами. Волновая функция бозонов не меняется при перестановке двух частиц, а волновая функция фермионов умножается на . В любом случае при возвращении каждой из частиц на прежнее место состояние системы не меняется. В двумерных системах возможно более сложное поведение. Прежде всего заметим, что речь пойдет не об элементарных частицах типа электрона, а о возбуждениях, или дефектах в двумерной электронной жидкости. Такие возбуждения похожи на "настоящие" (т.е. элементарные) частицы, но обладают некоторыми необычными свойствами. Возбуждение может иметь дробный электрический заряд (например, от заряда электрона). При движении одного возбуждения вокруг другого состояние окружающей их электронной жидкости меняется строго определенным образом, зависящим от типа возбуждений и от топологии пути, но не от конкретной траектории. В простейшем случае волновая функция домножается на число ( для анионов в двумерной электронной жидкости в магнитном поле при факторе заполнения ). Возбуждения с таким свойством называются абелевыми анионами. Другой пример абелевых анионов описан (на математическом языке) в разделе 14.1.
Более интересны неабелевы анионы, которые пока не наблюдались экспериментально. (Теория предсказывает существование неабелевых анионов в двумерной электронной жидкости в магнитном поле при факторе заполнения .) При наличии нескольких неабелевых анионов состояние электронной жидкости является вырожденным, причем кратность вырождения экспоненциально зависит от числа анионов. Другими словами, существует не одно, а много состояний, которые могут образовывать произвольные квантовые суперпозиции. На такую суперпозицию нельзя никак воздействовать, не перемещая анионы, поэтому она идеально защищена от возмущений. Если обвести один анион вокруг другого, суперпозиция подвергнется определенному унитарному преобразованию. Это преобразование является абсолютно точным. (Ошибка может возникнуть, только если анион "вырвется у нас из рук" вследствие квантового туннелирования).
На первый взгляд, проект с использованием анионов выглядит наименее реалистично. Прежде всего, абелевы анионы не годятся для квантовых вычислений, а неабелевы еще только предстоит найти в эксперименте. Для реализации квантового компьютера нужно контролировать каждую из частиц, которые будут двигаться на расстояниях порядка долей микрона друг от друга. Это чрезвычайно сложная техническая задача. Однако, с учетом высоких требований к точности, осуществить любой из перечисленных выше подходов ничуть не легче. Кроме того, идея топологического квантового вычисления, лежащая в основе подхода с анионами, может воплотиться каким-либо другим способом. Например, защищенная от возмущений квантовая степень свободы может возникнуть на конце "квантовой проволоки" (одномерного проводника с нечетным числом распространяющихся электронных мод, находящегося в контакте с трехмерным сверхповодником).
Итак, идея квантового компьютера выглядит столь же заманчиво, сколь нереалистично. Наверное, так же воспринимался проект обычного компьютера во времена Чарльза Бэббиджа, изобретение которого было реализовано лишь сто лет спустя. Будем надеяться, что в наше время научно-технический прогресс идет быстрее, поэтому не придется ждать так долго. Возможно, достаточно одной свежей идеи плюс несколько лет на разработку новой технологии
Неформально алгоритм -- это однозначно определенная совокупность инструкций по преобразованию исходных данных в результат, причем все инструкции элементарны, т.е. при их выполнении "нам придется только механически следовать предписаниям, как если бы мы были роботами: от нас не потребуется ни понимания, ни искусства, ни изобретательности" [5, с. 270]. Формализовать это понятие можно различными способами.
Обычно подразумевается, что каждый алгоритм решает какую-то вычислительную задачу. С формальной точки зрения, вычислительная задача - это функция
Что такое "входные данные" и "результат"? Рассмотрим, например, задачу об умножении двух многочленов с целыми коэффициентами. Тогда входные данные - это пара многочленов. Проблема в том, как записать эти многочлены, чтобы их можно было ввести в компьютер. Машины Тьюринга, которые мы рассматриваем ниже, понимают лишь конечные последовательности символов (слова) из некоторого конечного множества , называемого внешним алфавитом. Поэтому строгая формулировка вычислительной задачи должна включать в себя алфавит и способ кодировки входных данных. Например, можно записать пару многочленов с использованием 10 цифр, символа переменной , знаков +, -, * и скобок: (x**2-5)(-4*x+1). В другой кодировке коэффициенты записываются в двоичной системе счисления и перечисляются через запятую; два многочлена разделяются звездочкой: 1, 0, -101* -100, 1. Таким образом, мы имеем две различные вычислительные задачи. С практической точки зрения, обе задачи эквивалентны, поскольку перевод из одной кодировки в другую осуществляется с помощью полиномиального алгоритма. Пока определения полиномального алгоритма у нас нет, давайте будем формалистами: вычислительная задача - это частичная1) функция (где обозначает множество конечных слов в алфавите ). Потом мы позволим себе некоторую вольность и будем говорить о задаче умножения многочленов или разложения целого числа на множители, имея ввиду, что все разумные кодировки эквивалентны (т.е. переводятся друг в друга при помощи полиномиальных алгоритмов). Однако нужно помнить, что не всякая кодировка является "разумной". Нехорошо, например, представлять натуральное число набором из звездочек, потому что длина такой записи экспоненциально велика по сравнению с двоичной или десятичной записью. Заметим также, что в некоторых задачах нет хорошего выбора "разумной" кодировки, в таких случаях (они нам не встретятся) необходимо указывать кодировку всякий раз, когда формулируется задача.
Теперь дадим формальное определение алгоритма.
Машина Тьюринга (сокращенно МТ) однозначно задается указанием набора , где , , -- конечные множества, причем ; -- некоторый элемент ; -- некоторый элемент , а -- некоторая (частичная, вообще говоря) функция из в .
Составляющие части МТ называются так:
-- множество состояний управляющего устройства,
Состояние МТ задается тройкой , где -- бесконечное слово в алфавите , т.е. произвольная последовательность элементов ; -- неотрицательное целое число; . Символы слова будем, как это принято, представлять записанными на ленте, разбитой на ячейки, по ячейке на символ. На ленте также имеется головка, которая расположена над ячейкой с номером . Наглядно это изображается так:
Рисунок 1.1: Лента, разбитая на ячейки
Помимо ленты машина Тьюринга имеет управляющее устройство, состояние которого задается элементом множества .
Состояния МТ меняются дискретно. За один такт работы управляющее устройство выполняет следующие действия (полагаем, что МТ находится в состоянии ):
читает символ, находящийся под головкой (т.е. определяет );
вычисляет значение функции переходов: (если функция переходов на паре не определена, то останавливает машину Тьюринга);
записывает на ленту в ячейку символ , сдвигает головку на и переходит в состояние (другими словами, новое состояние машины задается тройкой );
Пожалуй, всякий согласится, что эти действия не требуют ни понимания, ни искусства, ни изобретательности.
Работа машины Тьюринга будет всегда начинаться из состояния , где за конечным словом , состоящим из символов внешнего алфавита (множество таких слов обозначается ), следует бесконечное слово, целиком состоящее из пустых символов. Слово будем называть входом МТ. В любой момент времени слово, записанное на ленте, однозначно записывается в виде , где последний символ слова -- не пустой, а за ним идут только пустые символы. Будем называть слово используемой частью ленты.
Выполняя один такт работы за другим, машина Тьюринга порождает последовательность состояний
Если МТ останавливается, используемая часть ленты в достигнутом перед остановкой состоянии называется результатом работы МТ.
Каждая машина Тьюринга вычисляет частичную функцию из в , отображающую вход в результат работы МТ на входе при условии, что результат работы является словом во внешнем алфавите. Для входов, на которых машина не останавливается или результат содержит символы из , функция не определена. Из определения ясно, что любая МТ вычисляет ровно одну функцию (быть может, нигде не определенную).
Определение 1.1 Частичная функция из в называется вычислимой, если существует машина Тьюринга , для которой . При этом будем говорить, что вычислима на .
Не все функции вычислимы. Это ясно из сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счетное множество). Более интересные примеры см. в задачах 1.3-1.5.
Под предикатом будем понимать некоторое условие, которое выполняется (предикат истинен) или не выполняется (предикат ложен) для каждого слова из . Определенные таким образом, предикаты легко отождествляются с языками (подмножествами слов в ) -- предикату соответствует множество слов, на которых он истинен. Каждому предикату сопоставим характеристическую функцию, которая равна 1 на множестве слов, для которых предикат истинен, и равна 0 на множестве слов, для которых предикат ложен. Мы будем обозначать характеристическую функцию так же, как и сам предикат. Предикат разрешим, если его характеристическая функция вычислима. О машине Тьюринга, вычисляющей характеристическую функцию предиката, будем говорить, что она дает ответ ("да" или "нет") на вопрос "истинно ли значение предиката на входе ?"
Понятия вычислимой функции и разрешимого предиката будут использоваться и для функций (предикатов) от многих переменных.
Пусть -- некоторый алфавит, а -- натуральное число. Пусть -- машина Тьюринга с внешним алфавитом . Построим частичную функцию из в так: , если результат работы машины на входе совпадает со словом . Если машина не останавливается или на ленте записано что-нибудь не то (например, символы не из алфавита и т.п.), то не определена.
Определение 1.2. Частичная функция из в называется вычислимой, если существует машина Тьюринга , для которой .
Предикат от нескольких переменных разрешим, если его характеристическая функция вычислима.
Нас будут интересовать ресурсы, требующиеся для вычислений. Два важнейших ресурса -- время и память. Будем говорить, что машина Тьюринга работает за время , если максимальное (по всем входам длины ) количество тактов, которое проработает до остановки, равно . Аналогично, машина Тьюринга работает на памяти , если наиболее удаленное от начала ленты положение головки при вычислениях на входах длины равно .
Очевидно, что МТ задает алгоритм в смысле приведенного выше неформального определения. Обратное утверждение называется тезисом Черча:
"любой алгоритм может быть реализован машиной Тьюринга"
Не вдаваясь в обсуждение тезиса Черча, заметим, что в настоящее время нет серьезных оснований подвергать его сомнению. Все известные в настоящее время алгоритмы реализуются машинами Тьюринга. Подробное изложение теории алгоритмов читатель может найти в книгах [1, 5, 6, 10, 13, 16, 17]. Мы же ограничимся краткими неформальными пояснениями приемов программирования на машинах Тьюринга.
Возможности машины Тьюринга при таком неформальном обсуждении -- это возможности человека с ограниченной памятью, карандашом и ластиком, которому вручили неограниченной (бесконечной) толщины тетрадь. Страницы тетради имеют ограниченный размер (все возможные варианты заполнения страницы образуют алфавит МТ при строгом описании). На первых страницах тетради записано входное слово -- по одному символу (из внешнего алфавита) на страницу. Человек может листать тетрадь, стирать символы, записывать новые. Заканчивается эта его деятельность тем, что он закрывает тетрадь (сдвиг головки влево в положении 0) и возвращает результат своей работы.
Представив себя в такой ситуации, легко сообразить, что можно, запоминая несколько символов, выполнять любые действия на ограниченном количестве подряд идущих страниц; можно ставить на страницах дополнитель
Классические и квантовые вычисления курсовая работа. Программирование, компьютеры и кибернетика.
Контрольная Работа На Тему Никелирование И Хромирование
Дипломная работа по теме Процесс оптимизации и системного совершенствования управления социальной поддержки населения в Дзержинском районе г. Ярославля
Курсовая работа: Основи управлінського консультування
Особенности Торговых Связей России И Японии Реферат
Речь Современных Людей Сочинение
Реферат по теме Причины и структура конфликта
Курсовая работа: Институт президентства ФРГ. Скачать бесплатно и без регистрации
Я Рыцарь Сочинение По Истории 6
Курсовая работа по теме Порівняльна характеристика братських шкіл та єзуїтських колегіумів на українських землях у першій половині XVI-першій половині XVII ст.
Курсовая работа по теме Анализ эффективности результатов деятельности на ОАО 'Лукойл'
Жизнь Без Войны Сочинение
Дипломная работа по теме Проектирование сборного ригеля поперечной рамы здания
Реферат: Проектировка и корректировка организационной структуры предприятия
Реферат по теме Розрахунки й оптимізація характеристик систем електрозв’язку. (Расчёты и оптимизация характеристик систем электросвязи)
Курсовая работа: Организация строительного производства. Скачать бесплатно и без регистрации
Отчет по практике по теме Редактирование и отладка программ с помощью Pascal
Реферат: Обеспечение украинской экономики энергоносителями
Курсовая работа по теме Эффективность мер социального воздействия на семью, находящуюся в социально-опасном положении
Дипломная работа по теме Работа над созданием PR-отдела в рекламном агентстве 'Golden PR'
Курсовая работа: Субстанциальный подход в социальном познании
Автоматизация производства и информационные системы на предприятии (на материалах предприятия ООО "Уралресурсы") - Менеджмент и трудовые отношения курсовая работа
Численное решение обратных задач по восстановлению граничных условий уравнения параболического типа - Математика диссертация
Формирование культуры здоровья младших школьников в учебно-воспитательной среде начальной школы - Педагогика курсовая работа