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

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

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

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

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

Презентация на тему Машины Тьюринга

Содержание

2. Машина Тьюринга – это конечный автомат, способный читать и писать на бесконечной ленте.
3. Машина Тьюринга состоит из:управляющего устройства, которое может
4. Устройства обращения к ленте, т.е. считывающей и
5. Данные машины Тьюринга – это слова в
6. Детерминированность:для любого внутреннего состояния qi и символа
7. Элементарные шаги машины – это считывание и
8. Стандартной начальной конфигурацией назовем конфигурацию вида q1α,
9. Пример 1. Пусть имеются команды:q2a5 → q3a4Rq3a1 → q4a2LТогда q2a5a1a2 → a4q3a1a2 → q4a4a2a2q2a5a1a2 → q4a4a2a2
10. Пример 2. Задана машина с алфавитом А={1, λ},
11. Пусть f – функция отображающая множество векторов
12. Если для функции f существует машина, которая
13. Пример 3.Алфавит А={1, *, λ}, состояния Q={q1,
14. Операции над машинами Тьюринга Теорема 1. Если функции
15. Определение: Машина Тьюринга Т вычисляет предикат P(α),
16. Определение. Говорят, что машина Т вычисляет предикат
17. Теорема 2. Если функции g1(α), g2(α) и
18. Универсальная машина Тьюринга Определение. Машина Тьюринга U,
19. Скачать презентацию
20. Похожие презентации

Машина Тьюринга – это конечный автомат, способный читать и писать на бесконечной ленте.

Машина Тьюринга состоит из:управляющего устройства, которое может находиться в одном из состояний,

Устройства обращения к ленте, т.е. считывающей и пишущей головки, которая в зависимости

Данные машины Тьюринга – это слова в алфавите ленты. Память машины Тьюринга –

Детерминированность:для любого внутреннего состояния qi и символа aj однозначно заданы:Следующее состояние

Элементарные шаги машины – это считывание и запись символов, сдвиг на ячейку

Стандартной начальной конфигурацией назовем конфигурацию вида q1α, т.е. конфигурацию, содержащую начальное состояние,

Пример 1. Пусть имеются команды:q2a5 → q3a4Rq3a1 → q4a2LТогда q2a5a1a2 → a4q3a1a2 → q4a4a2a2q2a5a1a2 → q4a4a2a2

Пример 2. Задана машина с алфавитом А={1, λ}, состояниями Q={q1, q2} и системой

Пусть f – функция отображающая множество векторов А* в себя. Машина Т

Если для функции f существует машина, которая ее вычисляет, то f называется

Пример 3.Алфавит А={1, *, λ}, состояния Q={q1, q2, q3, qz}, система команд:q1*

Операции над машинами Тьюринга Теорема 1. Если функции f1(x) и f2(y) вычислимы по

Определение: Машина Тьюринга Т вычисляет предикат P(α), если T(α)=ω, где ω=T, когда

Определение. Говорят, что машина Т вычисляет предикат P(α) c восстановлением, если Т(α)=ωα. Лемма.

Теорема 2. Если функции g1(α), g2(α) и предикат Р(α) вычислимы по Тьюрингу,

Универсальная машина Тьюринга Определение. Машина Тьюринга U, вычисляющая функцию от двух переменных

Теорема 4. Универсальная машина Тьюринга существует. Тезис Тьюринга. Всякий алгоритм может быть реализован

Слайды презентации

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

и писать на бесконечной ленте.

Слайд 3 Машина Тьюринга состоит из:
управляющего устройства, которое может находиться

Машина Тьюринга состоит из:управляющего устройства, которое может находиться в одном из

в одном из состояний, образующих конечное множество Q={q1, q2,

…, qn};
бесконечной ленты, разбитой на ячейки, в каждой из которых может быть задан один из символов конечного алфавита A={a1, a2, …, am};

Слайд 4 Устройства обращения к ленте, т.е. считывающей и пишущей

Устройства обращения к ленте, т.е. считывающей и пишущей головки, которая в

головки, которая в зависимости от символа в обозреваемой ячейке

и состояния управляющего устройства:
Записывает в ячейку символ;
Сдвигается на ячейку влево или вправо или остается на месте;
Переходит в новое состояние.

Слайд 5
Данные машины Тьюринга – это слова в алфавите

ленты.

Память машины Тьюринга – это конечное множество состояний (внутренняя

память) и лента (внешняя память)

Слайд 6 Детерминированность:
для любого внутреннего состояния qi и символа aj

однозначно заданы:
Следующее состояние ;
Символ ,

который нужно записать вместо ;
Направление сдвига головки: L(влево), R(вправо), Е(на месте).

Слайд 7 Элементарные шаги машины – это считывание и запись

Элементарные шаги машины – это считывание и запись символов, сдвиг на

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

переход управляющего устройства в следующее состояние.

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

Массовость машины Тьюринга – возможность выбора в качестве начальной системы любого слова в алфавите.

Слайд 8 Стандартной начальной конфигурацией назовем конфигурацию вида q1α, т.е.

Стандартной начальной конфигурацией назовем конфигурацию вида q1α, т.е. конфигурацию, содержащую начальное

конфигурацию, содержащую начальное состояние, в которой головка обозревает крайний

левый символ слова, написанного на ленте.

Стандартной заключительной конфигурацией назовем конфигурацию вида qzα.

Слайд 9 Пример 1.
Пусть имеются команды:
q2a5 → q3a4R
q3a1 →

q4a2L
Тогда q2a5a1a2 → a4q3a1a2 → q4a4a2a2

q2a5a1a2 → q4a4a2a2

Слайд 10 Пример 2.

Задана машина с алфавитом А={1, λ}, состояниями

Пример 2. Задана машина с алфавитом А={1, λ}, состояниями Q={q1, q2} и

Q={q1, q2} и системой команд
q11 → q11R,
q1λ→q11R

Слайд 11 Пусть f – функция отображающая множество векторов А*

Пусть f – функция отображающая множество векторов А* в себя. Машина

в себя. Машина Т вычисляет функцию f,если:
Для любых векторов

V и W, таких что f(V)=W, q1V*→qzW* , где V*, W* - правильные записи V и W;
Для любого вектора V, такого, что f(V) не определено, то машина Т, запущенная в стандартной начальной конфигурации q1V*, работает бесконечно.