Машина Тьюринга

Автор работы: Пользователь скрыл имя, 03 Марта 2014 в 18:27, доклад

Описание работы

Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. В каждой клетке может быть записан один символ или ничего не записано. Содержимое клетки может менятся – в нее можно записать другой символ или стереть находящийся там символ.
Пустое содержимое клетки договорились называть символом «пусто» и обозначать знаком Λ. В связи с этим изображение ленты, показанное на рисунке справа, такое же, как на рисунке слева. Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа , поэтому вместо длинной фразы «записать символ в клетку или стереть находящийся там символ» можно говорить просто «записать символ в клетку».

Файлы: 1 файл

1_машина Тьюринга.docx

— 39.66 Кб (Скачать файл)

Машина Тьюринга

Машина Тьюринга состоит из двух частей – ленты и автомата.


 

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

Пустое содержимое клетки договорились называть символом «пусто» и обозначать знаком Λ. В связи с этим изображение ленты, показанное на рисунке справа, такое же, как на рисунке слева.  Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа  , поэтому вместо длинной фразы «записать символ в клетку или стереть находящийся там символ» можно говорить просто «записать символ в клетку».

Автомат – это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит ее содержимое; это видимая клетка, а находящийся в ней символ – видимый символ; содержимое соседних и других клеток автомат  не видит.

Кроме того в каждый момент автомат находится в одном из состояний, которые будем обозначать q1, q2, и так далее. Находясь в некотором состоянии, автомат  выполняет какую-то определенную операцию (например, перемещается направо по ленте, заменяя все символы b на a), находясь в другом состоянии – другую операцию. Пару из видимого символа (S) и текущего состояния (q) будем называть конфигурацией и обозначать <S,q>.

Автомат может выполнять три элементарных действия:

1) записывать в видимую клетку новый символ (менять содержимое других клеток автомат не может);

2) сдвигаться на одну клетку влево или вправо («перепрыгивать» сразу через несколько клеток автомат не может);

3) переходить в новое состояние.

Ничего другого делать автомат не умеет, поэтому все более сложные операции так или иначе должны быть сведены к этим трем элементарным действиям.

 

Пример 1 (перемещение автомата, замена символов)

 

A={0,1,2,3,4,5,6,7,8,9}, P – непустое. Требуется получить на ленте запись числа на 1 больше числа  P.

 

Например:

 

Возможны 3 случая.


1)


 

 

1)       2)     3)

 

Решение.

 

 

0

1

2

3

4

5

6

7

8

9

Λ

q1

,R,

,R,

,R,

,R,

,R,

,R,

,R,

,R,

,R,

,R,

,L,q2

q2

1,,!

2,,!

3,,!

4,,!

5,,!

6,,!

7,,!

8,,!

9,,!

0,L,q2

1,,!


 

1) q1 – под последнюю цифру;

2) q2 – видимая цифра + 1.

 

Пример 2 (анализ символов)

 

A={a,b,c}. Перенести первый символ непустого слова p в его конец.

 

Например:


Решение.

 

Для решения этой задачи предлагается выполнить следующие действия:

1) запомнить первый символ слова P, а затем стереть этот символ;

2) перегнать автомат вправо под первую пустую строку за P  и записать в нее запомненный символ.

Как «бегать» вправо, мы уже знаем из предыдущего примера. А вот как запомнить первый символ? Ведь в МТ нет другого запоминающего устройства, кроме ленты, а запоминать символ в какой-то клетке на ленте бессмысленно: как только автомат сдвинется влево или вправо от этой клетки, он тут же забудет данный символ. Что делать?

Выход здесь таков – надо использовать разные состояния автомата. Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конец a. Если же первым был символ b, то надо перейти в состояние q3, где делается все то же самое, только в конце записывается символ b. Если же первым был символ с , тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c. Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разные состояния. Это типичный прием программирования на МТ.

С учетом сказанного программа будет такой:

 

 

a

b

c

Λ

 

q1

Λ,R,q2

Λ,R,q3

Λ,R,q4

,R,

анализ 1-го символа, удаление его, разветвление

q2

,R,

,R,

,R,

a,,!,

запись a справа

q3

,R,

,R,

,R,

b,,!,

запись b справа

q4

,R,

,R,

,R,

c,,!,

запись c справа


 

При пустом слове, которое является «плохим» для программы, программа зациклится.

Если же входное слово ровно один символ, тогда автомат сотрет этот символ, сдвинется на одну клетку вправо и запишет в нее данный символ.

 

 

 


Информация о работе Машина Тьюринга