Машина Тьюринга: модель алгоритма и выполнение программы
Цели и задачи
- Цель по SMART: к концу урока учащиеся смогут объяснить устройство машины Тьюринга и самостоятельно составить и пошагово выполнить программу машины для обработки простой цепочки символов, аргументируя назначение состояний, символов и переходов.
- Сформировать представление о машине Тьюринга как абстрактной математической модели алгоритма, включающей ленту, головку, множество состояний, алфавит и таблицу переходов.
- Научить читать таблицу переходов и применять её для пошагового моделирования работы машины на ленте.
- Развивать алгоритмическое, логическое и исследовательское мышление через поиск инвариантов, анализ остановки и обнаружение ошибок в программе.
- Показать связь темы с теорией алгоритмов, программированием и вопросами вычислимости, поддержать осознанный интерес к дальнейшему изучению информатики.
Планируемые результаты
Личностные
- Осознают значение абстрактных моделей для понимания принципов работы вычислительных систем.
- Проявляют интерес к исследовательским задачам, связанным с будущей профессиональной и учебной деятельностью.
- Понимают ценность точности, последовательности и проверки результата при разработке алгоритмов.
- Формируют ответственное отношение к аргументации собственного решения и конструктивному обсуждению ошибок.
Метапредметные
- Извлекают информацию из формального описания, таблицы переходов и последовательности конфигураций.
- Планируют исследование, выдвигают гипотезу о результате работы машины и проверяют её пошаговым моделированием.
- Сотрудничают в парах и группах, формулируют вопросы и аргументируют выбор переходов.
- Осуществляют самоконтроль по эталону, находят причину ошибки и корректируют алгоритм.
Предметные
- Знать назначение ленты, рабочего алфавита, пустого символа, головки, состояний и команды перехода.
- Уметь читать команду вида $(q_i,a)\to(q_j,b,D)$ и объяснять изменение конфигурации машины.
- Уметь выполнять трассировку программы машины Тьюринга на заданном входном слове.
- Уметь составлять простую таблицу переходов для записи символов или замены символов в цепочке.
- Понимать, что остановка, корректность результата и отсутствие бесконечного цикла являются свойствами алгоритма, которые необходимо проверять.
Универсальные учебные действия (УУД)
Личностные УУД
- Соотносят изучение машины Тьюринга с задачами будущего образования и профессии в области цифровых технологий.
- Осознают необходимость точного соблюдения правил формальной системы.
- Проявляют готовность принимать интеллектуальный вызов и доводить исследование до проверяемого вывода.
- Оценивают собственный вклад в парную работу и качество обоснования решения.
Регулятивные УУД
- Формулируют цель моделирования работы машины и составляют последовательность действий.
- Прогнозируют результат до начала трассировки.
- Сверяют каждую конфигурацию с таблицей переходов и исправляют найденные ошибки.
- Оценивают достижение цели по критериям правильности, полноты и объяснимости решения.
Познавательные УУД
- Выделяют существенные элементы формальной модели и отделяют их от второстепенных деталей.
- Преобразуют таблицу переходов в последовательность конфигураций.
- Устанавливают причинно-следственную связь между командой и изменением ленты, состояния или положения головки.
- Моделируют работу алгоритма и анализируют условие его остановки.
Коммуникативные УУД
- Распределяют роли наблюдателя, оператора и проверяющего в парной работе.
- Задают уточняющие вопросы о направлении движения и условии остановки.
- Объясняют партнёру каждую команду без пропуска промежуточных шагов.
- Корректно сопоставляют разные решения и аргументируют выбор более надёжного алгоритма.
Подготовка учителя к уроку
- Подготовить презентацию или интерактивную доску со схемой машины: бесконечная лента, головка, текущее состояние и направление движения.
- Вывести на доску памятку: команда $(q_i,a)\to(q_j,b,D)$ означает «прочитать, записать, изменить состояние, сдвинуться».
- Распечатать по одной карточке на каждого ученика с мини-определениями и двумя командами для быстрой проверки понимания.
- Распечатать по одной рабочей карте на пару: лента с клетками, входное слово, таблица переходов и поля для конфигураций.
- Подготовить три варианта исследовательских карточек: базовую, повышенную и творческую; по одной карточке каждого варианта на пару.
- Подготовить эталон трассировки на отдельном листе для самопроверки и лист наблюдения с критериями: корректность шага, результат, остановка.
- Подготовить маркеры трёх цветов или магнитные карточки для обозначения головки, состояния и записанного символа.
- Оборудование: компьютер учителя, проектор или интерактивная доска, таймер, доска и маркеры.
- На доске заранее оставить место для проблемного вопроса: «Может ли простая машина выполнить любой алгоритм?»
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в исследовательскую деятельность и обозначить проблемный вопрос урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране длинную ленту из клеток с символами 0 и 1. «Представьте, что перед нами очень простой исполнитель. Он умеет читать один символ, стирать или записывать символ, двигаться только влево или вправо и менять внутреннее состояние. Как вы думаете, достаточно ли такого набора действий, чтобы описать сложный алгоритм?» | Рассматривают схему, формулируют первые гипотезы: «Нужно много команд», «Возможно, если машина умеет повторять действия», «Одних команд может быть недостаточно без памяти». |
2 мин | Учитель записывает проблемный вопрос и добавляет: «Сегодня мы не будем просто запоминать устройство машины. Мы попробуем сами заставить её выполнить программу, а затем проверим, какие свойства алгоритма можно увидеть в такой модели. В конце вернёмся к вопросу и дадим аргументированный ответ». | Записывают тему и проблемный вопрос, формулируют личную цель: «Научиться читать команды», «Понять, как машина обрабатывает слово», «Составить простую программу». |
Завершение этапа: учитель подводит итог: «Мы увидели, что перед нами не обычный компьютер, а предельно строгая модель исполнителя. Чтобы понять её возможности, сначала восстановим язык, на котором описываются отдельные шаги.»
Этап 2. Актуализация знаний (5 мин)
Цель этапа: актуализировать понятия алгоритма, исполнителя, состояния и трассировки.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит приём «Подумай — обсуди в паре — поделись». «Вспомните, что обязательно должно быть задано для исполнителя алгоритма. Подумайте молча 30 секунд, затем обсудите ответ с соседом. Нас интересуют не примеры программ, а свойства самого описания». | Индивидуально выделяют понятия «система команд», «начальное состояние», «условие остановки», затем сравнивают формулировки в парах и предлагают ответы классу. |
3 мин | Учитель показывает короткую последовательность команд условного исполнителя и спрашивает: «Что называют состоянием? Зачем нужна трассировка? Почему нельзя проверить только конечный ответ? Какие ошибки обнаруживаются при записи промежуточных шагов?» Учитель фиксирует на доске слова «команда», «состояние», «трассировка», «проверка». | Отвечают: «Состояние описывает текущую ситуацию исполнителя», «Трассировка показывает ход выполнения», «По промежуточным шагам можно найти место ошибки». Заполняют мини-схему в рабочей карте. |
Завершение этапа: учитель подводит итог: «Мы вспомнили, что алгоритм задаёт точные действия исполнителя и должен быть проверяемым. Теперь найдём, как эти идеи реализуются в машине Тьюринга и где именно возникает затруднение.»
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить необходимость формального описания машины и совместно сформулировать план исследования.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предъявляет конфигурацию: на ленте записано 101, головка стоит над первой клеткой, машина находится в состоянии $q_0$. «Нам нужно заменить каждый символ 1 на 0 и остановиться после последнего символа. Каких сведений не хватает, чтобы исполнитель не угадывал наши намерения?» | Называют недостающие элементы: «Что делать с прочитанным символом», «Куда двигаться», «Как понять, что работа закончена», «Какое состояние считать текущим». |
2 мин | Учитель уточняет: «Сформулируйте план. Какие объекты мы должны определить, затем что сделать с программой и как проверить результат?» На доске появляется план: определить устройство; прочитать команду; выполнить трассировку; составить или исправить программу; проверить остановку. | Формулируют цель урока и записывают план: «Определить элементы машины, научиться читать переходы, выполнить программу, проверить результат и остановку». |
Завершение этапа: учитель подводит итог: «Мы выяснили, что одной идеи движения по ленте недостаточно: каждое действие должно быть формально задано. Переходим к модели и разберём одну команду настолько подробно, чтобы затем вы смогли работать без моей подсказки.»
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Этап 4. Открытие нового знания (10 мин)
Цель этапа: сформировать представление об элементах машины Тьюринга и научить читать таблицу переходов.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель показывает схему и объясняет: «Машина Тьюринга состоит из ленты, разделённой на клетки, головки, которая читает и записывает символы, конечного набора состояний и правил перехода. В каждой клетке ленты находится символ рабочего алфавита; пустой символ обозначим $\square$. Команда имеет вид $(q_i,a)\to(q_j,b,D)$: в состоянии $q_i$, прочитав $a$, машина записывает $b$, переходит в $q_j$ и сдвигает головку в направлении $D$, где $D$ — L или R. Важно: порядок действий фиксирован и не зависит от догадки исполнителя». | Подписывают элементы схемы: лента, головка, состояние, символ, направление. Вслух расшифровывают команду $(q_0,1)\to(q_1,0,R)$: «В состоянии $q_0$ прочитать 1, записать 0, перейти в $q_1$ и сдвинуться вправо». |
3 мин | Учитель записывает таблицу переходов для замены единиц нулями: «Для состояния $q_0$ и символа 1 используем команду $(q_0,1)\to(q_0,0,R)$. Для пустого символа используем $(q_0,\square)\to(q_f,\square,S)$, где $q_f$ — конечное состояние, а $S$ означает остановку. Посмотрим, почему состояние сохраняется при чтении 1 и меняется только на пустом символе». | Объясняют назначение правил: при 1 машина продолжает движение, при пустой клетке останавливается. Предсказывают результат для слова 101: «000». Отмечают в карте, какое правило срабатывает на каждом типе символа. |
3 мин | Учитель проводит мини-исследование «Найди ошибку»: «Вариант программы содержит правило $(q_0,1)\to(q_0,0,L)$. Что изменится? Почему машина не пройдёт слово слева направо? Сравните направления в двух правилах и сформулируйте критерий корректности для нашей задачи». | Анализируют правило, отвечают: «Головка будет уходить влево, поэтому слово не будет обработано слева направо». Формулируют критерий: «Для просмотра всех символов справа от начала нужен сдвиг вправо после обработки каждого символа». |
Запись в тетрадях
Записывают: «Машина Тьюринга — абстрактный исполнитель с лентой, головкой, состояниями и правилами переходов. Команда $(q_i,a)\to(q_j,b,D)$ означает: прочитать $a$, записать $b$, перейти в $q_j$, сдвинуться в направлении $D$.» Отдельно фиксируют обозначения $L$, $R$, $S$ и конечное состояние $q_f$.
Завершение этапа: учитель подводит итог: «Теперь у нас есть язык описания машины и критерий чтения команды. Следующий шаг — не просто повторить объяснение, а самим выполнить программу по клеткам и убедиться, что каждый переход меняет конфигурацию предсказуемо.»
Этап 5. Первичное закрепление: трассировка (7 мин)
Цель этапа: научить учащихся пошагово выполнять программу машины Тьюринга и фиксировать конфигурации.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт рабочие карты и говорит: «Работаем в парах. Один ученик — оператор, второй — проверяющий; через один шаг роли меняются. На ленте записано 101, головка стоит над первой цифрой, начальное состояние $q_0$. Используйте правила $(q_0,1)\to(q_0,0,R)$ и $(q_0,\square)\to(q_f,\square,S)$. После каждого шага записывайте состояние, содержимое ленты и положение головки». | Распределяют роли, обозначают головку стрелкой, выполняют первый переход и записывают конфигурацию: лента 001, состояние $q_0$, головка над второй клеткой. |
3 мин | Учитель останавливает работу после второго шага и спрашивает: «Какой символ теперь прочитан? Какую команду выбираем? Не перепрыгивайте через промежуточную конфигурацию». Учитель показывает на доске шаблон записи и проверяет две пары. | Продолжают трассировку: после обработки второй клетки получают 000, головка перемещается к третьей цифре; после обработки третьей — головка попадает на пустой символ. |
2 мин | Учитель просит пары сравнить последние записи: «Назовите условие остановки и итоговую ленту. Если результат отличается, найдите первую конфигурацию, в которой появились разные записи». | Сверяют ответы, находят расхождения по первой ошибочной конфигурации, формулируют вывод: «Машина останавливается при чтении пустого символа и выдаёт 000». |
Эталон решения
Начальная конфигурация: $q_0:101$. После первого шага читается 1, записывается 0, головка сдвигается вправо: $0q_0:01$. После второго шага: $00q_0:1$. После третьего шага: $000q_0:\square$. При чтении пустого символа срабатывает $(q_0,\square)\to(q_f,\square,S)$, поэтому машина останавливается. Результат на ленте: $000$.
Завершение этапа: учитель подводит итог: «Мы увидели, что трассировка — это доказательство того, как именно машина получает результат. Сейчас каждый проверит себя индивидуально и попробует не только выполнить готовую программу, но и проанализировать её качество.»
Этап 6. Самостоятельная исследовательская работа с самопроверкой (10 мин)
Цель этапа: применить модель при решении задач разного уровня и проверить корректность собственного алгоритмического рассуждения.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель объясняет дифференциацию: «Выберите уровень, на котором сможете дать полное обоснование. Базовый вариант требует трассировки, повышенный — составления программы, продвинутый — анализа остановки. Критерии одинаковы: каждый переход записан, результат объяснён, условие остановки названо». | Выбирают карточку, записывают номер уровня и индивидуально читают условие. |
4 мин | Учитель предлагает задания. Базовый: выполнить программу замены всех 0 на 1 для входа 010. Повышенный: составить таблицу переходов, которая стирает все символы слова 110, двигаясь слева направо, и останавливается на пустом символе. Продвинутый: объяснить, почему программа с правилом $(q_0,1)\to(q_0,1,R)$ и отсутствующим переходом для $\square$ не является завершённым алгоритмом. | Решают выбранное задание, записывают таблицу или последовательность конфигураций, подчёркивают момент остановки либо указывают, почему он не задан. |
2 мин | Учитель предлагает взаимопроверку по алгоритму «Две звезды и пожелание»: «Отметьте два корректных элемента решения и один вопрос или риск ошибки. Не ставьте оценку без объяснения». | Обмениваются работами, отмечают правильные переходы и формулируют конкретное замечание, например: «Не указано положение головки» или «Не задано действие на пустом символе». |
2 мин | Учитель выводит эталон для базового задания и критерии проверки. «Сравните не только конечное слово, но и первый шаг. Если решение отличается, восстановите правило, которое было применено». | Самостоятельно исправляют работу, фиксируют результат: для входа 010 после замены нулей получается 111; называют недостающий переход как причину незавершённости продвинутой программы. |
Эталон решения
Для базового задания программа содержит $(q_0,0)\to(q_0,1,R)$ и $(q_0,1)\to(q_0,1,R)$, а на пустом символе — $(q_0,\square)\to(q_f,\square,S)$. Трассировка входа 010: после первого шага 110, после второго 111, после третьего 111, затем при чтении $\square$ машина переходит в $q_f$ и останавливается. Для продвинутой программы отсутствие перехода для $\square$ означает, что поведение машины в этой конфигурации не определено; утверждать остановку нельзя.
Завершение этапа: учитель подводит итог: «Самостоятельная работа показала, что программа — это не только набор удачных команд. Она должна описывать поведение на каждом встречающемся символе и иметь понятное условие остановки. В финале обобщим, что именно мы открыли и какие вопросы остаются для дальнейшего исследования.»
Этап 7. Рефлексия и домашнее задание (6 мин)
Цель этапа: обобщить новое знание, оценить степень достижения цели и определить направление дальнейшей работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит приём «Одноминутная бумага»: «За одну минуту завершите три фразы: “Машина Тьюринга состоит из…”, “Команда перехода задаёт…”, “При трассировке особенно важно…”» | Письменно завершают фразы: «ленты, головки и состояний», «чтение, запись, переход и движение», «фиксировать каждую конфигурацию и проверять остановку». |
2 мин | Учитель возвращается к проблемному вопросу: «Может ли простая машина выполнить любой алгоритм? Сегодня мы не доказываем общий тезис, но какую роль играет модель?» Учитель предлагает сигнал «светофор»: зелёный — могу выполнить трассировку, жёлтый — нужна тренировка, красный — не понимаю выбор перехода. | Поднимают карточку выбранного цвета и устно аргументируют позицию. Формулируют вывод: «Машина Тьюринга позволяет формально описывать алгоритмы через простые повторяющиеся шаги». |
2 мин | Учитель сообщает домашнее задание и контрольные вопросы: «Перед выходом ответьте: что произойдёт, если не задан переход для прочитанного символа? Чем состояние отличается от символа на ленте? Как доказать, что машина остановилась?» | Записывают домашнее задание, отвечают на контрольные вопросы: «Поведение не определено», «Состояние относится к управлению, символ — к ленте», «Нужно показать конечный переход в состояние остановки». |
Критерии оценивания практической работы
- «5» — полностью и без ошибок выполнена трассировка или составлена таблица переходов; корректно указаны все конфигурации, итог ленты и условие остановки; объяснение содержит причинную связь между каждой командой и изменением машины.
- «4» — решение в целом верно, но допущена одна неточность в записи положения головки, состояния или промежуточной конфигурации, не повлиявшая на общий результат; ошибка исправлена при самопроверке.
- «3» — верно определены основные элементы машины и выполнена не менее половины переходов, но отсутствует полная трассировка, допущены две и более ошибки или не обосновано условие остановки.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какие элементы машины Тьюринга необходимы для выполнения одной команды? | Проверка осознания структуры формальной модели. |
Какой шаг трассировки оказался самым трудным и почему? | Выявление точек затруднения: чтение перехода, движение головки или фиксация конфигурации. |
Как вы доказали, что программа остановилась? | Проверка понимания роли конечного состояния и условия остановки. |
Где эта модель может быть полезна при изучении программирования и алгоритмов? | Связывание абстрактного знания с будущей учебной и профессиональной деятельностью. |
Завершающее слово учителя
«Сегодня мы увидели, как из очень простых действий — прочитать, записать, сдвинуться и изменить состояние — строится строгая модель алгоритма. Самая частая ошибка при работе с машиной Тьюринга — пропуск промежуточной конфигурации или отсутствие правила для символа, который машина реально прочитает. Поэтому любой алгоритм нужно не только придумать, но и проверить трассировкой. На следующем уроке мы усложним задачи и исследуем алгоритмы, которые обрабатывают структуру слова, а также обсудим, почему некоторые процессы могут быть неразрешимыми.»
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Выполнить трассировку машины, которая заменяет каждый символ 1 на 0 и каждый символ 0 на 1, для двух входных слов длиной 4–5 символов; записать все конфигурации и конечный результат. | Закрепляет чтение команд и аккуратную фиксацию положения головки; при проверке смотреть на полноту трассировки и правильность результата. |
Средний (повышающий) | Составить таблицу переходов для машины, которая проходит слово из символов 0 и 1 слева направо, стирает его и останавливается на первом пустом символе; проверить программу на двух разных словах. | Развивает умение проектировать алгоритм; при проверке смотреть, задано ли действие для каждого символа и корректно ли оформлен переход в конечное состояние. |
Продвинутый (дополнительный) | Предложить и обосновать машину, которая определяет, содержит ли входное слово хотя бы один символ 1: при обнаружении 1 останавливается в состоянии «да», при достижении пустого символа — в состоянии «нет». Привести трассировку для двух противоположных случаев. | Развивает создание и анализ алгоритма, работу с несколькими конечными состояниями и аргументацию корректности; при проверке смотреть на полноту случаев и доказательство остановки. |
Контрольные вопросы перед выходом из класса: «Что обозначает тройка действий в команде машины? Как определить следующий переход? Почему конечный результат без трассировки не всегда доказывает корректность? Какой элемент программы отвечает за остановку?»
