Содержание к диссертации
Введение
1 Электронное обучение в сфере высшего образовании 13
1.1 Массовые открытые онлайн-курсы 13
1.2 Информационные технологии, инструменты и стратегии их использования в образовании 17
1.3 Современные тенденции развития высшего образования 26
1.4 Требования образовательных стандартов в части результатов обучения 30
1.5 Проектирование образовательных программ 33
1.6 Выводы 36
2 Информационные модели, форматы и протоколы в электронном обучении 38
2.1 Стандарты и технические отчеты ISO/IEC 38
2.2 Стандарты IEEЕ 60
2.3 Стандарты и соглашения CEN 67
2.4 Стандарты консорциума IMS GLC 74
2.5 Рекомендации и технические отчеты комитета AICC 80
2.6 Инициатива ADL 87
2.7 Стандарты ТК 461 91
2.8 Спецификация Leap2A 92
2.9 Стандарты Open Badges и Blockcerts 94
2.10 Выводы 96
3 Управление траекториями обучения и оцениванием результатов обучения 98
3.1 Модель образовательной программы 98
3.2 Реализация многоканальной обратной связи 102
3.3 Методика формирования индивидуальных траекторий обучения 104
3.4 Структура электронного курса 110
3.5 Сценарии обучающих диалогов 130
3.6 Сценарии предъявления учебного материала 148
3.7 Диалоговые формы 155
3.8 Выводы 172
4 Защита процедур оценивания результатов электронного обучения 175
4.1 Методы идентификации обучающихся 175
4.2 Проведение процедур оценивания в территориальных центрах 177
4.3 Дистанционный надзор за процедурой оценивания 178
4.4 Использование биометрических данных для защиты процедур оценивания 181
4.5 Метод непрерывной идентификации личности обучающегося 186
4.6 Экспериментальные исследования метода идентификации 198
4.7 Выводы 202
5 Технологии реализации индивидуальных траекторий обучения и оценивания результатов обучения 205
5.1 Электронная информационно-образовательная среда 205
5.2 Импорт и экспорт электронных учебно-методических материалов 216
5.3 Метод управления удаленной лабораторий 230
5.4 Абстрактные алгоритмические машины 241
5.5 Многостилевой редактор кода 243
5.6 Формальная верификация программ для машины Поста 248
5.7 Внедрение предлагаемых решений и разработанных технологий 265
5.8 Выводы 268
Заключение 271
Список литературы 273
- Информационные технологии, инструменты и стратегии их использования в образовании
- Методика формирования индивидуальных траекторий обучения
- Использование биометрических данных для защиты процедур оценивания
- Формальная верификация программ для машины Поста
Информационные технологии, инструменты и стратегии их использования в образовании
В ежегодном отчете NMC Horizon Report: 2015 Higher Education Edition [198], подготовленном консорциумом NMC (New Media Consortium - Консорциум новых медиа) в сотрудничестве с EDUCAUSE Learning Initiative (Образовательная инициатива EDUCAUSE), указаны наиболее многообещающие для высшего образования информационные технологии, ключевые факторы, способствующие их скорейшему внедрению, и наиболее существенные проблемы, препятствующие широкому распространению новых технологий обучения, в краткосрочной (один год или менее), среднесрочной (от двух до трех лет) и долгосрочной перспективе (от четырех до пяти лет).
По мнению авторов отчета, в ближайшее время содействовать внедрению новых технологий обучения будут следующие факторы:
тенденция к использованию смешанного обучения, при котором аудиторные занятия сочетаются с самостоятельной работой студента в автоматизированной системе управления процессом электронного обучения;
тенденция к перепроектированию учебных помещений, обусловленная студенто-центрированным подходом в образовании и переходом к активным формам обучения.
тенденция к сбору и анализу данных о поведении обучающихся в онлайн-системах с целью индивидуализации учебного процесса и непрерывного оценивания достигнутых результатов обучения (учебная аналитика);
тенденция к распространению открытых образовательных ресурсов, т.е. ресурсов, которые без каких-либо ограничений можно просматривать, копировать, редактировать и использовать где-либо.
развитие традиций перманентных обновлений и инноваций, обусловленных статусом университета как инкубатора новых идей и открытий;
рост межуниверситетской кооперации, обусловленный стремлением университетов к объединению усилий и ресурсов с целью достижения наивысших
показателей в научной и образовательной деятельности.
Наряду с этим, как указано в отчете, внедрение новых информационных технологий в образование будет сталкиваться со следующими проблемами и рисками:
слияние формального и неформального образования может привести к выхолащиванию последнего в силу консерватизма системы образования;
отсутствие единого понимания требований к компьютерной грамотности студентов, тьюторов и преподавателей.
тенденция к персонализированному обучению, которое позволяет строить учебный процесс исходя из потребностей, устремлений и культурных традиций индивидуума, требует проведения дополнительных научных исследований и разработки на их основе новых технологий;
потребность в обучении комплексному и системному мышлению, обусловленная необходимостью подготовки специалистов способных понимать и решать задачи реального мира на более высоком уровне, что предполагает разработку новым методов обучения и технологических средств.
новые модели образования вступают в конкуренцию с традиционными моделями высшего образования, когда студенты, находясь в университете в течение четырех лет, получают инструкции от профессорско-преподавательского состава в соответствии с образовательной программой;
в академической среде сложилась ситуация, при которой преподавание ценится значительно меньше научной работы, поэтому ведущие сотрудники университетов, как правило, уделяют меньше внимание преподавательской работе.
В настоящее время существуют семь категорий технологий, инструментов и стратегий их использования, которое NMC контролирует непрерывно. Они необходимы для классификации вновь появляющихся технологий, которые относятся к образованию. Список из семи категорий прошел проверку временем, новые технологии добавляются каждый год, некоторые технологии меняют названия, другие технологии объединяются под одним названием.
Пользовательские технологии являются инструментами, созданными для отдыха или профессиональных целей и не предназначенными, по крайней мере первоначально, для использования в образовательных целях - хотя они могут служить в качестве учебных пособий и вполне пригодными для использования в университетах. Эти технологии приходят в университеты, потому что они широко используются.
Цифровые стратегии не относятся к технологиям, поскольку они являются способами использования цифровых устройств и программного обеспечения для обогащения преподавания и обучения, будь то внутри или за пределами аудитории. Эффективные цифровые стратегии могут быть использованы как в формальном, так и неформальном обучении.
Высокоэффективные технологии позволяют расширить возможности наших инструментов, сделать их более совершенными, полезными, а также простыми в использовании. Это та группа технологий, где главное технологическое новшество становится явным.
Интернет-технологии включают в себя методы и инфраструктуру, которые помогают сделать технологии, с помощью которых осуществляется взаимодействие с сетью, прозрачными и простыми в использовании.
Технологии обучения включают в себя как инструменты и ресурсы, разработанные специально для использования в образовании, так и инструменты, изначально созданные для других целей, но адаптированные для применения в образовании. Эта группа включает в себя технологии, которые расширяют процесс обучения, сделав его более доступным и персонализированным.
Социальные медиа-технологии могли быть отнесены к пользовательским технологиям, но так как они стали вездесущими и широко используются по всему миру, то для них создана отдельная категория. Несмотря на то, что эти технологии появились достаточно давно, они продолжают развиваться быстрыми темпами.
Технологии визуализации охватывают диапазон от простой инфографики до сложных форм визуального анализа данных. Их объединяет то, что они основаны на способности мозга быстро обрабатывать визуальную информацию, выявлять закономерности, воспринимать смысл и порядок в сложных ситуациях. Эти технологии принадлежат растущему кластеру инструментов и процессов для интеллектуального анализа больших наборов данных и динамических процессов.
Экспертам для определения технологий, инструментов и стратегий их использования, которые окажут наиболее сильное воздействие на высшее образование в течение пяти лет, изначально был предложен список, приведенный в таблице 1.2, из которого требовалось выбрать по два наименования на каждую из перспектив: краткосрочную, среднесрочную и долгосрочную.
Методика формирования индивидуальных траекторий обучения
Методика предусматривает построение индивидуальных траекторий обучения на трех уровнях [220]:
уровень образовательной программы,
уровень электронного курса,
уровень сценария взаимодействия.
Уровень образовательной программы предусматривает построение индивидуальной траектории обучения с учетом модульной структуры программы. В этом случае, формирование индивидуального учебного плана осуществляется на основе набора учебных курсов, используя:
множество результатов обучения V = {LOCt\ і Є IL0C с JV},
множество пороговых значений уровней подготовки LA = {в-: і Є IL0C с JV},
структуру результатов обучения W = { (LOCu LOCj): LOCu LOCj Є V, W(i,j)},
текущий уровень подготовки обучающегося LA = {в{: і Є IL0C с JV},
информацию об образовательной программе {Vb, Vf, т0 ,
множество доступных учебных курсов С = {Щ: і Є ILC с JV}, и предполагает следующий алгоритм действий:
1) формирование множества достигнутых результатов обучения Vа = {LOCf. LOCt EV,et о-У;
2) определение новых множеств пререквизитов и результатов освоения образовательной программы U$ =VbUVaи UrQ = V \Va;
3) построение булеана Т(С) множества всех курсов С;
4) формирование на основе булеана Т(С) множества С, содержащего совокупности курсов, удовлетворяющих одновременно условиям эффективности, результативности, обоснованности пререквезитов, востребованности и уникальности результатов обучения, ацикличности совокупности курсов по отношению к множествам UQ и t/g .
Таким образом, множество С будет содержать коллекции курсов, удовлетворяющие требованиям образовательной программы, поэтому любая из коллекций может использоваться при реализации образовательной программы. Для каждой совокупности курсов средствами сетевого планирования может быть построен индивидуальный план [113], если принять, что работами являются курсы, а зависимости описываются через пререквизиты и результаты обучения курсов. Сетевое планирование позволяет определить критический путь, который соответствует сроку освоения образовательной программы. Для выбора конкретной коллекции необходимо применить дополнительный критерий, например:
минимальная трудоемкость образовательной программы;
минимальный срок освоения образовательной программы;
максимальная доля практических занятий;
максимальная доля видеоматериалов;
предпочитаемый авторский коллектив.
В автоматизированной системе управления процессом электронного обучения реализация образовательной программы по выбранной совокупности курсов не потребует предварительного построения индивидуального плана. В частности, возможен следующий алгоритм освоения образовательной программы, если выбрана совокупность курсов С[ =
1) на выбор обучающемуся предлагается коллекция курсов С0 = {LCf. LCj Є Cl,LCj = (Vf,v/,Tj),Vf с и?};
2) обучающийся в соответствии со своими предпочтениями выбирает курс LCS Є С0 и изучает его;
3) после успешного завершения курса LCS Є С0 вычисляются множества Uf+1 = Uf U
4) если C i+1 = 0, то обучение по образовательной программе завершается, иначе і увеличивается на 1 и осуществляется переход к п. 1.
Очевидно, что при выполнении условий эффективности, результативности, обоснованности пререквизитов, востребованности и уникальности результатов обучения, ацикличности совокупности курсов данный алгоритм завершиться за р шагов и все планируемые результаты освоения образовательной программы (Vb,Vf, т0) будут достигнуты за время, которое не превышает т0.
Для конкретной образовательной программы использование описанного алгоритма обеспечивает построение нескольких различных схем реализации образовательной программы, все из которых будут удовлетворять заданным пререквизитам и результатам обучения образовательной программы. Построение схем осуществляется на основе анализа пререквизитов и результатов обучения курсов, что позволяет создавать различные наборы курсов, удовлетворяющие требованиям образовательной программы. Рассмотрим пример схемы реализации образовательной программы, представленный на рисунке 3.2. Схема реализации образовательной программы основывается на пререквизитах {LOC1,LOC2} и реализует результаты обучения {LOC7,LOCe,LOC9}, соответствующие результатам обучения, указанным в образовательной программе. Рассматриваемая схема реализации образовательной программы включает 6 курсов \LC1,LC2 ...LC6}, часть из которых, в соответствии с современными тенденциями, может быть представлена в виде открытых онлайн-кур сов. Данная схема предполагает, что результаты обучения курса ЬСг являются пререквизитами курса LC4, что требует последовательного прохождения этих курсов. При успешном завершении курсов LC2 и LC3 обучающемуся становится доступным курс LCS. Курс LC6 является завершающим курсом, обеспечивающим результаты обучения по образовательной программе. Он становится доступным для обучающихся после успешного завершения курсов LC4 и LCS . Таким образом, при построении индивидуального учебного плана (рисунок 3.3) для заданной схемы может быть выделено 3 семестра, при этом курсы ЬСЪ LC2 и LC3 могут проходить параллельно в первом семестре, в то время как во втором семестре для обучающегося откроются курсы LC4 и LC5, завершится обучение курсом LCe, по итогам которого будут получены все необходимые знания, умения и навыки.
Наравне с описанной схемой реализации образовательной программы может быть также сформирована другая схема (рисунок 3.4), удовлетворяющая требованиям к пререквизитам и результатам обучения образовательной программы. Сформированный набор курсов основывается на тех же пререквизитах {LOCvLOC2} и результатах обучения {LOC7,LOC8,WC9} образовательной программы, как и в первом случае, однако набор использованных курсов отличается от первого варианта.
Схема реализации образовательной программы, представленная на рисунке 3.4, включает 7 курсов {LC7,LC8...LC13}, что позволяет создать отличающийся от первого варианта индивидуальный учебный план (рисунок 3.5). В соответствии с представленным учебным планом, для освоения образовательной программы с указанной схемой реализации должно быть отведено четыре семестра. Курс LC7 является единственным курсом, представленным в первом семестре, поскольку его результаты обучения обеспечивают пререквизиты для курсов второго семестра LC8, LC9 и LC10, базирующихся в то же время и на пререквизитах образовательной программы. Курсы второго семестра должны быть пройдены одновременно с тем, чтобы обеспечить получение необходимых знаний и навыков, являющихся пререквизитами к курсам третьего семестра. В третьем семестре обучающимся открывается курс LClt после успешного прохождения ими курсов LC8 и LC9, и LC12, к которому обучающиеся могут приступить после окончания курса LC9. Курсы третьего семестра обеспечивают 2 из 3 необходимых результатов обучения образовательной программы. Выполнение требований образовательной программы по третьему результату обучения достигается в четвертом семестре путем прохождения завершающего курса LC13.
Использование биометрических данных для защиты процедур оценивания
Наиболее перспективные методы идентификации личности построены на результатах анализа биометрических данных, которые позволяют определить физиологические или поведенческие особенности человека. Создание систем для защиты процедур оценивания, построенных на анализе биометрических данных, позволит преодолеть ограничения и недостатки, свойственные наблюдению за процедурой оценивания в территориальном центре или дистанционно (таблица 4.1).
В силу ряда причин среди биометрических данных человека особо большое значение для электронного обучения имеют параметры движения глаз обучающегося во время его работы в автоматизированной системе управления процессом обучения, т.к. эти данные можно одновременно использовать для идентификации личности обучающегося и его состояния, для оценивания результатов обучения и организации интерфейсов пользователя нового типа. Появляется возможность, анализируя параметры движения глаз, одновременно осуществлять идентификацию личности обучающегося, оценивание его функционального состояния и достигнутых им результатов обучения. В конце 70-х годов 19-го века известный французский офтальмолог Луи Эмиль Жаваль определил понятия [197] фиксаций – фокусировки взгляда в определенной области – и саккад – быстрых перемещений взгляда между точками фиксаций. В связи с началом быстрого развития технологий в начале 20-го века стали появляться первые айтрекеры – приборы для регистрации параметров движения глаз и траектории взгляда [123], которые позволили различить другие типы движения взгляда, такие как плавные и вергентные перемещения [175]. С тех пор, технологии ушли далеко вперед [177], [178], [236], [259], и на данный момент существует множество типов айтрекеров с различными частотами дискретизации данных, используемых в разнообразных научных областях и сферах деятельности.
Высокочастотные айтрекеры с частотой дискретизации данных 120 Гц и выше широко используются в различных медицинских исследованиях, в том числе в области когнитивной психологии и неврологии [252] или офтальмологии [150]. Технологии для регистрации траектории взгляда также применяются для определения психофизиологического состояния человека [213], [249] или когнитивной нагрузки во время обучения [149], поскольку данные движения глаз предоставляют множество информации, в том числе и об изменении размеров зрачков, что часто используется в качестве индикатора функционального состояния человека [243], [253]. Айтрекеры широко применяются при проведении различных исследований в сфере информационных технологий. Одной из основных областей являются юзабилити-исследования [159], [235]. Также подобные системы используются при проектировании пользовательских интерфейсов, основанных на управлении взглядом [196], [225], и в области образования [204] для определения результатов обучения с помощью анализа траектории взгляда.
Одной из наиболее перспективных сфер исследований движения глаз является биометрическая идентификация [167], [168], [210], [251], [258]. В современном мире существует множество систем, предоставляющих доступ к различным информационным ресурсам. Большинство таких систем являются закрытыми и требуют прохождения человеком процедуры подтверждения личности, в связи с чем, одним из наиболее важных вопросов является обеспечение стабильных высокоточных методов идентификации. Наиболее часто используемым в информационных системах способом идентификации является проверка личных данных – имени пользователя и пароля, однако такой способ не предоставляет точной информации о человеке, пытающемся получить доступ к ресурсу. Вследствие этого, некоторые системы постепенно внедряют методы биометрической идентификации, которые в последнее время обретают все большую область применения в силу предоставления неподдельной информации о человеке. На текущее время существует множество различных методов биометрической идентификации, в том числе анализ отпечатков пальцев [152] или ладони [237], определение формы ушной раковины [231], анализ радужной оболочки глаз [179], исследование формы сигнала ЭКГ [145], идентификация с помощью клавиатурного почерка [144] и др. Тем не менее, вышеупомянутые методы биометрической идентификации не предоставляют высокоточной информации и подобные данные являются воспроизводимыми, что не обеспечивает достаточную защиту от подлога. В то же время, глаза предоставляют огромное количество информации о человеке. Движения глаз являются сложными и уникальными для каждого человека особенностями, неповторимыми биометрическими данными, включающими также поведенческие характеристики. Следовательно, методы биометрической идентификации, основанные на анализе движения глаз человека, призваны стать одними из наиболее высокоточных.
Глаза человека являются динамической системой, на которую оказывает влияние показанный стимул, например, текст или изображение, а выходным параметром является траектория взгляда, которая может быть отслежена с помощью айтрекера. Глаза обладают различными динамическими характеристиками, в том числе скоростью, ускорением, угловой скоростью и другими. Были проведены различные исследования, направленные на изучение этих особенностей [167], [210]. Авторы в своих публикациях описывают эксперименты по комбинированию этих параметров с другими параметрами, рассчитанными по траектории взгляда и исследуют возможное их использование для биометрической идентификации пользователей. На данный момент подобные методы идентификации не предоставляют необходимой точности, поэтому проводится большое количество исследований, связанных с поиском наилучших методов. Авторы используют различные параметры для идентификации и различные стимулы для получения данных о траектории взгляда [167]. Также проводятся соревнования, нацеленные на поиск методов идентификации, основанных на анализе траектории взгляда, предоставляющих наиболее точные результаты по определенному набору данных, выданному участникам [205], [206]. Благодаря возрастающему количеству упоминаний данной темы, все большее количество исследователей по всему миру демонстрируют к ней свой интерес.
Айтрекеры – это технические устройства, включающие аппаратное и программное обеспечение. В большинстве исследований используются высокочастотные айтрекеры с частотой дискретизации данных от 120 Гц. Однако, чем больше частота дискретизации, тем более сложным внутренним устройством обладает айтрекер. Многие авторы также описывают применение камер для регистрации траектории взгляда, но, в основном, камеры также являются высокочастотными, например, в исследовании [251] была использована камера с частотой 500 кадров в секунду. Следовательно, является востребованным применение низкочастотных айтрекеров, и в текущем исследовании использовался прибор с частотой дискретизации 30 Гц, что приближенно равно частоте кадров, установленной в стандартных камерах.
В последнее время многими авторами были представлены различные методы идентификации на основе анализа траектории взгляда. Для каждого метода авторы подсчитывают погрешность, определяющую точность представленного метода. Наиболее часто используемыми типами оценки точности являются процент ложных принятий (FAR) и ложных отказов (FRR), а также половинная оценка, объединяющая две предыдущие (HTER) [195], [232]. FAR определяется отношением количества ложных принятий к общему количеству возможных ложных входов. Ошибка FRR представлена отношением количества ложных отказов к общему количеству попыток доступа к системе зарегистрированными пользователями системы. HTER объединяет два описанных ранее типа ошибок и определена как (FAR+FRR)/2. Многие авторы также оценивают точность, используя оценку равных ошибок (EER), рассчитываемую в точке, где значения FAR и FRR равны. Другим методом оценки точности методов служит построение кривых рабочих характеристик приемника (ROC) [195], [203] – кривых, основанных на FAR и FRR, рассчитанных по значениям экспериментов.
Данные траектории взгляда могут быть собраны с применением различных стимулов. Например, в исследовании [167] были использованы 4 стимула, два из которых представляли собой наборы точек и пользователю было необходимо воспроизвести путь между определенными точками с помощью взгляда, третий стимул состоял из трех линейных графиков и предназначался для того, чтобы пользователь отследил глазами каждый из графиков, четвертый стимул не заключал в себе определенного задания и представлял собой некоторое изображение. Одним из наиболее часто используемых стимулов являются определенным образом перемещающиеся по экрану точки [251], [258].
После получения необходимых данных о траектории взгляда применяется некоторый метод для их обработки. В нескольких исследованиях [167], [168] авторы рассматривают различные динамические параметры взгляда, например, скорость, ускорение, угловую скорость взгляда, а также скорость изменения размеров зрачков и другие параметры для саккад и фиксаций. Некоторые методы сконцентрированы на анализе одного конкретного типа движения взгляда, например, скорость, ускорение, амплитуда и другие особенности саккад [210], [251], [258].
Формальная верификация программ для машины Поста
Лабораторные работы отличаются от тестовых заданий видом множества правильных ответов. В тестовых заданиях множество правильных ответов перечислимо и разрешимо, т.е. обладает общерекурсивной характеристической функцией. В заданиях лабораторных работ в качестве множества правильных ответов в общем случае выступает язык, порожденный формальной грамматикой произвольного вида. Таким образом, множество правильных ответов в заданиях лабораторной работы может оказаться алгоритмически неразрешимым [25]. Это означает, что не существует алгоритма, который по любому ответу обучающегося дает ответ, правильный он или нет. В большинстве случаев ответ представляет собой описание некоторой системы, которое составлено на указанном языке. Функционирование описанной системы может быть воспроизведено в определенной программной среде и заключается в переработке входных данных в выходные. Для того чтобы убедиться в правильности ответа обучающегося, необходимо проверить реакцию системы на всех возможных наборах входных данных. Однако даже в простейших случаях множество наборов входных данных оказывается бесконечным, поэтому ограничиваются проверкой реакции системы на некоторых наиболее характерных наборах входных данных, что не гарантирует правильную работу системы на других наборах данных. Для решения указанной проблемы можно прибегнуть к методу символьного выполнения [140], [154], [250], который может стать эффективным инструментом для проверки ответов обучающихся в силу ограниченности их размера.
Проиллюстрируем сказанное с помощью виртуальной лаборатории "Машина Поста", поскольку она является наиболее простой алгоритмической машиной, имеющей минимальный алфавит, представленный двумя элементами. Машина Поста состоит из ленты и каретки, называемой также считывающей и записывающей головкой. Лента бесконечна в обе стороны и разделена на ячейки одинакового размера, каждая из которых может либо содержать метку, либо быть пустой. Информация о том, какие ячейки отмечены, описывает состояние ленты. В начальный момент времени только конечное количество ячеек содержат метку, остальные остаются пустыми. Если единицей обозначить отмеченную ячейку, а нулем пустую, то каждому состоянию ленты можно поставить во взаимно однозначное соответствие слово из нулей и единиц. Слова, соответствующие состояниям ленты машины Поста, образуют язык, который можно определить регулярным выражением 8+1+1(0+1) 1, где є - пустая цепочка. За единицу времени, которую называют шагом, каретка может переместиться вдоль ленты на одну ячейку влево или вправо, поставить метку в неотмеченную ячейку или снять метку с отмеченной ячейки, определить, отмечена или нет ячейка, напротив которой она находится. Ячейка ленты, напротив которой находится каретка, называется обозреваемой. Состояние, или конфигурация, машины определяется состоянием ленты и положением каретки на ленте. Описать состояние машины можно тройкой 1Л 2, где 1 - слово, описывающее состояние фрагмента ленты слева от каретки, Л - символ, символизирующий положение каретки, 2 - слово, описывающее состояние фрагмента ленты, образованного обозреваемой кареткой ячейкой и ячейками справа от нее. Стандартной конфигурацией называется конфигурация, при которой каретка обозревает крайнюю слева отмеченную ячейку, т.е. состояние Л, где - слово, описывающее состояние ленты.
Программа машины Поста состоит из команд следующих видов:
1) переместить каретку вправо и перейти к команде с номерому (движение вправо)
2) переместить каретку влево и перейти к команде с номерому (движение влево)
3) установить метку в обозреваемую ячейку и перейти к команде с номером/
4) снять метку с обозреваемой ячейки и перейти к команде с номером/
5) если обозреваемая ячейка не содержит метки, то перейти к команде с номером j1, иначе перейти к команде с номером (команда передачи управления)
6) остановка
Здесь / - порядковый номер команды в программе, j, j1, у 2 - ссылки, номера команд, которым будет передано управление после выполнения команды. Количество команд программы F обозначим \F\. Программа для машины Поста считается правильной, если для каждой ссылки существует команда с указанным номером. Команда установки метки в отмеченную ячейку и команда снятия метки из пустой ячейки считаются невыполнимыми. Чтобы запустить машину Поста, надо задать программу и начальную конфигурацию машины. После запуска машина приступает к выполнению первой команды и выполняет ее за один шаг. Далее машина переходит к выполнению команды, номер которой указан в ссылке или ссылках первой команды. Если, задав программу и начальную конфигурацию, запустить машину, то может произойти одно из трех событий:
1) машина достигнет невыполнимой команды - выполнение программы прекращается, происходит безрезультатная остановка;
2) машина достигает команды остановки - выполнение программы прекращается, происходит результативная остановка;
3) машина работает бесконечно - выполнение программы никогда не прекращается.
Во время выполнения программы машина переходит из одной конфигурации в другую. Если во время выполнения / -й команды программы F машина за один шаг перешла из конфигурации Кг в конфигурацию К2, то пишут Кг - К2. Индекс / можно опустить при условии, что из контекста ясно, о какой команде идет речь. Если в процессе выполнения программы F машина за п шагов переходит из конфигурации Кг в конфигурацию К2, выполняя последовательность команд S = (i1, i2,..., in-1), где 1 ij \F\,j = 1,2,... , n - 1, то будем писать Л = ЛГ2. Если машина из конфигурации 1Л2 начинает выполнять программу F и осуществляет результативную остановку в конфигурации р1Лр2, то говорят, что программа F перерабатывает слово 12 в слово р1р2, и писать Д 12)=р1р2. Вместе с тем запись F() может обозначать программу F с исходными данными . В дальнейшем будут рассматриваться программы, которые машина начинает выполнять из стандартной конфигурации и осуществляет результативную остановку в стандартной конфигурации.
Пример 5.1. В качестве примера рассмотрим программу, которая добавляет единицу к числу, записанному на ленте машины в унарном коде:
В унарном коде любое натуральное число х представляется словом 11… 1=1 , последовательность натуральных чисел х1, х2, … , хп представляется словом 1Х10У11Х20У2 ...0у-1 1х, гдеу1, у2, … , уп - некоторые натуральные числа. В рассматриваемом примере начальная стандартная конфигурация машины будет иметь вид Л1х. Первая команда перемещает каретку влево и переводит машину в конфигурацию Л01х; вторая команда устанавливает метку в обозреваемую ячейку и переводит машину в конфигурацию Л1х+1; третья команда не меняет конфигурацию машины и осуществляет результативную остановку. Поэтому программе соответствует следующая последовательность конфигураций Л1х Л01Х Л1Х+1 Л1Х+1, отсюда следует, что Л1Х = Л1Х+1 и F(1x) = 1x+1. Подобные рассуждения позволяют описать результат работы программы в символьном виде, и, следовательно, восстановить функцию, значения которой вычисляет программа, что можно использовать для оценивания программ [64].