 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Машины Тьюринга
|
|
В понятии “машина Тьюринга” не следует искать некоторый материальный объект − вычислительное устройство в общепринятом смысле. Это абстрактная вычислительная машина, концепция которой возникла в середине 30-х годов XX века у английского математика А. Тьюринга в результате произведенного им анализа действий человека, осуществляющего в соответствии с заранее разработанным планом поиск численного решения той или иной задачи. Этот анализ стимулировался желанием разрешения назревшей к тому времени проблемы поиска точной математической формулировки понятия алгоритма, в качестве которого до работ Тьюринга использовалось интуитивное понятие. Тьюрингом был сформулирован тезис: всякая интуитивно вычислимая функция может быть реализована на соответствующей машине Тьюринга (МТ).
В ходе развития теории алгоритмов появился целый ряд модификаций МТ, одна из наиболее распространенных версий которой была предложена Постом. Эту версию МТ обычно представляют в виде автоматически функционирующего устройства, включающего в себя следующие основные части:
1) внешний алфавит, т.е. конечное множество символов 
, с помощью которого входная информация кодируется в виде некоторой последовательности букв этого алфавита (слов) и вводится в машину. Последняя перерабатывает информацию, представленную в виде слова, в новое слово;
2) внутренний алфавит машины 
. Символы 
определяют конечное число состояний машины, причем два состояния имеют особое значение: 
− начальное состояние, 
− конечное состояние (стоп-состояние). Символы п, л, н − это соответственно символы сдвига (вправо, влево, на месте).
3) бесконечную в обе стороны ленту, представляющую собой внешнюю память машины. Эта лента разбита на клетки. В каждую клетку может быть записана только одна буква алфавита. Пустую клетку обозначают символом 
.
|
|
Перед началом работы машины на ленту записывается исходная информация, а управляющая головка устанавливается, как правило, у крайнего левого символа входного слова с указанием начального состояния 
, как показано на рис.1 (это состояние машины называют начальной конфигурацией).
|
1. После конечного числа тактов машина останавливается, переходя в стоп-состояние . При этом на ленте фиксируется новая информация. В таком случае говорят, что машина применима к исходной информации 
, так как может преобразовать ее в результирующую информацию 
.
2. Машина никогда не останавливается, т.е. не переходит в стоп-состояние , а продолжает работать бесконечно долго. В этом случае говорят, что машина неприменима к исходной информации .
В каждом такте МТ работает по функциональной схеме, которую условно можно представить так:
,
где 
п, л, н − символы сдвига.
В зависимости от того, какая буква на ленте обозревается (считывается) управляющей головкой (в приведенном выше случае буква 
) и в каком состоянии (в приведенном случае 
) находится машина, в каждом такте вырабатывается команда, определяющая поведение машины в следующем такте и состоящая из трех элементов:
1) буквы внешнего алфавита 
, на которую заменяется обозреваемая буква ;
2) адреса внешней памяти п, л, н;
3) нового состояния машины 
.
Совокупность всех команд, которые могут формироваться в каждом такте, образует программу МТ. Эта программа представляется двумерной таблицей и называется Тьюринговой функциональной схемой (табл. 10).
Таблица 10
| А Q | a 0 | a 1 | a 2 |
| q 1 |  a 2л q 3
| a 1п q 2 | a 2л q 1 |
| q 2 | a 0н q 2 | a 2н q 1 | a 1н q 2 |
| q 3 | a 0п q 0 | a 1п q 4 | a 2н q 1 |
| q 4 | a 1н q 3 | a 0п q 4 | a 2п q 4 |
Для простоты изображения различных конфигураций, получаемых в результате работы МТ, будем в дальнейшем записывать информацию в виде слова, не изображая самой ленты и ее разбивки на клетки. Не будем также изображать управляющую головку, а будем записывать лишь состояние машины.
Рассмотрим пример работы МТ, функциональная схема которой задана табл.10, а начальная конфигурация имеет вид
a 0 a 2 a 2 a 0.
q 1
Так как управляющей головкой обозревается буква a 2 и машина находится в состоянии q 1 то ею будет выработана команда a 2л q 1 которая находится в табл.10 на пересечении строки q 1 и столбца a 2 В соответствии с этой командой обозреваемая буква внешнего алфавита a 2 заменяется на ту же самую букву a 2 т.е. не изменяется, а состояние машины q 1 заменяется на q 1 т.е. тоже не изменяется, но происходит сдвиг управляющей головки влево вдоль ленты на одну клетку. В результате получим новую конфигурацию
a 0 a 2 a 2 a 0.
q 1
В этой конфигурации обозреваемая буква a 2 и состояние машины q 1 не изменились. Поэтому этой конфигурации соответствует та же команда, и мы сдвигаемся на одну клетку влево и получаем конфигурацию
a 0 a 2 a 2 a 0.
q 1
Пустой клетке a 0 и состоянию q 1 соответствует команда a 2л q 3 из табл.10. В соответствии с этой командой обозреваемая буква a 0 (пустая клетка) должна замениться на букву a 2, а состояние машины q 1 – на состояние q 3. С учетом этого и с учетом необходимости сдвига головки влево на одну клетку, получим конфигурацию
a 0 a 2 a 2 a 2 a 0.
q 3
Этой конфигурации соответствует команда a 0п q 0, выполняя которую, получим следующую конфигурацию:
a 0 a 2 a 2 a 2 a 0.
q 0
Так как в случае последней конфигурации машина попала в состояние q 0 (стоп-состояние), то процесс останавливается и слово a 2 a 2 a 2, заключенное между двумя пустыми клетками (слева a 0 и справа a 0), является результатом работы машины. Поскольку исходным словом было a 2 a 2, то произошло преобразование его машиной Тьюринга в слово a 2 a 2 a 2.
Рассмотрим случай, когда процесс будет повторяться бесконечно долго. Пусть функциональная схема задается той же табл.10, а исходная конфигурация имеет вид
a 0 a 1 a 2 a 2 a 0.
q 1
Так как управляющей головкой обозревается буква a 2 а машина находится в состоянии q 1, то в соответствии с табл.10 машиной будет выработана команда a 2л q 1. Поэтому управляющая головка сдвинется влево на одну клетку, буква a 2 заменится на a 2 (т.е. останется без изменения), состояние q 1 также не изменится и следующая (вторая) конфигурация будет иметь вид
a 0 a 1 a 2 a 2 a 0.
q 1
Третья конфигурация будет такой:
a 0 a 1 a 2 a 2 a 0,
q 1
четвертая − a 0 a 1 a 2 a 2 a 0, пятая − a 0 a 1 a 1 a 2 a 0, шестая – a 0 a 1 a 2 a 2 a 0.
q 2 q 2 q 1
Видим, что процесс начал повторяться (шестая конфигурация совпадает со второй), и если его не остановить, то он будет продолжаться бесконечно долго. Таким образом, результат не может быть получен. В таком случае говорят, что МТ неприменима к исходной информации.
Рассмотренные примеры демонстрировали абстрактную суть МТ. Чтобы продемонстрировать построение МТ для решения хотя и простой, но реальной задачи, рассмотрим следующий пример: построить МТ, реализующую алгоритм вычисления функции 
, где 
– любое число десятичной системы счисления.
Решение. Очевидно, что внешний алфавит А будет состоять из символов 
. Тогда для реализации указанного алгоритма необходимо, чтобы МТ, находясь в некотором состоянии, заменяла последнюю цифру числа (если эта цифра меньше 8) цифрой на две единицы большей и переходила в стоп-состояние. Если последняя цифра числа 
, то ее нужно заменить на 0 и сдвинуться на одну клетку влево, перейдя в новое состояние q 2. Состояние q 2 должно добавлять 1 к следующему разряду. Если же последняя цифра числа 
, то ее нужно заменить на 1 и сдвинуться влево на одну клетку, перейдя в состояние 
.
Таким образом, МТ будет иметь три состояния: 
и , а функциональная схема машины будет представлена таблицей (функциональной схемой):
| a 0 | ||||||||||||
| q 1 | 2н q 0 | 3н q 0 | 4н q 0 | 5н q 0 | 6н q 0 | 7н q 0 | 8н q 0 | 9н q 0 | 0л q 2 | 1л q 2 | |||
| q 2 | 1н q 0 | 1н q 0 | 2н q 0 | 3н q 0 | 4н q 0 | 5н q 0 | 6н q 0 | 7н q 0 | 8н q 0 | 9н q 0 | 0л q 2 |
Вычислим по приведенной функциональной схеме (фактически по алгоритму) значения функции 
для 
и 298, записав последовательно соответствующие конфигурации:
1. 
1) a 0 9 8 a 0; 2) a 0 9 0 a 0; 3) a 0 0 0 a 0; 4) a 01 0 0 a 0, т.е. 
.
q 1 q 2 q 2 q 0
2. 
1) a 0 5 9 a 0; 2) a 0 5 1 a 0; 3) a 0 6 1 a 0, т.е. 
.
q 1 q 2 q 0
3. 
1) a 0 8 8 a 0; 2) a 0 8 0 a 0; 3) a 0 9 0 a 0, т.е. 
.
q 1 q 2 q 0
4. 
1) a 0 2 9 8 a 0; 2) a 02 9 0 a 0; 3) a 0 2 0 0 a 0; 4) a 0 3 0 0 a 0,
q 1 q 2 q 2 q 0
т.е. 
.
Как отмечалось вначале данного подраздела, МТ дает один из путей уточнения понятия алгоритма. В соответствии с этой теорией, последовательность действий, с помощью которых может быть решена некоторая задача, является алгоритмом, если она может быть реализована соответствующей МТ. Однако при этом возникает ряд вопросов: является ли способ задания алгоритмов функциональной схемой для соответствующей МТ универсальным и всякий ли алгоритм может быть реализован МТ?
На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы (тезис Тьюринга): всякий алгоритм может быть задан в виде тьюринговой функциональной схемы и реализован на соответствующей МТ.
Гипотезу Тьюринга, как и приведенный выше тезис Чёрча, нельзя доказать, так как он связывает нестрогое определение понятия алгоритма со строгим определением понятия МТ. Однако эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Но до настоящего времени такие примеры неизвестны.
Интересным примером опровержения гипотезы, непосредственно не относящимся к теории алгоритмов, но являющимся поучительным, является гипотеза Эйлера, формулируемая следующим образом: для любого показателя 
диофантово уравнение (это уравнение вида 
, где 
является многочленом с целочисленными коэффициентами)
не имеет решений в натуральных числах, если 
При 
эта гипотеза превращается в упоминавшуюся ранее великую теорему Ферма.
В течение более 200 лет никому так и не удавалось ни доказать, ни опровергнуть гипотезу Эйлера. И только в 70-е годы ХХ века группа американских ученых с помощью мощного компьютера (очевидно, путем перебора) получила всего один единственный результат:
.
Этим самым гипотеза Эйлера была опровергнута.
А несколько позже американский ученый Roger Frye получил уникальный результат − наименьший по числу слагаемых контрпример, опровергающий гипотезу Эйлера:
.
Читателям предлагается самостоятельно проверить приведенные контрпримеры.
Свое развитие теория алгоритмов, основанная на понятии МТ, получила в последние годы путем рассмотрения различных модификаций МТ. Самыми распространенными среди них являются многоленточные МТ, имеющие по одной или нескольку головок на каждой из лент. Движение головок и запись букв на лентах происходят одновременно согласно программе, записанной в функциональной схеме.
С помощью многоленточных МТ естественно формализуется понятие вероятностного алгоритма. Распространенный подход состоит в том, что на одной из лент многоленточной МТ записывается случайная последовательность букв, и МТ в каждый момент времени считывает ровно одну букву этой последовательности. При этом выбор команд для каждой управляющей головки осуществляется с заданными вероятностями.
Дата публикования: 2015-01-10; Прочитано: 566 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
