10 класс Тема урока: Машина Тьюринга. Выполнила учитель информатики МАОУ «Гимназия 37» г.Казани Хуснутдинова Р.Р.

1. Историческая справка Историческая справка 2. Разминка Разминка 3. Машина Тьюринга Машина Тьюринга 4. Решение задач Решение задач 5. Применение машины Тьюринга Применение машины Тьюринга 6. Домашнее задание Домашнее задание

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

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

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

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

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

Бескон. лента Алфавит состояний запускALGO2000

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

Дискретность Понятность Детерминированность Результативность. Массовость.

Задача 1 На ленте МТ находится десятичное число. Прибавить к этому числу 1. Автомат обозревает некую цифру входного числа 125 Q0 – поиск последней цифры числа Q1 – изменение значения последней цифры на 1 6

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

Для лучшего понимания термина «алгоритм» Для понимания принципов работы ЭВМ, в связи с наличием общих свойств: наличие атомарных носителей информации, наличие некоторого набора элементарных действий, работа на основе особой инструкции – программы.

1. Задача На ленте МТ находится натуральное число N. Разработать алгоритм машины Тьюринга, который бы умножил заданное число на 2 2. Творческое задание. Выяснить, что такое «Тест Тьюринга»

Оцените свою работу на уроке: На уроке было скучно и ничего не понятно Все получилось, урок удался

1. Шаблон презентации dlya-oformleniya-prezentatsiy-ms-powerpoint-po Портреты Тьюринга: a) Turing.jpghttp:// Turing.jpg b) ru.yandex.net/i?id=885138e8d9dc781a85e426c1e8b829dd &n=21http://im0-tub- ru.yandex.net/i?id=885138e8d9dc781a85e426c1e8b829dd &n=21 3. Машина Тьюринга: 4. Биография Тьюринга: 5. Изображение Калькулятор: tbn1.gstatic.com/images?q=tbn:ANd9GcS0169cTfiZCK_rtf6N8p 0KWvykp9gyYcor0ksSUctVJ9C8JL00Cg

6. Изображение на слайде 15: 7. Изображение компьютера а) tbn3.gstatic.com/images?q=tbn:ANd9GcRYN3sVlt5OlGzmrN x2ZSycg5lV4tCqzZPM1IOORKD9LerZBBZEJghttps://encrypted- tbn3.gstatic.com/images?q=tbn:ANd9GcRYN3sVlt5OlGzmrN x2ZSycg5lV4tCqzZPM1IOORKD9LerZBBZEJg б) tbn3.gstatic.com/images?q=tbn:ANd9GcSu8kUcHo_zaLwn6d arXiFMbAH5MfDf-7jxiW8UR0_DfOaxir1t2Ahttps://encrypted- tbn3.gstatic.com/images?q=tbn:ANd9GcSu8kUcHo_zaLwn6d arXiFMbAH5MfDf-7jxiW8UR0_DfOaxir1t2A 8. ALGO Чепкунова Е.Г. 9. Чепкунова Е.Г.«Основы теории кодирования информации и теории алгоритмов» Казань – 2009, 60 с.