Машина Тьюринга Реферат
Машина Тьюринга Реферат
Вход
Помощь
Заказать работу
махорин.docx
— 90.61 Кб ( Скачать файл )
© 2009 — 2020 Я неуч! — тысячи рефератов, курсовых и дипломных работ
Предметы
Поиск
Помощь
Автор работы: Пользователь скрыл имя, 08 Апреля 2013 в 23:39, реферат
Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, … . В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = {L, a1, a2 ,..., an-1 }, n ³ 2 . Пустая ячейка обозначается символом L, а сам символ L называется пустым, при этом остальные символы называются непустыми
1. Математическая модель машины Тьюринга 3 2. Работа машины Тьюринга 6 3. Примеры машин Тьюринга, работающих в алфавите {a, b} 7 4. Способы задания машин Тьюринга, операции над ними 11 5. Список используемой литературы 14
(Государственный
Технический Университет)
Математическая
логика и теория алгоритмов
1. Математическая модель
машины Тьюринга 3
3. Примеры машин Тьюринга, работающих в алфавите
{a, b} 7
4. Способы задания
машин Тьюринга, операции над ними 11
5. Список используемой
литературы 14
1. Математическая
модель машины Тьюринга
Идея создания
машины Тьюринга, предложенная английским
математиком А. Тьюрингом в тридцатых
годах XX века, связана с его попыткой
дать точное математическое определение
понятия алгоритма.
Машина Тьюринга (МТ) – это математическая
модель идеализированной цифровой вычислительной
машины.
Машина Тьюринга
является таким же математическим объектом, как функция, производная, интеграл, группа и т. д. Так же как и другие
мате-матические понятия, понятие машины Тьюринга
отражает объективную реальность, моделирует некие
реальные процессы.
Для описания алгоритма
МТ удобно представлять некоторое устройство, состоящее из четырех
частей: ленты, считывающей головки, устройства управления
и внутренней памяти.
1. Лента предполагается потенциально
бесконечной, разбитой на ячейки (равные клетки). При необходимости
к первой или последней клетке, в которой находятся
символы пристраивается пустая клетка. Машина работает
во времени, которое считается
дискретным, и его моменты занумерованы
1, 2, 3, … . В каждый момент
лента содержит конечное число клеток. В клетки в дискретный
момент времени может быть записан только один символ (буква) из внешнего алфавита A = {L, a 1 , a 2 ,..., a n - 1 }, n ³ 2 . Пустая ячейка обозначается
символом L, а сам символ L называется пустым, при этом остальные
символы называются непустыми. В этом алфавите A в виде слова
(конечного упорядоченного
набора символов) кодируется та информация, которая подается
в МТ. Машина «перерабатывает» информацию, поданную в виде
слова, в новое слово.
2. Считывающая
головка (некоторый считывающий
элемент) пере-мещается вдоль ленты
так, что в каждый момент
времени она обозревает
ровно одну ячейку
ленты. Головка может считывать
содержимое ячейки и записывать в нее
новый символ из алфавита А. В одном такте работы
она может сдвигаться только на одну ячейку
вправо (П), влево (Л) или оста-ваться на месте
(Н). Обозначим множество
перемещений (сдвига) головки D = {П, Л, Н}. Если в данный момент
времени t головка находится
в крайней клетке и сдвигается в отсутствующую
клетку, то пристраивается
новая пустая клетка, над которой окажется
головка в момент t + 1.
3. Внутренняя
память машины представляет собой
некоторое конеч-ное множество внутренних
состояний Q = { q 0 , q 1 , q 2 , ..., q m }, m ³ 1. Будем считать, что мощность
|Q | ³ 2. Два состояния машины
имеют особое значение: q 1 – начальное внутреннее
состояние (начальных внутренних
состояний может быть несколько), q 0 – заключительное
состояние или стоп-состояние (заключительное состояние
всегда одно). В каждый момент
времени МТ характеризуется положением
головки и внутренним состоя-нием. Например, под ячейкой, над которой находится
головка, указывается внутреннее
состояние машины.
4. Устройство
управления в каждый момент t в зависимости от
счи-тываемого в этот
момент символа на ленте и внутреннего
состояния ма-шины выполняет следующие
действия: 1) изменяет считываемый
в момент t символ a i на новый символ a j (в частности оставляет
его без изменений,
т. е. a i = a j ); 2) передвигает головку
в одном из следующих направлений:
Н, Л, П;
3) изменяет имеющееся
в момент t внутреннее состояние
машины
q i на новое q j , в котором будет машина
в момент времени t +1 (может
Такие действия устройства
управления называют командой, которую можно записать
в виде:
где q i – внутреннее состояние
машины в данный момент; a i – считываемый в этот
момент символ; a j – символ, на который изменяется
символ a i (может быть a i = a j ); символ D есть или Н, или Л, или П и указывает направление
движения головки; q j – внутреннее состояние
машины в следующий момент (может быть q i = q j ). Выражения q i a i и a j D q j называются левой
и правой частями этой команды соответственно. Число команд, в которых левые
части попарно различ-ны, является конечным
числом, так как множества Q \ {q 0 } и A конечны.
Не существует
команд с одинаковыми левыми частями, т. е. если про-грамма машины T содержит выражения q i a i ® a j D q j и q t a t ® a k D q k ,
то q i ¹ q t или a i ¹ a t и D Î{П, Л , Н}.
Совокупность
всех команд называется программой
машины Тьюринга. Максимальное число
команд в программе равно (n + 1) × m , где n + 1 = A и m + 1 = Q . Считается, что заключительное
состояние команды
q 0 может стоять только
в правой части команды, начальное состояние q 1
может стоять как
в левой так и в правой части команды.
Выполнение одной
команды называется шагом. Вычисление (или работа) машины Тьюринга
является последовательностью шагов одного
за другим без пропусков, начиная с первого.
Итак, МТ задана, если известны четыре
конечных множества: внешний алфавит A , внутренний алфавит Q , множество D перемещений головки
и программа машины, представляющая
собой конечное множество команд.
Работа машины
полностью определяется заданием в
первый (на-чальный) момент: 1) слова на ленте, т. е. последовательности
символов, записанных в клетках
ленты (слово получается
чтением этих символов по клеткам ленты
слева направо); 2) положения головки;
3) внутреннего со-стояния машины. Совокупность этих
трех условий (в данный момент) на-зывается конфигурацией
(в данный момент). Обычно в начальный
момент внутренним состоянием машины
является q 1 , а головка находится
либо над первой слева, либо над первой
справа клеткой ленты.
Заданное слово
на ленте с начальным состоянием q 1 и положение головки
над первым словом называется начальной конфигурацией. В противном случае
говорят, что машина Тьюринга
не применима к слову начальной конфигурации.
Другими словами, в начальный момент
конфигурация представима в следующем
виде: на ленте, состоящей из некоторого
числа клеток, в каждой клетке
записан один из символов внешнего алфавита A , головка находится
над первой слева или первой справа клеткой
ленты и внутренним состоянием машины
является q 1 . Получившееся в результате
реализации этой команды слово на ленте
и положение головки называется заключи-тельной конфигурацией.
Например, если в начальный
момент на ленте записано слово a 1 La 2 a 1 a 1 , то начальная конфигурация
будет иметь вид:
(под клеткой, над которой находится
головка, указывается внутреннее
со-стояние машины).
Работа машины
Тьюринга состоит в последовательном
применении команд, причем, применение той или
команды определяется текущей конфигурацией. Так в приведенном
выше примере должна применится команда
с левой частью q 1 a 1 .
Итак, зная программу и
задав начальную конфигурацию, полностью определяем
работу машины над словом в начальной
конфигурации.
Если в работе
машины Тьюринга в некоторый момент t выполняется команда, правая часть которой
содержит q 0 , то в такой момент
работа маши-
ны считается
законченной, и говорят, что машина применима
к слову на лен-те в начальной конфигурации. В самом деле, q 0 не встречается в
левой части ни одной команды – этим и объясняется
название q 0 «заключительное со-
стояние». Результатом работы
машины в таком случае считается слово, кото-рое будет записано
на ленте в заключительной конфигурации, т. е. в конфи-гурации, в которой внутреннее
состояние машины есть q 0 . Если же в работе
машины ни в
один из моментов не реализуется команда
с заключительным состоянием, то процесс вычисления
будет бесконечным. В этом случае гово-рят, что машина не применима
к слову на ленте в начальной конфигурации.
3. Примеры машин
Тьюринга , работающих в алфавите {a, b}
Проиллюстрируем
работу машину Тьюринга на следующем
примере.
Пример 1. Построить
машину Тьюринга T 1 , которая применима
ко всем словам с внешним алфавитом
{a,b} и делает следующее: любое слово x 1 x 2 ...x n , где x i = a или x i = b (i =1,2,...n) преобразует в слово x 2 ...x n x 1 ,
т. е., начиная работать
при слове x 1 x 2 ...x n на ленте в начальной
конфигу-
рации, машина остановится, и в заключительной
конфигурации на некото-ром участке ленты
будет записано слово x 2 ...x n x 1 , а все остальные
клетки ленты (если такие будут) окажутся пустыми.
Решение. За внешний алфавит
машины T 1 возьмем множество A = {L,a,b}, а за внутренний – Q = {q 0 ,q 1 ,q 2 ,q 3 }. Команды определим
сле-дующим образом: q 1 a ® LПq 2 , q 1 b ® LПq 3 , q i y ® yПП i , где y Î{a,b}, i = 2,3 ; q 2 L ® aHq 0 , q 3 L ® bHq 0 .
Рассмотрим работу
машины T 1 над словом ba . В работе машины
над словом ba начальная конфигурация
имеет следующий вид:
На первом шаге
действует команда: q 1 b ® LПq 3 . В результате создается
следующая конфигурация:
q 3 a ® aПП 3 , и на машине создается
Наконец, третий шаг обусловлен
командой q 3 L ® bHq 0 . В результате чего
создается конфигурация:
Эта конфигурация
является заключительной, так как машина оказалась
в состоянии остановки q 0 .
Таким образом, слово ba переработано в слово ab .
Полученную последовательность
конфигураций можно записать более
коротким способом. Конфигурация
(1) записывается в виде
следующего слова в алфавите A È Q : q 1 ba (содержимое обозреваемой
ячейки записано справа от состояния, в котором находится
данный момент машина). Далее, конфигура-ция (2) записывается так: q 3 a , конфигурация
(3) – aq 3 L , и наконец, (4)
– abq 0 .
Вся последовательность
записывается так: q 1 ba Þ Lq 3 a Þ aq 3 L Þ abq 0 .
Пример 2. Применить
машину Тьюринга T 1 из примера 1 к слову bbabb, исходя из начального
положения, при котором в состоянии q 1 обо-
зревается крайняя
левая ячейка, в котором содержится
символ этого слова.
Машина Тьюринга . Парадигма программирования. Реферат .
Рефераты : Машина Тьюринга
Машина Тьюринга
реферат - Машина Поста и машина Тьюринга .
Машина Тьюринга
Идеальные Сочинения Егэ По Русскому Языку 2021
Роль Друзей В Жизни Человека Сочинение
Эссе На Тему Свободное Время
Жизнь Молекулы Сочинение
Эссе На Тему Электричество В Моей Жизни