Машина Тьюринга - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Машина Тьюринга. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Слайд 2

Описание слайда:

Машина Тьюринга — абстрактная вычислительная машина. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга — абстрактная вычислительная машина. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Слайд 3

Описание слайда:

Машина Тьюринга- расширение конечного автомата. Согласно тезису Чёрча — Тьюринга, она способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. Машина Тьюринга- расширение конечного автомата. Согласно тезису Чёрча — Тьюринга, она способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

Слайд 4

Описание слайда:

В состав машины Тьюринга входят: В состав машины Тьюринга входят: 1) Управляющее устройство (внутренняя память): Q={q1,q2,q3} 2)Бесконечная в обе стороны лента; 3)Устройство обращения к ленте(головка).

Слайд 5

Описание слайда:

Управляющее устройство – устройство, работающее согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Управляющее устройство – устройство, работающее согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине( в зависимости от текущего состояния и наблюдаемого в текущей клетке символа): 1. Записать в эту клетку новый символ, 2. Перейти в новое состояние и переместиться на одну клетку влево или вправо или остаться на месте.

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Среди состояний устройства управления выделяют начальное состояние q1 и заключительное состояние q0 .

Слайд 8

Описание слайда:

Бесконечная в обе стороны лента- лента, разделённая на ячейки, в каждую из которых записан символ алфавита(внешняя память). Бесконечная в обе стороны лента- лента, разделённая на ячейки, в каждую из которых записан символ алфавита(внешняя память). Возможны машины Тьюринга, которые имеют несколько бесконечных лент.

Слайд 9

Описание слайда:

Головка может: Головка может: перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

Слайд 10

Описание слайда:

Детерминированная машинаТьюринга- Детерминированная машинаТьюринга- это машина, у которой каждая комбинация состояния и символа на ленте в таблице имеет не более одного правила.

Слайд 11

Описание слайда:

Недетерминированная машина Тьюринга - это машина, каждая комбинация состояния и ленточного символа которой в таблице имеет 2 и более команд. Недетерминированная машина Тьюринга - это машина, каждая комбинация состояния и ленточного символа которой в таблице имеет 2 и более команд.

Слайд 12

Описание слайда:

1) Система команд; 2) Таблица(строки - состояния, столбцы - входные символы); 3)Блок-схема(диаграмма переходов).

Слайд 13

Описание слайда:

Полное состояние машины Тьюринга -это состояние, по которому можно однозначно определить дальнейшее поведение машины Тьюринга.

Слайд 14

Описание слайда:

Конфигурация( полное состояние машины Тьюринга): Конфигурация( полное состояние машины Тьюринга): Задается её внутреннее состояние, состояние ленты и положение головки на ленте α1 qi α2: α1 - слово на ленте, находящееся слева от головки; α2 - слово образованное символами справа от головки и начинающееся с символа, обозреваемого головкой; qi - текущее внутренне состояние.

Слайд 15

Описание слайда:

Стандартная начальная конфигурация - это конфигурация вида q1 α: - q1 - начальное состояние; -головка обозревает крайний левый символ на ленте слова α .

Слайд 16

Описание слайда:

Стандартная заключительная конфигурация - это конфигурация вида q0α: Стандартная заключительная конфигурация - это конфигурация вида q0α: - q0 -заключительное состояние, - головка обозревает крайний правый символ слова α на ленте.

Слайд 17

Описание слайда:

Ко всякой незаключительной конфигурации k применяется ровно одна команда, которая переводит машину Тьюринга в конфигурацию k‘:k→k'.

Слайд 18

Описание слайда:

Если между конфигурациями k1 и kn существует последовательность kj конфигураций, такая что k1→k2→...→kn, то можно записать k1→kn…

Слайд 19

Описание слайда:

Унарный код- это представление натуральных чисел в машине Тьюринга: для всех числовых функций Aисх={1}, A={1,*} число x представляется словом, состоящим из x единиц. Унарный код- это представление натуральных чисел в машине Тьюринга: для всех числовых функций Aисх={1}, A={1,*} число x представляется словом, состоящим из x единиц.

Слайд 20

Описание слайда:

Задача: Сложить два натуральных числа a и b (5+3) Дано: исходная лента « 11111*111» Найти: конечная лента «11111111» Решение: нач.сост.-q1 заключит.сост.-qz; Пусть головка в начальном положении обозревает крайний левый символ. Тогда машину Тьюринга, заданная с помощью команд, будет выглядеть так: q11→q2λR q21→q21R q2*→q31L q31→q31L q3λ→qzλR q1*→qzλR

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

Дано: Исходная лента «слово» Дано: Исходная лента «слово» Найти: Конечная лента «слово*слово» Слово представить в унарном коде Построить систему команд, диаграмму переходов. Решение: q11→q2λR q1*→qz*R q21→q21R q2λ→q3*R q2*→q5*R q3λ→q41L q4*→q4*L q41→q41L q4λ→q11R q51→q51R q4λ→q41L