Методическая разработка:  Открытый урок в 9 классе                            

Учитель информатики ГБОУ СОШ № 448 г. Москвы27.01.2016

Тема урока. Универсальный исполнитель:  машина Тьюринга

Цель урока.  Познакомить учащихся с исполнителем «Машина Тьюринга». Научить строить алгоритмы для машины Тьюринга.

Задачи урока.

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

Развивающие.  Развивать алгоритмическое мышление, способность к формализации, развивать системное мышление.

Воспитательные.  Развивать чувство ответственности за результаты своего труда.

Оборудование.  Каждый ученик обеспечен рабочим местом за персональным компьютером. Интерактивная доска. Презентация. На всех рабочих местах установлена программа Algo2000 – имитатор МТ.

Тип урока.  Комбинированный урок.

Форма урока.  Беседа. Сообщения учащихся

Практическая часть:  решение задач с использованием  программы Algo2000.

План урока.

1. Организационный момент.

2. Объяснение нового материала. Работа с презентацией.

• Вступление.
• Немного об изобретателе. Сообщения учащихся
• Основные определения.

• Принцип работы МТ.
•  Описание машины Тьюринга.
• Понятие о функциональной схеме машины Тьюринга.
•  Компьютерная реализация машины Тьюринга.
•  Примеры решения задач.

3. Закрепление нового материала. Работа в группах.

4. Решение задач. Работа в парах.

5. Домашнее задание.

6. Подведение итогов.

Ход урока.

1. Организационный момент.

• Актуализация знаний.

Опрос  учащихся.

– Что такое Исполнитель?

– Как вы думаете, что такое универсальный исполнитель?

(Исполнитель, который может делать все?)

«Изяществу зябко в этом суетном  свете»

Такую фразу сочинил  компьютер по одной из первых программ генерации  текстов  на естественных языках. Но эмоция, переданная этой фразой, конечно, недоступна компьютеру.

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

  Тема нашего урока  «Универсальный исполнитель».

Но это не исполнитель, который может выполнить все. Инженерам пока не удалось построить исполнителя, который может выполнить любую команду, ведь система команд исполнителя небезгранична. 

Все-таки, что такое универсальный исполнитель?

– Компьютерные игры  … Наверно, каждый, кто хоть однажды имел дело с компьютером, видел, а возможно и сам играл в какую-либо компьютерную игру. На экране одни объекты в виде живых существ или технических устройств подчиняются командам играющего, другие – управляются компьютером, который исполняет заданную программу. Все эти объекты – формальные исполнители, каждый со своим набором допустимых действий. Только объекты эти не реальные, а имитируемые компьютером. Получается, что с помощью одного формального исполнителя – компьютера – имитируются другие формальные исполнители – объекты компьютерной игры.

Говорят, что формальный исполнитель А имитирует другого формального исполнителя В, если:

• каждому объекту, которым управляет исполнитель В, однозначно соответствует объект,

которым управляет исполнитель А (имитация среды);

• каждому допустимому действию исполнителя В однозначно сопоставлено допустимое

действие исполнителя А (имитация действий);

• каждая инструкция исполнителя В, приводящая его к определенному результату,

соответствует  инструкции  для  исполнителя  А,  исполнение  которой  приводит  к соответствующему результату в среде исполнителя А.

Один из важнейших вопросов теоретической информатики звучит так: существует ли такой

формальный исполнитель, с помощью которого можно имитировать любого формального

исполнителя?

Ответ на данный вопрос положителен. Такого исполнителя естественно называть универсальным.

Универсального исполнителя принято называть машиной. Также принято давать машинам имена их

изобретателей. Универсального исполнителя, придуманного А.Тьюрингом, называют машиной Тьюринга

Тема нашего урока действительно «Универсальный исполнитель или формальный исполнитель».

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

Естественно считать, что сообщение записано на бесконечной ленте, разделенной на отдельные клетки, и в каждой клетке записан ровно 1 символ сообщения. Пустые клетки будем считать «пробелом» - а0 , Остальные символы будем обозначать а1 , а2 , а3 , … аn .  

Но это не исполнитель, который может выполнить все. Инженерам пока не удалось построить исполнителя, который может выполнить любую команду, ведь система команд исполнителя небезгранична.

Цели и задачи урока.

– Как вы думаете, какова цель нашего урока?

(Возможные ответы: Познакомиться с машиной Тьюринга, научиться управлять машиной Тьюринга)

2. Объяснение нового материала. Работа с презентацией (40 сладов).

a. Ключевые слова.

• Имитация одним формальным исполнителем другого формального исполнителя
•  Определение универсального исполнителя
• Понятие о машине Тьюринга
•  Описание машины Тьюринга
• Допустимые действия машины Тьюринга
•  Понятие о функциональной схеме машины Тьюринга
• Компьютерная реализация машины Тьюринга

 Вступление.

Характеризуя понятие алгоритма, отмечено, что предписание, задающее алгоритм, должно быть составлено таким образом, чтобы его исполнение было во всех деталях однозначно осуществимо и не требовало никаких свободно принимаемых решений. Другими словами, исполнитель алгоритма должен действовать согласно предписанию совершенно механически, «машинально», не вкладывая в свою работу никакой инициативы, изобретательности. Но что или кто может в наибольшей степени обладать таким свойством? Конечно же, машина.

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

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

Дадим описание машины Тьюринга. Потом покажем, каким образом ее можно определить как математическое понятие.

 Основные определения.

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

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

Во-вторых, машина Тьюринга снабжена потенциально бесконечной памятью. Что значит «потенциально бесконечная память»? Это значит, что хотя в каждый момент ее память хранит лишь конечное количество информации, однако для этого количества информации нет никакой верхней границы. Вообразим такую память машины Тьюринга в виде ленты, разделенной на клеточки — ячейки памяти, — которая может быть продолжена вправо сколько угодно (рис.).

В каждой ячейке может храниться только один знак из конечного множества знаков, называемого алфавитом машины Тьюринга, эти же знаки называются буквами алфавита. Ячейка может оказаться и пустой. Ради удобства договоримся: когда ячейка пустая, считать, что в ней хранится специальная буква алфавита, которую мы обозначим через s0 и назовем пустой буквой. Таким образом, в каждой ячейке ленты в любой данный момент находится одна и только одна буква алфавита А = {a0, a1, a2, ... ,ak}, причем только конечное число ячеек заполнено буквами из А, отличными от пустой буквы a0.

Машина Тьюринга снабжена (в нашем воображении) управляющей головкой, которая в каждый момент обозревает (воспринимает) лишь одну ячейку памяти и может изменить информацию, находящуюся в ней. Представить это можно следующим образом: если в какой-то момент букву в обозреваемой ячейке нужно заменить другой, то старая буква стирается и в ячейку вписывается новая (так же, как на магнитофонной ленте при новой записи автоматически стирается старая запись). Если эту операцию записать в общем виде «ai→aj», т. е. буква ai заменена буквой a j, то можно выделить следующие частные случаи:

а) i = j, т. е. буква в обозреваемой ячейке не изменилась;

б) i ≠ j – буква изменилась, при этом:

б1) если i = 0, то в пустую ячейку вписана буква aj, и aj, если j = 0, то стерта буква si в обозреваемой ячейке.

Управляющая головка за один такт работы машины может также передвинуться влево и воспринимать соседнюю слева ячейку (этот сдвиг головки будем обозначать через Л), управляющая головка может передвинуться вправо и воспринимать соседнюю справа ячейку (этот сдвиг мы обозначим через П), управляющая головка может остаться на месте и воспринимать ту же ячейку (этот «сдвиг» обозначим через Н). На рисунке изображен фрагмент ленты, а также управляющая головка. В обозреваемой ячейке хранится буква ai.

Рисунок 1

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

В каждой машине Тьюринга есть две части:

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

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

Тезис Тьюринга: Всякий алгоритм может быть задан посредством МТ.

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

c. Понятие о функциональной схеме машины Тьюринга.

Множество символов q i , обозначающие состояния машины Тьюринга называется внутренним алфавитом. Реакцию машины Тьюринга на символы, прочитанные читающей головкой, удобно представлять в виде таблицы, в которой строки таблицы помечены символами внешнего и внутреннего алфавитов соответственно. В клетки таблицы записываются команды.

Таблица 1

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

d.  Компьютерная реализация машины Тьюринга.

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

В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.

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

При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.

Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость. Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер 5 .

f. Примеры решения задач.

Пример 1. На ленте записана последовательность из некоторого количества одного и того же символа «*». Составить функциональную схему, которая заставляет машину Тьюринга увеличивать на одну количество звездочек в этой последовательности.

Учащимся демонстрируется работа имитатора АЛГО2000.

 Пример 2. Работа машины Тьюринга описана следующей функциональной схемой . Определите, какое сообщение будет на ленте, и укажите, напротивкакой ячейки в этот момент будет находиться ее пишущий блок.

3. 3. Закрепление нового материала. Работа в группах.

Учащиеся разбиваютcя на две группы, Каждая группа получает задание. В группе проходит обсуждение задач. По мере готовности решения, лидер группы выступает с решением.

Задание для  группы № 1

На ленте машины Тьюринга записана строка, состоящая из символов «*» и символов «#» (вперемежку без пробелов). Например:

Для решения какой задачи предназначена  функциональная схема:

Решение:

Данная функциональная схема заменяет символ «*» на символ «#», находящийся слева от символа  «#».

Дано:

 Получаем:

<Приложение 1>

Задание для  группы № 2.

Для решения какой задачи предназначена  функциональная схема:

Решение.

Данная функциональная схема заменяет символ «*» на символ «#».

Дано:

 Получаем:

5.Домашнее задание

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

Решение. 

Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так:

В этой машине Тьюринга q1 — состояние изменения цифры, q0 — состояние останова. Если в состоянии ql автомат видит цифру 0..8, то он заменяет ее на 1..9 соответственно и переходит в состояние q0, т.е. машина останавливается. Если же он видит цифру 9, то заменяет ее на 0, сдвигается влево, оставаясь в состоянии ql. Так продолжается до тех пор, пока автомат не встретит цифру меньше 9. Если же все цифры были равны 9, то он заменит их нулями, запишет 0 на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем перейдет в состояние q0, т.е. остановится.

Ссылки для просмотра фильмов

Учебные фильмы  http://www.youtube.com/watch?v=8jAu5Ts0oFg, http://www.youtube.com/watch?v=OPr_Ks4lvy0

6. Подведение итогов урока