Свыше пятидесяти лет назад выдающийся американский математик Эмиль Л. Пост опубликовал статью "Финитные комбинаторные процессы, формулировка 1". В этой публикации в появившейся одновременно статье английского математика А. М. Тьюринга "О вычислимых числах с приложением к проблеме разрешения" было впервые уточнено понятие "алгоритм" - одного из центральных понятий математической логики и информатики, играющих все более важную роль в автоматизации, и, следовательно, в жизни современного общества.
Эти работы замечательны также тем, что в них за несколько лет до появления первых действующих экземпляров больших ("универсальных") вычислительных машин были в абстрактной форме предвосхищены их основные принципиальные черты. Сами конструкции были предложены Постом и Тьюрингом в виде неких "абстрактных машин".
Архитектура первого идеального компьютера
Машина Тьюринга - модель математического устройства, порождающего вычислительные процессы с целыми числами. Она состоит из абстрактной бесконечной в оба конца ленты, разделенной на секции (ячейки) одинакового размера, и каретки, способной обозревать эти ячейки. В каждой из ячеек может быть записана или метка, или "пустой" знак. Распределение меток по ленте составляет состояние машины Тьюринга. Каретка может двигаться по ленте влево или вправо, ставить метки или стирать их, а также распознавать состояние ячейки на текущий момент времени. Целым числом принято считать совокупность меток, не содержащую в себе пустых ячеек.
Состояние машины Тьюринга в следующий момент времени определяется ее состоянием в данный момент времени (меткой, воспринимаемой в данной ячейке) и командой, соответствующей данному моменту времени. Таким образом, поведение машины Тьюринга, обусловленное только этими факторами, не зависит от ее прошлых состояний: в этом смысле машина Тьюринга не имеет памяти. Она реагирует только на команды, составляющие алгоритм ее работы:
· стереть метку,
· поставить метку,
· распознать состояние ячейки,
· сдвинуться вправо,
· сдвинуться влево,
· остановиться.
Алгоритмом машины Тьюринга называется конечный, содержащий в себе хотя бы одну команду список команд машины Тьюринга, обладающий следующими свойствами:
· на k месте в списке должна стоять k команда;
· ссылка команды должна производиться на существующую в списке команду.
Согласно тезису Тьюринга, любой математический процесс может быть преобразован в алгоритм для машины Тьюринга. На практике это осуществимо, если допустить существование алгоритмов сколь угодно длинных и сколь угодно долго работающих.
Уточнения, внесенные в понятие "алгоритм" Постом и Тьюрингом, не потеряли своего значения до сих пор. В настоящее время машина Тьюринга постоянно используется в качестве рабочего аппарата в современной теории алгоритмов.
Наш проект
Программа "Машина Тьюринга" предназначена для моделирования работы машины Тьюринга. Она может быть использована для ознакомления с машиной Тьюринга и принципами ее работы, для теоретического уточнения понятия алгоритма и для его исследования, а также при изучении теории алгоритмов. Программа ценна также тем, что содержит в себе четыре общих алгоритма нахождения суммы, модуля разности, произведения, целой части и остатка от деления двух целых чисел.
Программа "Машина Тьюринга" написана на языке Borland Pascal 7.0. Для упрощения программирования за основу "бесконечной" ленты взята строковая переменная (s: string), которая заполнена буквами A и B, соответственно означающими "не пусто" и "пусто". По этой строке моделируется графическое представление "бесконечной" ленты, состоящей из ячеек. Координаты передвигающейся каретки строго привязаны к координатам ячеек. Размер ячеек и каретки масштабируется в зависимости от длины строки.
Для имитации основных команд машины Тьюринга были созданы специальные процедуры:
· Vlevo – движение каретки влево
· Vpravo – движение каретки вправо
· Eraser – стирание галочки
· Painter – рисование галочки
Команда "Анализ содержимого ячейки" реализована в виде условного оператора if поэтому алгоритмы в программе представлены как наборы этих процедур и условных операторов.
Основной экран программы выполнен в виде пяти параллелепипедов (кнопок), переключение по которым осуществляется с помощью клавиш управления курсором.
В программу заложены четыре общих алгоритма:
· суммы двух чисел,
· разности двух чисел,
· произведения двух чисел,
· целочисленного частного и остатка от деления двух чисел.
Для создания программы были созданы два модуля: Algoritm.tpu и Screener.tpu. Первый содержит алгоритмы и процедуры работы с лентой, а также управляющие движением каретки; второй – процедуры, формирующие окна и управляющие ими. Таким образом, исходный вариант программы состоит из файла программы Turing.pas, двух модулей Algoritm.tpu и Screener.tpu, файла помощи Turing.hlp и стандартных драйверов.
Программа содержит файл помощи с краткой информацией по машине Тьюринга и по программе в целом. Доступ в файл возможен из самой программы (Помощь).
Программа содержит следующие экраны:
1. главный экран <Рис.1>
2. экран выбора операции <Рис.2>
3. экраны ввода данных <Рис.3>
4. экран демонстрации: машина выполняет вычитание: 5-2 с расстоянием между числами в 2 ячейки
начальный этап <Рис.4 >
стирание символа первого числа <Рис.5>
движение каретки вправо <Рис.6>
стирание символа второго числа <Рис.7>
движение каретки влево <Рис.8>
Каретка двигается до начала уменьшаемого; когда она его достигает – закончен один цикл; работа повторяется до тех пор, пока не закончится одно из чисел; результат получен: <Рис.9 >
5. экран примеров <Рис.10>
6. экран демонстрации алгоритмов
алгоритм модуля разности <Рис.11>
Выход из программы осуществляется через меню "Выход".
Авторы программы – выпускники 1999 года школы № 1414 Рослова Е., Симакин А.
Приоритетной формой сдачи экзамена я считаю защиту реферата, в котором представлена большая программа с техническим описанием. Учащиеся пишут программы в течение года и защищают их во время выпускных экзаменов в 9-х и 11-х классах соответственно. Защита подразумевает демонстрацию работы программы; учащиеся объясняют особенности ее функционирования и порядок написания. Обязательным является наличие реферата. Я предъявляю строгие требования к экзаменационному реферату: необходимо описание назначения работы, постановка задачи, исходный текст программы, если возможно, полный перечень используемых переменных, описание объектов, укрупненная блок-схема программы. Принимается только работающая программа! Учащийся ставит перед собой две цели: изучение особенностей среды программирования, в которой он работает, и создание программного продукта, готового к реализации. Из десятилетнего опыта преподавания я могу сделать вывод о правильности данного направления: ученики с удовольствием и успешно работают над программой, а выпускники часто с интересом продолжают развивать свой школьный проект и в институте. Программы по направлению очень разные: от учебных пособий по предметам школьной программы и игр до мультимедийных проектов: 3D-графических и Web-сайтов, так как в последние годы расширилось использование доступных нам по аппаратным возможностям технологий. В дальнейшем ученики и выпускники с интересом развивают свои проекты. О "Машине Тьюринга", например, могу сказать, что предпринимаются попытки дальнейшего развития программы, а именно: создается редактор произвольных алгоритмов самих учащихся, т. е. программа принимает действительно обучающий характер.
КОРОТКО ОБ АВТОРЕ:
Кряжева Анна Анатольевна – преподаватель ИВТ школы № 1414, руководитель проекта "Машина Тьюринга"
E-mail: uvk1414@mtu-net.ru