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

(23.06.1912 – 7.06.1954)
— английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики.

.

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

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

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

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

1. прибавь 3
2. умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

ОТВЕТ: 2 2 1 1 1

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

Машина Тьюринга

для считывания/записи, управляемая программой).
3) Алфавит (состояний и внешний)

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

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

к этому числу 1. Автомат обозревает некую цифру входного числа

1

2

5

Q0 – поиск последней цифры числа
Q1 – изменение значения последней цифры на 1

6

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

N>1. Разработать алгоритм МТ, которая уменьшала бы заданное число N на 1. Автомат обозревает правую цифру числа.

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

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

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

алгоритм машины Тьюринга, который бы умножил заданное число на 2

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

понятно

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

Изображение Калькулятор:
https://encrypted-tbn1.gstatic.com/images?q=tbn:ANd9GcS0169cTfiZCK_rtf6N8p0KWvykp9gyYcor0ksSUctVJ9C8JL00Cg

ALGO2000
http://www.fayloobmennik.net/1492236 Чепкунова Е.Г.
9. Чепкунова Е.Г.«Основы теории кодирования информации и теории алгоритмов» Казань – 2009, 60с.

Источники