П. От конечных автоматов к машине Тьюринга

Машина Тьюринга: от конечных автоматов к машине Тьюринга. Примеры использования МТ. Обратимая машина Тьюринга .

Лекция 3 Машина Тьюринга . Обратимые компьютеры.

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

Вторая часть главы посвящена актуальной для квантовых вычислений теме – обратимой машине Тьюринга

 

 

В этой связи вначале коснемся проблемы моделирования реальности.

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

Вначале напомним некоторые положения теоретической информатики….

Важное понятие в теории вычислений – сложность вычисления. Эта величина определяется через объем (количество) ресуров , необходимых для вычисления. Последние в свою очередь интуитивно связаны с временем вычисления и необходимым объемом памяти Конкретное количество ресурсов, необходимое компьютеру для расчета некоторого алгоритма зависит от его (компьютера) архитектуры. Так, например, время необходимое одному компьютеру для вычисления произведения двух n-разрядных чисел пропорционально полиному . Для другого компьютера это время пропорционально полиному . Принято за оценку времени вычисления алгоритма принимать член высшего по n порядка и обозначать это время символом в первом случае и - во втором. Эта оценка обозначает верхний предел времени вычисления алгоритма. Существует еще и нижняя оценка указанного времени ,т.е. минимально необходимое время вычисления. Обозначается это время символом .

В теории вычислительных систем считается что алгоритм считается эффективным с точки зрения какого-либо ресурса (например, времени или количества памяти ( «пространства» , как его иногда именуют)) если его количество, необходимое для вычисления данного алгоритма не превышает для некоторого k. В этом случае говорят, что данный алгоритм является полиномиальным относительно данного ресурса. Если верхний предел ресурса нельзя выразить полиномом ( или логарифмом n) , то алгоритм называют экспоненциальным и он считается неэффективным. Оценка эффективности алгоритма имеет огромное практическое значение. Огромное разнообразие размеров и архитектур современных компьютеров означает , что проблема оценки эффективности алгоритмов ( и вычислимости) является исключительно непростой.

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

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

 

п. Конечные автоматы Основные идеи. Конечные автоматы – это такие машины, которые переходят из одного состояния в другое, причем оба эти состояния принадлежат некоторому конечному набору. Эти устройства представляют интерес потому, например, что в ряде случаев они оказываются удивительно мощными вычислителями и , кроме того, их поведение легко описать полностью, без какой-либо неопределенности или аппроксимации. Для конечных автоматов характерна простая связь между структурой и поведением. Если нам дано: 1) описание автомата, 2) его начальное состояние и 3) описание сигналов, которые поступают в него из среды, то мы можем описать его состояние в каждый последующий момент времени. Это достигается путем пошагового установления последовательности состояний машины во времени. При этом со временем теория конечных автоматов обходится весьма своеобразно. Поведение машины описывается как простая линейная последовательность событий во времени. Эти события происходят лишь в дискретные моменты времени, в промежутках между которыми не случается ничего. Эти моменты образуют регулярную последовательность и им можно сопоставить целые числа, т.е. время t принимает лишь целочисленные значения. При желании можно считать, что машина работает непрерывно, а наши моменты времени соответствуют случаям, когда «фотографируются» состояния системы. Таким образом, можно рассматривать любую детерминированную систему. Однако такой подход возможен в случае, если система удовлетворяет требованию – в конце каждого интервала времени машина находится в одном из конечного числа возможных состояний ( физик бы сказал – в одном из возможных состояний из некоторого дискретного набора). С позиции физики конечные автоматы это устройства, работа которых предполагает квантованность времени , что кажется весьма рискованным особенно в случае использования автомата для моделирования физической задачи. С позиций пользователя машину можно рассматривать как «черный ящик» с входными и выходными клеммами. Воздействие на машину осуществляется через входные каналы и время от времени машина воздействует на пользователя через выходные каналы. Пользователю не обязательно знать, как устроена и как работает такая машина. Ему важно знать лишь ее входно-выходные характеристики. именно поэтому мы определили это устройство как «черный ящик». Точнее, интерес представляет множество различимых состояний, которые может иметь канал. Предположение о том, что число возможных состояний канала конечно, является одним из основных постулатов теории автоматов. Будем обозначать входной канал буквой S, а выходной – буквой R. Входной канал может находиться в некоторых состояниях ,которые будем также называть сигналами. Выходной канал может находиться в состояниях. В каждый момент времени t среда определяет некоторое состояние входа S, которое является входным воздействием на машину. Будем обозначать это воздействие через S(t).В каждый момент машина выбирает некоторое состояние выхода (ответный сигнал), которое некоторым образом воздействует на среду. Ответный сигнал в момент t будем обозначать как R(t). Для того чтобы более полно представить себе функционирование машины необходимо установить каким образом ее выходные сигналы зависят от входных? Каково будет состояние выхода R в некоторый момент времени t ? В общем случае это зависит от всей предыстории системы. Здесь мы условимся, что состояние выхода в момент времени t не зависит от состояния входа в тот же момент времени. Иными словами мы не допускаем мгновенного прохождения сигнала через устройство. Но выход в момент времени t+1 зависит, хотя бы частично, от входа в момент времени t. Это ограничение отражает физическую невозможность мгновенного перехода из одного места в другое. Но здесь оно вводится по простой причине- чтобы избежать нереализуемой ситуации, когда каналы оказываются просто непосредственно соединены друг с другом и избежать мгновенной реакции также физически нереализуемой. Представим, что машина М функционирует, взаимодействуя с внешней средой Е (Environment) в течение некоторого неизвестного промежутка времени. Машина получает сигналы от среды Е и реагирует на эти сигналы. Обозначим через Н(t) предысторию этого процесса до момента времени t. Таким образом, предполагается, что Н(t) некоторым образом описывает все события, относящиеся к машине М с момента времени ее создания до момента времени t. Предполагается также, что предыстория Н(t) машины М содержит запись всех воздействий на М с тех пор, как она начала функционировать. Если в момент t мы отключим М от среды и подадим на вход сигнал , то машина в момент t+1 ответит сигналом . Какой именно сигнал появится на выходе машины в момент t+1, будет зависеть как от того какой выбран сигнал , так и от внутреннего состояния машины М в момент t. Предполагая, что ситуация внутри М определяется ее предысторией Н(t), можно написать: К сожалению, любое такое соотношение оказывается исключительно громоздким, для того чтобы пользоваться им непосредственно. Это объясняется слишком явной зависимостью состояния выхода от всей предыстории. Необходимо заменить это соотношение другим, в котором состояние выхода R(t+1) и входное взаимодействие S(t) были бы связаны гораздо более прямо. Это можно сделать, если ввести некоторое ограничение на природу машины М – оно состоит в том ,что машина М должна быть в некотором смысле конечной. Для данной машины М в данный момент t можно представить себе бесконечное число возможных предысторий. Лишь та из них, которая имела место на самом деле, определяет реакцию машины на следующее входное воздействие. Может оказаться, что на определение этой реакции на выходе существенное влияние оказывают события из очень отдаленного прошлого. Если каждому событию из этого прошлого соответствует своя линия поведения машины, то машина должна иметь в определенном смысле бесконечно большую память, чтобы помнить эти события. Для нас практический интерес могут представлять машины, состоящие из конечного числа дискретных элементов, таких как переключатели, реле или магнитные сердечники и транзисторы. Эти устройства способны хранить информацию о прошлых событиях, но эта память физически ограничена . Если память машины ограничена, то машина не может помнить всего, что с ней случилось и ее поведение не может по разному зависеть от всех возможных предысторий. Здесь можно ввести понятие об эквивалентности двух предысторий. Представим, что мы имеем две абсолютно одинаковые машины М. Но к моменту времени t их истории Н(t) , возможно из-за различия сред Е оказались различными. Мы будем говорить что предыстории Н₁ и Н₂ являются эквивалентными предысториями относительно машины М, если в дальнейшем для любой возможной последовательности сигналов машины и будут иметь одинаковые сигналы на своих выходах. Это значит, что не существует способа различить машины , подавая на их входы последовательности сигналов и наблюдая реакции на их выходах. Определим теперь класс эквивалентности любой предыстории как множество всех предысторий, эквивалентных ей. Поскольку две истории эквивалентные третьей, эквивалентны друг другу, то все члены класса эквивалентности эквивалентны между собой. Ясно, что два класса эквивалентности не могут частично перекрываться – они должны быть полностью отличны друг от друга, либо полностью совпадать. Мы приходим , таким образом, к основному постулату теории конечных автоматов: машина может различать в своем настоящем и будущем поведении лишь конечное число классов возможных предысторий. Эти классы мы будем называть «внутренними состояниями» машины. Внутреннее состояние машины в момент времени t мы будем обозначать символом Q(t), а сами состояния – символами . В соответствии с нашим определением внутреннего состояния ответный сигнал машины на входное воздействие может зависеть лишь от . В противном случае поведение зависело бы не только от различных классов предысторий. Эту зависимость можно записать в виде: Сигнал , зависит конечно от среды. От чего зависит внутреннее состояние ? Конечно , внутреннее состояние зависит от всей предыстории машины. Но! Оказывается нетрудно доказать, что зависимости от недавнего прошлого и далеких во времени событий можно легко отделить друг от друга. В самом деле предыстория в момент t+1 отличается от предыстории в момент t лишь наличием дополнительного члена, который описывает то что случилось в момент t , а именно наличием сигнала . По предположению ничто другое не может влиять на то, что происходит внутри черного ящика. Каково же внутреннее состояние машины в момент t+1? Состояние может зависеть лишь от предыдущего входа и от предыдущего внутреннего состояния . В противном случае машина могла бы различать в своем будущем поведении две предыстории, которые по предположению принадлежат одному и тому же классу и, следовательно, неразличимы. Это утверждение можно записать в виде: Два выражения для и дают самое полное описание машины, которое только можно пожелать, оставаясь безразличным к тому, что в действительности происходит внутри черного ящика. Действительно, предположим, что нам сообщили внутреннее состояние машины Q(t) в некоторый момент t , а также последовательность входных воздействий, которые будут поступать на вход машины с этого момента . Тогда функции F и G определят, какой выход R(t+1) следует ожидать в момент t+1, а также внутреннее состояние Q(t+1) , в котором машина будет находиться в этот момент. После этого снова, используя функции F и G, мы можем определить выход и внутреннее состояние в момент t+2. Мы можем продолжать шаг за шагом эти вычисления, с тем, чтобы находить выход и внутреннее состояние машины в любой момент времени в будущем ( до тех пор пока мы знаем, какой вход будет в этот момент). Конечная машина описана полностью, когда заданы ее функции переходов F и G. Каждая из этих функций задана для конечного числа значений входного сигнала, так что сами эти функции можно представить в виде таблиц. В качестве первого примера рассмотрим устройство «запоминания» . ПРИМЕР1. Запоминающий автомат.

 

Входной канал может передавать только два вида сигналов, называемых и , и имеются

Только два внутренних состояния и и два выходных сигналаи .

 

 

Из таблиц видно, что состояние в момент t ( или выход в момент t+1) указывает, каким был сигнал, появившийся в момент t-1: или . (Задача: показать, что автомат, выход которого в момент t+1 указывает, каков был сигнал в момент t требует лишь одного состояния). Ввиду того, что между входом и выходом автомата имеется как бы встроенная задержка на единицу времени, можно считать , что описанный автомат имеет зачаточную способность к запоминанию – в данном случае к сохранению цифры, которая оказалась на входе в момент t -1.

 

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