Тема урока «МАШИНА ТЬЮРИНГА».

Представленная тема занятия «Машина Тьюринга» входит в состав главы "Алгоритмы обработки информации"  в рамках предмета информатики в 10 классе на профильном уровне.

Тип урока урок изучения и первичного закрепления новых знаний

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

Задачи урока

Образовательные:

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

·         формировать у будущих специалистов теоретическую базу практического применения теории алгоритмов при программировании.

Развивающие:

·         развитие алгоритмического мышления, способностей к формализации, элементов системного мышления;

Воспитательные:

• формировать культуру познавательной деятельности;
• формировать культуру коллективной деятельности, воспитывать чувство ответственности за результаты своего труда, используемые другими людьми;

План урока:

ТЕМА «Машина Тьюринга»

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

2.      Вступление.

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

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

5.      Задачи.

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

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

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

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

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

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

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

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

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

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

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

2. Вступление.

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

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

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

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

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

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

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

- Лента: Бесконечная в обе стороны лента, разделенная на ячейки. Каждая ячейка может содержать один символ из конечного алфавита. Обычно включают "пустой" символ.

- Головка (читывающе-пишущая): Способна считывать символ из текущей ячейки ленты, записывать новый символ в эту ячейку и перемещаться влево или вправо по ленте на одну позицию.

- Множество состояний: Конечное множество внутренних состояний, в которых может находиться машина. Одно из состояний является начальным, а другие — принимающими (или конечными).

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

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

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

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

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

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

б₁) если i = 0, то в пустую ячейку вписана буква s_j, и б₂) если j = 0, то стерта буква s_i в обозреваемой ячейке.

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

Машина Тьюринга имеет конечное множество внутренних состояний: Q = {q₀, q₁, q₂, …, q_m}. В каждый данный момент времени машина Тьюринга находится в одном из своих внутренних состояний. После выполнения очередного такта работы машина может изменить свое внутреннее состояние и воспринимать ячейку в следующий момент уже в новом состоянии. Разумеется, внутреннее состояние может остаться и прежним. Если машина в какой-то момент времени попадет в состояние q₀, то ее работа заканчивается (состояние q₀ называется пассивным). Из множества Q выделим еще одно состояние — q₁ — начальное состояние. В этом состоянии машина всегда начинает свою работу.

Что умеет воображаемая машина?

За один такт работы она может:

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

И больше машина Тьюринга ничего не умеет делать.

Может показаться, что это очень мало. В действительности, это очень много.

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

Порядок работы машины Тьюринга с алфавитом A={s₀, s₁, s₂, …, s_k} и множеством состояний Q = {q₀, q₁, q₂, ..., q_m} полностью определяется программой, представляющей собой таблицу, содержащую k+1 столбец и m строк. В клетке таблицы на пересечении i-го столбика (i=0, 1, 2, ..., k) и j-й строки (j=1, 2, ..., m) вписана команда, которую должна выполнить машина Тьюринга.

Таблица 1

Если машина в какой-то момент воспринимает управляющей головкой ячейку, в которой записана буква s_i, и машина находится в состоянии q_j, команда будет записываться в виде трехбуквенного слова s_hTq_p, где ТÎ{Л, Н, П}, т. е. обозначает один из сдвигов управляющей головки.

Рассмотрим машину Тьюринга, программа которой задана таблицей 2:

Алфавит этой машины Тьюринга A = {s₀, 0, 1,2, 3, 4, 5, 6, 7, 8, 9}, а множество состояний: Q = {q₀, q₁}

Какую задачу решает эта машина?

Допустим, что в памяти машины перед началом работы хранится число 385, т. е. лента имеет вид, показанный на таблице 3 а):

Таблица 3

a)

б)

Из таблицы 3 а) видно, что машина в состоянии q₁ обозревает самый правый символ записи на ленте. Из программы (таблица 2) следует, что соответствующая паре (5,q₁) команда имеет вид: 6Нq₀. Согласно этой команде машина стирает цифру 5 в обозреваемой ячейке и помещает в ней цифру 6, остается на месте и переходит в состояние q₀, т. е. останавливается, причем состояние памяти будет таким, как показано в таблице 3, б). Таким образом, машина прибавила 1 к исходному числу.

Рассмотрим теперь другую начальную ситуацию, показанную на таблице 4 а), т.е. в памяти машины хранится число 4899.

Таблица 4

a)

б)

в)

г)

По окончании работы машины лента имеет вид, приведенный на таблице 4, г).

Когда исходное число — 4899, машина прибавляет единицу и останавливается. Нетрудно заметить, что вообще машина, определяемая программой, заданной таблицей 2, воспринимая в начальном положении запись любого натурального числа в десятичной системе счисления, по окончании своей работы будет выдавать в качестве результата запись этого числа, увеличенного на 1.

В дальнейшем будем считать, что машина всегда в начальном состоянии (т.е. в состоянии q₁) воспринимает самый правый символ записи на ленте (разумеется, отличный от s₀), и называть это положение, в котором машина воспринимает запись на ленте, стандартным.

5.      Задачи.

Задача 1.

Какую работу выполнит машина Тьюринга, если она работает по программе:

Пусть перед началом работы машины ее память (лента) имеет вид

Согласно программе, обозревая ячейку, в которой хранится знак |, и находясь в состоянии q₁ машина производит следующее действие: не производя никаких изменений в воспринимаемой ячейке, управляющая головка движется вправо, и машина остается в состоянии q₁

Состояние ленты после первого такта работы машины будет таким:

Дальнейшее действие приводит к остановке машины с состоянием ленты:

Таким образом, рассматриваемая машина отыскивает первую пустую ячейку справа от воспринимаемой, печатает на ней букву алфавита и останавливается, воспринимая эту ячейку.

Условимся представлять числа 0, 1, 2, 3, ... словами в алфавите {|}: |, ||, |||, ||||, ... соответственно. Для представления на ленте набора целых неотрицательных чисел x₁, x₂, ..., x_n мы будем писать соответствующее число раз букву |, оставляя в точности одну пустую ячейку между каждыми двумя словами (конечными последовательностями букв |). Так, набор чисел 3, 0, 2 запишется на ленте следующим образом:

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

В дальнейшем мы будем иметь дело только с целыми неотрицательными числами (расширенным нулем множеством натуральных чисел) или наборами этих чисел и их записями в однобуквенном алфавите {|}.

Пример 2.

Машина B воспринимает любое число из набора x₁, x₂, ..., x_n, уменьшает число палочек в его записи на одну и останавливается, воспринимая уменьшенное число. Так работает машина с программой, данной в таблице 6.

Таблица 6

Задача 2.

Изобразите на ленте в алфавите {s₀, |} набор чисел 2, 3, 4 и пусть машина В воспринимает второе число в стандартном положении. Изобразите ленту после работы машины. Какой набор чисел будет записан на ней?

Пример 3.

Машина C воспринимает набор чисел x₁, x₂, ..., x_n в стандартном положении и через одну пустую ячейку справа от этого набора записывает число 0, после чего останавливается, воспринимая 0.

Программа машины C представлена таблицей 7.

Таблица 7

Пустая клетка таблицы означает, что пара (|, q₂) не возникает в процессе работы этой машины (поэтому можно записать в этой клетке произвольную команду).

Задача 3.

Изобразите на ленте в алфавите {s₀, |} набор чисел 1, 2, 3 и имитируйте работу машины C (изобразите ленту после каждого такта машины до ее остановки).