Презентация, доклад по информатике на тему Машина Тьюринга

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

.

Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

исполнителя.
Универсальный исполнитель принято считать машиной.

формального исполнителя?
Ответ на этот вопрос получили ученые А. Тьюринг и Э. Пост.
Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное – имитировать вообще любого формального исполнителя.

свойства современной информационной системы: программное управление, память, и пошаговый способ действий. Эта воображаемая машина, получившая название «машины Тьюринга», используемая в теории автоматов или компьютеров позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.

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

Память об Алане Тьюринге Одна из ежегодных наград Ассоциации вычислительной техники называется
Премия Тьюринга,
в народе ее называют

нобелевская для программистов.

понятия алгоритма.

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

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

Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач.

в обе стороны ленты, разделенной на ячейки;
- каретки (читающей и записывающей головки)
- программируемого автомата.
Программируемый автомат управляет кареткой, посылая ей команды в соответствии с заложенной в него сменяемой программой. Лента выполняет роль внешней памяти компьютера, автомат — роль процессора, а каретка служит для ввода и вывода данных
 

какую букву он видит, а также в зависимости от своего состояния q автомат может выполнять следующие действия:
записать новую букву в обозреваемую ячейку;
выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
перейти в новое состояние.

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

Служит для записи исходных данных.

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

момент времени машина Тьюринга находится в одном из состояний q0, q1, …, qm

При этом: q1 - начальное состояние (машина начинает работу)
q0 - заключительное состояние (машина закончила работу)
Символы {<, >, .} – символы сдвига (вправо, влево, на месте)

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

ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н)
Перейти в новое состояние.

Указание о смене символа

Указание о сдвиге каретки

Указание о смене внутреннего состояния

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

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

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

управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита, а столбцы - состояниям автомата Q.
В начале работы МТ находится в состоянии q1. Состояние q0-это конечное состояние, попав в него, автомат заканчивает работу.

qj, находится команда, состоящая из трех частей · символ из алфавита A · направление перемещения: «>» (вправо), «<» (влево) или «.» (на месте) · новое состояние автомата

Функциональная схема

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

символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Решение задач

Решение

символы из алфавита в следующем порядке 00111*11***0. каретка находится над первым символом. Необходимо составить программу, которая заменит * на 1 и вернет каретку в первоначальное положение.

Решение задач

системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.

с наличием общих свойств: наличие атомарных носителей информации, наличие некоторого набора элементарных действий, работа на основе особой инструкции – программы.

Применение машины Тьюринга

№ 1-4


Творческое задание.
Выяснить, что такое «Тест Тьюринга»

понятно

Все получилось, урок удался