Презентация Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 69 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Математика » Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:69 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.59 MB
- Просмотров:96
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№10 слайд
Содержание слайда: Структура алгоритма (составляющие алгоритма)
Процессорная структура. (Исполнитель алгоритма).
Во всех теоретических конструкциях алгоритмов и большинстве алгоритмических языках это единственный процессор.
Структуры данных. Структура данных это способ организация записи, хранения и извлечение данных.
Данные – это элементы множеств, которые нужно порождать или распознавать..
№11 слайд
Содержание слайда: Составляющие структуры
Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования функции от функций из базовых.
Логическая структура алгоритма (ЛСА) или программы (ЛСП). ЛСА суть описание организации вычислительного процесса, который управляется состоянием памяти.
№12 слайд
Содержание слайда: Интерпретация МТ.
Процессор – в МТ называется управляющей головкой (УГ).
Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ
Процесс вычислений происходит по тактам
Процесс остановки (остановка) МТ.
Замечание Список правил для МТ не упорядочен
№13 слайд
Содержание слайда: МТ
Тьюринг назвал свое абстрактное механическое устройство "универсальной машиной", поскольку она должна была справляться с любой допустимой, то есть теоретически разрешимой задачей — математической или логической.
Данные должны были вводиться в машину на бумажной ленте, поделенной на клетки — ячейки.
Каждая такая ячейка либо содержала символ, либо была пустой.
Машина могла не только обрабатывать записанные на ленте символы, но и изменять их, стирая старые и записывая новые в соответствии с инструкциями, хранимыми в ее внутренней памяти.
№20 слайд
Содержание слайда: Головка неподвижна, а лента передвигается относительно нее вправо или влево.
Головка неподвижна, а лента передвигается относительно нее вправо или влево.
Машина работает в некотором произвольном конечном алфавите
A = {ε a1…a n} – этот алфавит называется внешним.
В нем выделяется специальный символ – ε, называемый пустым – его посылка в какую-либо ячейку стирает тот символ, который до этого там находился, и оставляет ячейку пустой.
№21 слайд
Содержание слайда: В каждую ячейку ленты может быть записан лишь один символ.
В каждую ячейку ленты может быть записан лишь один символ.
Информация, хранящаяся на ленте, изображается конечной последовательностью символов внешнего алфавита, отличных от пустого символа.
Головка всегда расположена над одной из ячеек ленты.
Работа происходит тактами (шагами).
№22 слайд
Содержание слайда: Система исполняемых головкой команд предельно проста:
Система исполняемых головкой команд предельно проста:
на каждом такте она производит замену символа в обозреваемой ячейке ai символом aj
При этом возможны сочетания:
j = i – это означает, что в обозреваемой ячейке символ не изменился;
i_0, j = 0 означает, что хранившийся в ячейке символ заменяется пустым, т.е. стирается;
i =0, j_ 0 означает, что пустой символ заменяется непустым (с номером j в алфавите), т.е. производится вставка символа;
i j_ 0 соответствует замене одного символа другим.
№24 слайд
Содержание слайда: Элементарный шаг (такт) работы машины Тьюринга
головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние
№25 слайд
Содержание слайда: Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и положение головки
Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и положение головки
В зависимости от начальной конфигурации возможны два варианта :
после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;
остановки не происходит.
В первом случае говорят, что данная машина применима к начальной информации, во втором – нет.
№26 слайд
Содержание слайда: Пример
Пусть начальной является конфигурация 1q11111.
Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11q111.
Такт 2 – аналогичным образом осуществляется переход к конфигурации 111q11.
Такт 3 – переход к конфигурации 1111q1.
Такт 4 –переход к конфигурации 11111q
Такт 5 Обозревается , в ЛУ состояние q. Выходная команда z1S – вместо в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация 111111z.
Задача решена.
№31 слайд
Содержание слайда: Представление машины Тьюринга совокупностью команд
Совокупность всех команд, которые может выполнять машина, называется ее программой. Машина Тьюринга считается заданной, если заданы ее внешний и внутренний алфавиты, программа, начальная конфигурация и указано, какие из символов обозначают пустую ячейку и заключительное состояние.
Чтобы записать совокупность команд, нужно воспользоваться следующими правилами:
1) начальному шагу алгоритма ставится в соответствие q 0 - начальное состояние;
2) циклы реализуются так, что последнее действие цикла должно соответствовать переходу в то состояние, которое соответствует началу цикла;
3) соседним шагам алгоритма соответствует переход в смежные состояния, которые соответствуют этим пунктам;
4) последний шаг алгоритма вызывает переход в заключительное состояние.
№33 слайд
Содержание слайда: Представление машины Тьюринга графом
При представлении машины Тьюринга посредством графа необходимо каждому состоянию поставить в соответствие вершину графа, а каждой команде - помеченную дугу. Машина Тьюринга из рассмотренного примера инвертирования цепочки, состоящей из символов 0 и 1, будет представлена в виде графа следующим образом:
№36 слайд
Содержание слайда: Пример 1.
Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =x+1 по правилам двоичного сложения.
Решение. Исходя из формулировки задачи, требующей вычислить функцию по правилам сложения в двоичной системе сложения, выберем входной алфавит: А ={0, 1, ε}.
Представим машины Тьюринга таблицей соответствия и графом. Таблица соответствия:
№39 слайд
Содержание слайда: Построение МТ
Для того чтобы доказать вычислимость функции, а в дальнейшем и существование алгоритма необходимо построить машину Тьюринга, реализация которой на практике зачастую представляет собой трудоемкую задачу. В связи с этим возникает необходимость
разбиения алгоритма на отдельные задачи, каждая из которых будет решаться отдельной машиной Тьюринга. Если объединить программы этих машин, то получится новая программа, позволяющая решить исходную задачу.
№40 слайд
Содержание слайда: Операции над машинами Тьюринга
1. Композиция машин Тьюринга. Пусть машины Т1 и Т2 имеют программы Р1 и Р2.
Предположим, что внутренние алфавиты этих машин не пересекаются; пусть qz1 - заключительное состояние машины Т1, а q02 - начальное состояние машины Т2. Заменим всюду в программе Р1 заключительное состояние qz1 на начальное состояние q02 машины Т2 и полученную программу объединим с программой Р2. Новая программа Р определяет машину Т, называемую композицией машин Т1 и Т2 по паре состояний (qz1, q02).
Композиция машин может быть обозначена Т1 ⋅Т2 или Т1Т2. Более подробно композиция машин записывается следующим образом:
Т = Т(Т1, Т2, (qz1, q02)), где
T1 = (Q1, A1, δ1, p01, pz1, a01, a11),
Т2= (Q2, A2, δ2, p02, pz2, a02, a12).
№43 слайд
Содержание слайда: Алгоритмическая машина Поста
(МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм»
Абстрактная машина Поста состоит
из бесконечной ленты, разделенной на равные секции,
считывающе-записывающей головки.
Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена – т.е. в нее записана метка).
Состояние ленты и информация о положении головки характеризуют состояние машины Поста.
№44 слайд
Содержание слайда: За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку.
За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку.
Работа машины Поста заключает в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд.
№49 слайд
Содержание слайда: Комментарий к примеру
Последовательное исполнение команд 1 и 2 приводит к тому, что головка за два такта работы машины сдвигается на одну позицию вправо.
Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустая ячейка – тогда по команде 3 в нее будет поставлена метка
и по команде 4 машина остановится
№50 слайд
Содержание слайда: Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата.
Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата.
В отличие от этой ситуации, остановка по команде
<x стоп> является результативной, т.е. она происходит после того, как результат действия алгоритма получен.
Кроме того, возможна ситуация, когда машина не останавливается никогда – это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.
№56 слайд
Содержание слайда: Рекурсивные функции
Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г.
Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий.
№58 слайд
Содержание слайда: Рекурсивные функции
Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция числового аргумента, которая в своей записи содержит себя же. Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
№59 слайд
Содержание слайда: Свойства рекурсивных алгоритмов:
Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя.
Для этого он обязательно должен содержать нерекурсивный выход, т.е. при некоторых исходных данных вычисления в алгоритме должны производиться без вызовов его самого - тривиальный случай.
Определение сложного случая в терминах более простого.
При любых исходных данных нерекурсивный выход должен достигаться за конечное число рекурсивных вызовов. Для этого каждый новый вызов рекурсивного алгоритма должен решать более простую задачу, т.е. рекурсивный алгоритм должен содержать определение некоторого сложного случая в терминах более простого случая.
№60 слайд
Содержание слайда: Примитивная рекурсия
Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную функцию f по двум заданным функциям, одна из которых является n- местной функцией g, а другая (n+2) - местной функцией h.
Функция f(x1, x2, ..., xn, y) получается оператором примитивной рекурсии из функции g(x1, x2, ..., xn) и функции h(x1, x2, ..., xn, y, z), по схеме:
f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);
f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)).
Независимо от числа переменных в f рекурсия ведется только по одной переменной у. Остальные n переменных x1, x2, ..., xn на момент применения схемы зафиксированы и играют роль параметров.
№63 слайд
Содержание слайда: Исчисления.
Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г.
-исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г.
Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г.
№65 слайд
Содержание слайда: Метапрограммирование
Метапрограммирование предусматривает написание программ, которые работают с другими программами в качестве данных. Язык обрабатывающей программы называется метаязыком, язык обрабатываемой — объектным языком. Простейшим примером метапрограмми-рования является любой компилятор, преобразующий код, написанный на языке высокого уровня, в низкоуровневый машинный язык или ассемблер.
Скачать все slide презентации Машина Тьюринга. Теория алгоритмов, формальных языков, грамматик и автоматов одним архивом:
-
Алгоритмически неразрешимые проблемы. Машина Тьюринга
-
Алгоритмы теории игр
-
Алгебра высказываний. Формальные теории. Предикаты. Модуль 5
-
Теория алгоритмов
-
Алгебра высказываний. Логика и теория алгоритмов
-
Математическая логика и теория алгоритмов
-
Основы дискретной математики и теории алгоритмов. Основные понятия теории множеств. Тема 1
-
Формальные логические теории. Исчисление предикатов
-
Формальные логические теории
-
Теория сложности алгоритмов