Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Определение машины Тьюринга

Содержание

Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процессЭто математический объект, а не физическая машинаПредложена Аланом Тьюрингом в 1936 году
Определение машины Тьюринга Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процессЭто математический объект, а не 1) Внешний алфавит А = {a0, a1, …, an} Элемент a0 называется пустой символВ 2) Внутренний алфавит Q = {q0, q1, …, qm}, {П, Л, С}В любой 3) Внешняя память (лента)Машина имеет ленту, разбитую на ячейки, в каждую из 3) Внешняя память (лента)Устройство машины ТьюрингаПустая клетка содержит a0. В каждый момент 4) Каретка (управляющая головка)Каретка машины располагается над некоторой ячейкой ленты – воспринимает 5) Функциональная схема (программа)Программа машины состоит из команд:Устройство машины ТьюрингаДля каждой пары Замечание1) В недетерминированной машине может появиться несколько параллельных вычислительных процессов2) Разные машины К началу работы машины на ленту подается исходный набор данных в виде Описание работы машины ТьюрингаСтандартное положение называется начальным (заключительным), если машина, воспринимающая слово Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим состоянием Описание работы машины ТьюрингаВ соответствии с командой qiaj → qkal Х выполняются При переходе машины в заключительное состояние q0 ее работа прекращаетсяНа ленте записан Машинным словом (конфигурацией) машины Тьюринга называется слово вида α1qkal α2, где α1 Конфигурация α1qkal α2 интерпретируется следующим образом:- машина находится в состоянии qk- каретка ПримерДана машина Тьюринга с внешним алфавитом А = {a0, 1, * }, Решение Решение1) Заменяем содержимое обозреваемой ячейки 1 на а0 Решение2) Машина переходит в новое состояние q2 Решение3) Каретка перемещается влево РешениеПолное подробное решение РешениеПолное подробное решение РешениеПолное подробное решение РешениеРешение, записанное с помощью конфигураций (в строчку) α = 1*11Ответ: β = 111 ЛитератураИгошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. - Люди могут вести себя по-разному в одинаковых ситуациях, и этим они принципиально отличаются от машин.
Слайды презентации

Слайд 2 Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс

Это

Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процессЭто математический объект, а

математический объект, а не физическая машина

Предложена Аланом Тьюрингом в

1936 году

Слайд 3
1) Внешний алфавит
А = {a0, a1, …, an}
Элемент

1) Внешний алфавит А = {a0, a1, …, an} Элемент a0 называется пустой

a0 называется пустой символ

В этом алфавите в виде слова

кодируется исходный набор данных и результат работы алгоритма

Устройство машины Тьюринга

Слайд 4
2) Внутренний алфавит
Q = {q0, q1, …, qm},

2) Внутренний алфавит Q = {q0, q1, …, qm}, {П, Л, С}В

{П, Л, С}

В любой момент времени машина М находится

в одном из состояний q0, q1, …, qm

При этом: q1 - начальное состояние
q0 - заключительное состояние

Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)

Устройство машины Тьюринга

Слайд 5
3) Внешняя память (лента)
Машина имеет ленту, разбитую на

3) Внешняя память (лента)Машина имеет ленту, разбитую на ячейки, в каждую

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

одна буква

Устройство машины Тьюринга

Слайд 6
3) Внешняя память (лента)

Устройство машины Тьюринга
Пустая клетка содержит

3) Внешняя память (лента)Устройство машины ТьюрингаПустая клетка содержит a0. В каждый

a0.
В каждый момент времени на ленте записано конечное

число непустых букв

Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов.

Это соответствует принципу абстракции потенциальной осуществимости

Слайд 7
4) Каретка (управляющая головка)
Каретка машины располагается над некоторой

4) Каретка (управляющая головка)Каретка машины располагается над некоторой ячейкой ленты –

ячейкой ленты – воспринимает символ, записанный в ячейке

В одном

такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте

Устройство машины Тьюринга

Слайд 8
5) Функциональная схема (программа)
Программа машины состоит из команд:




Устройство

5) Функциональная схема (программа)Программа машины состоит из команд:Устройство машины ТьюрингаДля каждой

машины Тьюринга
Для каждой пары (qi, aj) программа машины должна

содержать одну команду (детерминированная машина Тьюринга)

Слайд 9 Замечание
1) В недетерминированной машине может появиться несколько параллельных

Замечание1) В недетерминированной машине может появиться несколько параллельных вычислительных процессов2) Разные

вычислительных процессов

2) Разные машины Тьюринга отличаются своими программами
Для каждого

алгоритма создается своя машина Тьюринга, точнее ее программа


Слайд 10
К началу работы машины на ленту подается исходный

К началу работы машины на ленту подается исходный набор данных в

набор данных в виде слова α

Описание работы машины Тьюринга
Будем

говорить, что непустое слово α в алфавите А\{a0} воспринимается машиной в стандартном положении, если:
- оно задано в последовательных ячейках ленты,
- все другие ячейки пусты,
- машина обозревает крайнюю правую ячейку из тех, в которых записано слово α

Слайд 11
Описание работы машины Тьюринга
Стандартное положение называется начальным (заключительным),

Описание работы машины ТьюрингаСтандартное положение называется начальным (заключительным), если машина, воспринимающая

если машина, воспринимающая слово в стандартном положении, находится в

начальном состоянии q1 (стоп-состоянии q0)

Слайд 12 Находясь в не заключительном состоянии, машина совершает шаг,

Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим

который определяется текущим состоянием qi и обозреваемым символом aj

Описание

работы машины Тьюринга

Слайд 13
Описание работы машины Тьюринга
В соответствии с командой qiaj

Описание работы машины ТьюрингаВ соответствии с командой qiaj → qkal Х

→ qkal Х выполняются следующие действия:

1) Содержимое обозреваемой ячейки

aj стирается и в нее записывается символ al (который может совпадать с aj)

2) Машина переходит в новое состояние qk (оно может совпадать с состоянием qi)

3) Каретка перемещается в соответствии с управляемым символом Х ∈ {П, Л, С}

Слайд 14 При переходе машины в заключительное состояние q0 ее

При переходе машины в заключительное состояние q0 ее работа прекращаетсяНа ленте

работа прекращается

На ленте записан результат работы алгоритма – слово

β в алфавите А\{a0}

Описание работы машины Тьюринга

Слайд 15
Машинным словом (конфигурацией) машины Тьюринга называется слово вида

Машинным словом (конфигурацией) машины Тьюринга называется слово вида α1qkal α2, где

α1qkal α2, где α1 и α2 - слова в

алфавите А.

Слайд 16 Конфигурация α1qkal α2 интерпретируется следующим образом:

- машина находится

Конфигурация α1qkal α2 интерпретируется следующим образом:- машина находится в состоянии qk-

в состоянии qk
- каретка обозревает на ленте символ al


- α1 и α2 – это содержимое ленты до и после символа al

Слайд 17 Пример
Дана машина Тьюринга с внешним алфавитом А =

ПримерДана машина Тьюринга с внешним алфавитом А = {a0, 1, *

{a0, 1, * }, алфавитом внутренних состояний Q =

{q0, q1, q2, q3}, и следующей функциональной схемой:

Применить машину Тьюринга к слову α=11*1, начиная со стандартного начального положения

Слайд 18 Решение


Решение

Слайд 19 Решение
1) Заменяем содержимое обозреваемой ячейки 1 на а0

Решение1) Заменяем содержимое обозреваемой ячейки 1 на а0

Слайд 20 Решение
2) Машина переходит в новое состояние q2

Решение2) Машина переходит в новое состояние q2

Слайд 21 Решение
3) Каретка перемещается влево

Решение3) Каретка перемещается влево

Слайд 22 Решение
Полное подробное решение

РешениеПолное подробное решение

Слайд 23 Решение
Полное подробное решение

РешениеПолное подробное решение

Слайд 24 Решение
Полное подробное решение

РешениеПолное подробное решение

Слайд 25 Решение
Решение, записанное с помощью конфигураций (в строчку)

РешениеРешение, записанное с помощью конфигураций (в строчку)

Слайд 26 α = 1*11
Ответ: β = 111

α = 1*11Ответ: β = 111

Слайд 27 Литература
Игошин В.И. Математическая логика и теория алгоритмов. –

ЛитератураИгошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008.

М.: Академия, 2008. - 448 с.
Лихтарников Л.М., Сукачева Т.Г.

Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с.
Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.
  • Имя файла: opredelenie-mashiny-tyuringa.pptx
  • Количество просмотров: 89
  • Количество скачиваний: 0
- Предыдущая Начальная военная подготовка
Следующая - Упражнения в написании слов с заглавной буквы

Похожие презентации

Презентация устный счёт к уроку математики 4 класс Презентация устный счёт к уроку математики 4 класс 119
Методическая разработка: Конспект непрерывной образовательной деятельности Образование числа 5 план-конспект занятия по математике (средняя группа) Методическая разработка: Конспект непрерывной образовательной деятельности Образование числа 5 план-конспект занятия по математике (средняя группа) 125
Блиц-опрос Блиц-опрос 96
Открытый урок по математике Состав числа 13 план-конспект урока по математике (2 класс) Открытый урок по математике Состав числа 13 план-конспект урока по математике (2 класс) 117
Презентация для занятия на основе ИКТ Путешествие к вершине горы презентация к уроку по математике (подготовительная группа) Презентация для занятия на основе ИКТ Путешествие к вершине горы презентация к уроку по математике (подготовительная группа) 113
Математика М.И.Моро. УМК Школа России 1 класс. Устный счёт. презентация к уроку по математике (1 класс) Математика М.И.Моро. УМК Школа России 1 класс. Устный счёт. презентация к уроку по математике (1 класс) 149
МД Нумерация. Числа от 1 до 20. Часть 3 презентация к уроку по математике (1 класс) МД Нумерация. Числа от 1 до 20. Часть 3 презентация к уроку по математике (1 класс) 135
Все четыре действия презентация к уроку по математике (2 класс) Все четыре действия презентация к уроку по математике (2 класс) 116
презентация к уроку математики 3 класс презентация к уроку по математике (3 класс) презентация к уроку математики 3 класс презентация к уроку по математике (3 класс) 110
Умножение дробей Умножение дробей 118
Игра по математике - Второй тур Дроби Игра по математике - Второй тур Дроби 99
Социальные нормы. Миф - или реальная экономия Социальные нормы. Миф - или реальная экономия 100
Презентация Устный счет до 5 презентация урока для интерактивной доски по математике (средняя группа) Презентация Устный счет до 5 презентация урока для интерактивной доски по математике (средняя группа) 145
Проект урока по теме: Вычитание числа 5 проект по математике (1 класс) Проект урока по теме: Вычитание числа 5 проект по математике (1 класс) 44
Презентация по геометрии на тему Теорема Пифагора Презентация по геометрии на тему Теорема Пифагора 128
Совместная деятельность по позновательной мотивации дошкольного возраста : Сказочные приключения презентация к уроку по математике (средняя группа) Совместная деятельность по позновательной мотивации дошкольного возраста : Сказочные приключения презентация к уроку по математике (средняя группа) 132
Презентация к уроку: Действия с десятичными дробями. Урок обобщения и систематизации знаний в 5 классе. Презентация к уроку: Действия с десятичными дробями. Урок обобщения и систематизации знаний в 5 классе. 109
Презентация к уроку математики на тему: Действия с десятичными дробями. Презентация к уроку математики на тему: Действия с десятичными дробями. 117
Презентация к уроку математики в 4 классе презентация к уроку по математике (4 класс) по теме Презентация к уроку математики в 4 классе презентация к уроку по математике (4 класс) по теме 117
Координаты вектора Координаты вектора 98
Презентация Урок Математики Решение уравнений разными способами презентация урока для интерактивной доски по математике (4 класс) Презентация Урок Математики Решение уравнений разными способами презентация урока для интерактивной доски по математике (4 класс) 121
Урок-соревнование по теме: Умножение обыкновенных дробей Урок-соревнование по теме: Умножение обыкновенных дробей 144
Презентация: Краткое знакомство с космосом Презентация: Краткое знакомство с космосом 96
Учебно-методический комплект к уроку математики Поразрядное сложение единиц учебно-методический материал по математике (1 класс) Учебно-методический комплект к уроку математики Поразрядное сложение единиц учебно-методический материал по математике (1 класс) 112
Письменное умножение на двузначное число презентация к уроку по математике Письменное умножение на двузначное число презентация к уроку по математике 51
Урок изучения нового материала по математике в 5 классе по теме Доли Обыкновенные дроби Урок изучения нового материала по математике в 5 классе по теме Доли Обыкновенные дроби 99
Определение степени с натуральным показателем Определение степени с натуральным показателем 104
Сложение и вычитание десятичных дробей Сложение и вычитание десятичных дробей 84
Логарифмические неравенства Логарифмические неравенства 102
Урок математики по теме Порядок выполнения действий в выражениях. 3 класс. Программа Гармония методическая разработка по математике (3 класс) по теме Урок математики по теме Порядок выполнения действий в выражениях. 3 класс. Программа Гармония методическая разработка по математике (3 класс) по теме 114