Машина Т юрінга. Конструкція машини Тюрінга, її функціональна схема і конфігурація. - презентация

1 Машина Т юрінга. Конструкція машины Тюрінга, її функціональна схема і конфігурація.

2

3 Описание машины Тьюринга Представляет собой бесконечную ленту, разделенную на ячейки. Имеет управляющее устройство, которое перемещается в двух направлениях. В управляющем устройстве содержится таблица, которая описывает порядок действий.

4 Отличия ЭВМ от машины Тьюринга Гланое отличие машины Тьюринга от ЭВМ – бесконечная лента В отличие от машины Тьюринга память реальных машин всегда конечна и ее ограничения удается преодолеть путем организации циклов.

5 Описание машины Тьюринга МТ будем называть конечный автомат: Задавая МТ, вместо двух функций можно использоваться одной, сопоставляющей каждой паре выходную тройку Логическая функция МТ

6 Анализатор скобок ( алгоритм Марвина Мински ) ), A1 Х, L, A2 (, A1 (, R, A1 λ, A1 λ, L, A3 X,A1 X, R, A1 λλ ())(() λλ Алфавит A=( (,), λ,0,1,Х ) ), A2 ), L, A2 (, A2 X, R, A1 λ, A2 0, S, A0 X,A2 X, L, A2 ), A3 нет (, A3 0, S, A0 λ, A3 1, S, A0 X,A3 X, L, A3 A0, A1, A2, A3 – состояния (А0 - остановка)

7 Пример работы машины Тьюринга Машина Тьюринга G задана таблицей и имеет следующие алфавиты и функции. G Х0Х0 Х1Х1 А1А1 Х 0,R, А 2 А2А2 Х 1,R, А 1 Х 1,L, А 0 Рассмотрим 2 входных слова:

8 Операции над машинами Тьюринга Пусть М1 и М2 – машины Тьюринга с общим алфавитом. М = М1 М2 – композиция (произведение МТ), тогда результат преобразования входного слова P машиной М: М(Р) = М2(М1(Р)) Если известны схемы машин М1 и М2, то схема композиции М = М1 М2 строится следующим образом: 1.СТОП-состояние машины М1 отождествляется с начальным состоянием машины М2; 2.СТОП-состояние машины М2 объявляется СТОП- состоянием композиции М = М1 М2 ; 3. Остальные состояния М2 пере обозначаются.

9 Пример композиции машин Тьюринга Пусть М1 и М2 - машины Тьюринга заданы следующими таблицами: Их композицией будет М = М1 М2. Алфавит состояний: - стоп общей МТ

10 Операции над машинами Тьюринга Пусть даны М1,М2,М3 – машины Тьюринга с общим алфавитом и некоторое условие Г. Разветвление машины М1 на машины М2 и М3 по признаку Г При построении машины М можно считать, что М1 имеет два СТОП-состояния A 0 и A 0 таких, что машина приходит в состояние A 0 в том случае, когда для М1(Р) выполнено условие Г и в A 0 в противном случае.

11 Операции над машинами Тьюринга Пусть даны М1,М2,М3 – машины Тьюринга с общим алфавитом и некоторое условие Г. Называется разветвление машины М1 с циклом, если выходное слово машины М2 снова подается на вход машины М1 (СТОП-состояние М2 отождествляется с начальным состоянием М1) Начало и конец цикла обозначают точкой () над соответствующими буквами. Если в МТ содержится более одного цикла, тогда принимается следующее обозначение: начало и конец второго цикла – две точки () над соответствующими буквами, начало и конец третьего цикла – три точки () и т.д.

12 Пример циклов в машинах Тьюринга Пусть М1, М2 и М3 – МТ заданы следующими таблицами: Алфавит состояний: Работа начинается с М1. Если прийти к первому СТОП-состоянию (1) тогда начинает работу М2. Ее СТОП-состояние – общее СТОП-состояние МТ М. Если прийти к (2) М1, тогда начинает работать М3. Ее СТОП-состояние – начальное состояние МТ М1.

13 Криптоанализ « Энигмы » Немецкая трёх роторная военная шифровальная машина «Энигма» Ротор «Энигмы» 1. кольцо с выемками 2. маркирующая точка для контакта «A» 3. алфавитное кольцо 4. залужённые контакты 5. электропроводка 6. штыревые контакты 7. пружинный рычаг для настройки кольца 8. втулка 9. пальцевое кольцо 10. храповое колесо

14 Дешифровальная машина «Bombe»

15 Полная функционирующая копия машины «Bombe» в Блэтчли - парке