Содержание
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Содержание

  О программе

Теория:

   Из истории...

   Машина Поста:

     • Устройство

     • Система команд

     • Порядок работы

   Машина Тьюринга:

     • Устройство

     • Система команд и порядок работы

Работа с программой:

  Главное меню

  Машина Поста:

     • Информационная лента

     • Таблица

     • Исполнение алгоритма

     • Возникающие ошибки

  Машина Тьюринга:

     • Внешний алфавит

     • Информационная лента

     • Таблица

     • Исполнение алгоритма

     • Возникающие ошибки


О программе
Algo2000

Интерпретатор машины Поста и машины Тьюринга

О программе

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

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

Требования:

        компьютер IBM PC AT 486 и выше (на "тройках" не тестировал),

        наличие операционной системы Windows' 95/98/NT,

        палитра не менее 16 разрядов.

Автор - Зартдинов Радик,

        студент 4 - го курса факультета "Информатика - Экономика",

        Пермского Государственного Педагогического Университета.

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

         algo@newmail.ru

         radik_z@chat.ru

Домашняя страничка:

         http://algo.newmail.ru

Апрель, 2000 год.

содержание


Из истории...
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Из истории...

Свыше пятидесяти лет назад, в 1935 году, выдающийся американский математик Эмиль Л. Пост опубликовал в     "Журнале символической логики" статью "Финитные комбинаторные процессы, формулировка 1". В этой статье и появившейся одновременно в "Трудах Лондонского математического общества" статье английского математика А.М. Тьюринга "О вычислимых числах с приложением к проблеме решения" были даны первые уточнения понятия "алгоритм" - одного из центральных понятий математической логики и кибернетики, играющего важную роль в вопросах автоматизации, а поэтому и во всей жизни общества.

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

Ее суть:

• вся информация, которая должна быть обработана по существу, должна быть обработана по форме, то есть, с помощью двоичного алфавита.

• вся  информация должна обрабатываться побуквенно.

При этом Пост доказал, что его система обладает алгоритмической полнотой. Его идеи были настолько фундаментальны, что к ним вернулись через 30 лет. В 1967 году профессор Успенский пересказывает их с новых позиций. Он вводит термин машины Поста. Машина Поста - абстрактная машина, которая работает по алгоритмам, разработанным человеком.

Уточнения понятия "алгоритм", предложенные Постом и Тьюрингом, не теряют своего значения до нашего времени. Машина Тьюринга часто используется в качестве рабочего аппарата в теории алгоритмов; машина Поста менее популярна, хотя - или именно по той причине, что она проще машины Тьюринга. Машина Поста устроена проще, чем машина Тьюринга, в том отношении, что ее элементарные действия проще, чем элементарные действия машины Тьюринга, и способы записи менее разнообразны, однако по этим причинам запись и переработка информации на машине Поста требует, вообще говоря, большего объема "памяти" и большего числа шагов, чем на машине Тьюринга.

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

В 1970 году машина Поста была разработана в металле в Симферопольском Университете. А машина Тьюринга была построена в металле в 1973 году в Малой Крымской Академии Наук.

содержание


Устройство машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Устройство машины Поста

  Машина Поста - абстрактная машина.

  Машина Поста состоит из ленты и каретки (считывающая и записывающая головка). Лента бесконечна и разделена на секции одинакового размера.

  В каждую секцию ленты заносится один символ двоичного информации, который подлежит обработке. Один из символов двоичного алфавита - метка "V", другой - пустота.

Если в секцию занесена "V" - секция отмеченная, если в секции "V" нет - секция пустая или неотмеченная.

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

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

  Команды, по которым каретка должна занести метку в отмеченную секцию или удалить метку из пустой секции являются недопустимыми.

См. также:

Система команд машины Поста.

Порядок работы машины Поста.

содержание


Система команд машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Команды машины Поста

Формат команды: nKm, где:

n  - номер текущей команды,

K  - команда из системы команд машины Поста,

m - отсылка - номер команды, которая будет выполняться следующей.

Последовательность команд из системы команд - программа, если:

1) на n - ом месте этой программы будет стоять команда с номером n.

2) отсылке m соответствует реальная команда в программе.

Система команд машины Поста:

1). a [image] b

Сдвиг каретки вправо, содержимое ленты не меняется.

2). a [image] b

Сдвиг каретки влево,  содержимое ленты не меняется.

3). a [image] b

В обозреваемую секцию ставится метка "V". Выполнение этой команды возможно только в том случае, если обозреваемыя секция пустая, в противном случае команда считается невыполнимой.

4). a [image] b

Каретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемыя секция содержит метку, в противном случае команда считается невыполнимой.

5). a [image] b1, b2

Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть - команде с номером b2. Содержимое ленты не меняется.

6).  a [image] [ b ]

Команда останова машины.  Содержимое ленты не меняется. У команды остановки отсылка не обязательна.

См. также:

Устройство машины Поста.

Таблица машины Поста

Порядок работы машины Поста.

содержание


Порядок работы машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Порядок работы машины Поста

  Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Чтобы машина Поста работала, надо задать некоторую программу и некоторое состояние машины (т.е. нужно как-то расставить метки по секциям ленты, в частности, можно все секции   оставить пустыми, и поставить каретку против одной из секций).

 Работа машины на основании заданной программы происходит следующим образом.

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

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

1) если эта команда имеет единственную отсылку b, то на (k + 1)-ом шаге выполняется команда с номером b;

2) если эта команда имеет две отсылки b1 и b2, то на (k + 1)-ом шаге выполняется одна из двух команд - с номером b1 или с номером b2;

3) если же выполняющаяся на k-ом шаге команда вовсе не имеет отсылки,  то на (k +1) - ом шаге и на всех последующих шагах не выполняется никакая команда – машина останавливается.

Возможные случаи останова машины Поста:

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

2) в ходе выполнения программы машина дойдет до выполнения команды остановки;

программа в этом случае считается выполненной, машина останавливается - происходит результативная остановка.

3) в ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах; выполнение программы при этом никогда не прекращается, машина никогда

не останавливается - процесс работы машины происходит бесконечно.

См. также:

Устройство машины Поста.

Система команд машины Поста.

содержание


Устройство машины Тьюринга
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Устройство машины Тьюринга

  Машина Тьюринга - абстрактная машина.

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

  Лента ограничена (т.е. жестко закреплена) слева и бесконечна справа. Лента разделена на секции одинакового размера.

  В каждую секцию ленты заносятся символы внешнего алфавита машины Тьюринга

A = {a0, a1,... aN}, где а0, как правило, пробел.

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

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

  Операционное исполнительное устройство может находиться в одном из дискретных состояний:

Q = {q0, q1,...qM} - внутренний алфавит машины Тьюринга или алфавит внутренних состояний.

См. также:

Команды и порядок работы машины Тьюринга

содержание


Команды и порядок работы машины Тьюринга
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Команды и порядок работы машины Тьюринга

  Порядок работы машины Тьюринга обычно задается в виде таблицы:

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

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

A/Q  |  q0   |  q1  |   ...   |  qn

      -----------------------------------------------

a0     |          |        |         |

a1     |          |        |         |

...      |          |        |         |

ai      | aKq  |        |         |

...      |          |        |         |

am    |          |        |         |

      -----------------------------------------------

Формат команды: aKq, где:

a  - новое содержание текущей ячейки (новый символ внешнего алфавита, который заносится в текущую ячейку),

K  - команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп)

q - новое внутренне состояние машины Тьюринга

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

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

 Работа машины на основании заданной программы происходит следующим образом.

Предположим, что в данный момент времени машина Тьюринга находится во внутреннем состоянии q[i], а в обозреваемой кареткой ячейке ленты находится символ a[j].

Тогда машина переходит к выполнению команды aKq в ячейке, на пересечении столбца q[i] и строчки a[j]:

1) в текущую секцию ленты заносится новый символ a.

2) происходит сдвиг каретки влево (K = влево),  или сдвиг каретки вправо (K = вправо), или происходит остановка машины (K = стоп).

3) машины переходит в новое внутреннее состояние q.

Возможные случаи останова машины Тьюринга:

1) в ходе выполнения программы машина дойдет до выполнения команды остановки;

программа в этом случае считается выполненной, машина останавливается - происходит результативная остановка.

2) машина никогда не останавливается, происходит зацикливание.

См. также:

Устройство машины Тьюринга.

содержание


Главное меню
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Главное меню

Под текущей машиной понимается машина Поста или машина Тьюринга, в зависимости от того, какая из них является активной в данный момент. Файл машины Поста имеет расширение *.pst, а файл машины Тьюринга - *.tur

(МП) - данный пункт меню виден только в машине Поста.

(МТ) - данный пункт меню виден только в машине Тьюринга.

Файл

Новый - создает новый файл текущей машины с именем 'Без имени'

Открыть - загружает ранее сохраненный файл текущей машины

Сохранить - сохраняет файл текущей машины на диск

Сохранить как - сохраняет файл текущей машины на диск с новым именем

Выход - выход из программы

Интерпретатор - переход на соответствующую машину:

Машина Поста

Машина Тьюринга

Вид - прячет/ показывает соответствующие компоненты программы:

Панель инструментов

Условие задачи

Строка состояния

Команды

Каретка влево - сдвиг каретки влево на одну ячейку

Каретка вправо - сдвиг каретки вправо на одну ячейку

Поставить/ удалить метки (МП) - отметить/ удалить метки в выделенных ячейках ленты

Отметить символ на ленте (МТ) - занести текущий символ внешнего алфавита в выделенные ячейки ленты

Изменить символ (МТ) - изменить значение в выделенных ячейках ленты

Очистить - очищает содержимое соответсвующих компонентов программы:

  • Условие задачи

  • Информационную ленту

  • Таблицу

  в МТ для очистки таблицы полностью нужно очистить внешний алфавит

  • Столбец

  • Строку

  • Внешний алфавит (МТ)

  • Комментарии (МТ)

  • Все

Манипуляции со строками и столбцами в таблице:

Удалить столбец (МТ)

Вставить столбец (МТ)

Добавить столбец (МТ)

Удалить строку (МП)

Вставить строку (МП)

Добавить строку (МП)

в МТ строки добавляются (удаляются) добавлением (удалением) символов во внешнем алфавите

Запомнить ленту - запоминает ленту

Восстановить ленту - восстанавливает запомненную ленту

работают отдельно(независимо) для МП и МТ

Пуск

Запустить - начинает выполнение программы (для МП с команды номер 1, для МТ с состояния q0)

Пауза - приостановить  выполнение программы (затем можно продолжить выполнение с данного места)

Пошагово - пошаговое выполнение программы

Прервать - прервать выполнение программы (продолжить выполнение с прерванного места нельзя)

Скорость - изменяет скорость выполнения программы

Очень быстро

Быстро

Средне

Медленно

Очень медленно

Помощь

Справка - вызов справки

О программе - информация о программе Algo2000

содержание


Информационная лента машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Информационная лента машины Поста

Лента состоит из 1999 ячеек, нумерация от -999 до 999.

Ячейка с толстой рамкой, находящаяся  в центре ленты  - каретка.

Всплывающее меню ленты вызывается при щелчке правой кнопкой мыши на ленте.

При получении фокуса лентой на ней появляется курсор (синий прямоугольник).

Его можно сдвигать по ленте вправо и влево клавишами управления курсором.

Удерживая клавишу Shift и нажимая клавиши "Влево"/ "Вправо" можно выделить несколько ячеек.

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

Метки ставятся/ удаляются в ячейках, которые выделены.

Это можно сделать несколькими способами (лента должна быть сфокусирована):

 • клавишей "Пробел"

 • щелкнуть мышью на кнопку "V" на панели инструментов

 • выбрать пункт главного или всплывающего меню "поставить/ удалить метки"

 • двойным щелчком мыши (в этом случае изменение происходит только в одной ячейке).

Клавиши управления курсором "Вверх" или "Вниз" ставят курсор в каретку.

"Home" - курсор в начало видимой части ленты.

"End"  - курсор в конец  видимой части ленты.

"Ctrl" + "Влево" - сдвиг каретки влево

"Ctrl" + "Вправо" - сдвиг каретки вправо

Кнопки со стрелкой слева и справа от ленты - прокрутить каретку соответственно влево и вправо

Кнопки со стрелкой и вертикальной палочкой слева и справа от ленты - прокрутить каретку соответственно до крайней левой отмеченной ячейки и до крайнеи правой отмеченной ячейке.

Номера этих ячеек указываются в строке состояния как мин и макс соответственно.

Можно непосредственно поставить каретку в нужную ячейку, указав ее номер в редакторе над кареткой.

Ленту можно запомнить (пункт меню Команда/ Запомнить ленту) и затем восстановить (Команда/ Восстановить ленту).

См. также:

Устройство машины Поста

содержание


Таблица машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Таблица машины Поста

В нее непосредственно вписывается алгоритм решения задачи.

В столбце "Номер" формируются номера команд алгоритма, начиная с 1, с шагом 1.

В столбце "Команды" указываются команды машины Поста.

Они выбираются из выпадающего по нажатию клавишы "Enter" или щелчку мыши списка.

В столбце "Отсылка" указываются номера отсылок, т.е. номер строки, которая должна выполняться следующей. Значения в этом столбце не должны быть меньше 1 и больше номера последней команды.

В столбце "Комментарии" можно писать различные пояснения, а можно ничего не писать. При выполнении этот столбец игнорируется.

Чтобы удалить, вставить, добавить строки, очистить строки или столбцы воспользуйтесь соответствующими пунктами главного или всплывающего меню или панелью инструментов.

содержание


Исполнение алгоритма машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Исполнение алгоритма машины Поста

Запуск алгоритма на исполнение:

 • пункт главного меню Пуск/ Запустить

 • кнопка запустить на панели инструментов

При этом выполнение программы будет идти до тех пор, пока не встретиться команда стоп или не возникнет какая- нибудь ошибка.

Приостановить выполнение:

 • пункт главного меню Пуск/ Пауза

 • кнопка пауза на панели инструментов

Если выполнение не было приостановлено, то оно всегда начинается с первой команды алгоритма.

Если была нажата пауза, то можно продолжить выполнение  с той команды, на которой машина остановилась.

Программу можно выполнить по шагам:

 • пункт главного меню Пуск/ Пошагово

 • кнопка пошагово на панели инструментов

При этом выполнится очередная команда и выполнение приостановится.

Полностью прервать выполнение программы:

 • пункт главного меню Пуск/ Прервать

 • кнопка прервать на панели инструментов

Регулировать скорость выполнения:

 • пункт главного меню Скорость

См. также:

Порядок работы машины Поста.

содержание


Ошибки машины Поста
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста

При возникновении этих ошибок происходит прерывание исполнения алгоритма.

 • Не указана команда

 • Не указана отсылка

 • Неверно указан номер отсылки

 • Команды с таким номером не существует

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

 • Нельзя стереть метку, где ее нет

 • Ошибка чтения файла

 • Ошибка записи файла

содержание


МП Не указана команда
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: не указана команда

При выполнении программы машина Поста дошла до такой строки таблицы, в которой не указана команда.

См. также:

Другие ошибки машины Поста

содержание


МП Не указана отсылка
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: не указана отсылка

При выполнении программы машина Поста дошла до такой строки таблицы, в которой не указана отсылка.

См. также:

Другие ошибки машины Поста

содержание


МП Неверно указан номер отсылки
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: неверно указан номер отсылки

Номер отсылки - это всегда натуральное число.

Для команды передачи управления нужно указать две отсылки разделенных запятой.

Для команды останова номер отсылки можно не указывать.

См. также:

Другие ошибки машины Поста

содержание


МП Команды с таким номером не существует
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: команды с таким номером не существует

Отсылка указывает на несуществующую команду

Значение отсылки не должно быть меньше 1 и больше номера последней команды.

См. также:

Другие ошибки машины Поста

содержание


МП Нельзя ставить метку, где она уже есть
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: нельзя поставить метку, где она уже есть

Эта команда считается невыполнимой.

См. также:

Система команд машины Поста

Другие ошибки машины Поста

содержание


МП Нельзя стереть метку, где ее нет
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: нельзя стереть метку, где ее нет

Эта команда считается невыполнимой.

См. также:

Система команд машины Поста

Другие ошибки машины Поста

содержание


МП Ошибка чтения файла
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: ошибка чтения файла

Возможные причины:

  • это файл не машины Поста

  • это файл машины Поста, но был испорчен

  • какая- то другая причина

См. также:

Другие ошибки машины Поста

содержание


МП Ошибка записи файла
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Поста: ошибка записи файла

Возможные причины:

  •  диск защищен от записи

  •  не вставлена дискета

  •  не хватает места на диске

  •  какая- то другая причина

См. также:

Другие ошибки машины Поста

содержание


Внешний алфавит
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Внешний алфавит

Это редактор для введения, отображения и хранения символов внешнего алфавита машины Тьюринга.

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

Каждый символ можно указать только один раз. Между символами могут быть пробелы.

Символ "Пробел" присутствует во внешнем алфавите всегда по умолчанию.

Если редактор "внешний алфавит" не виден, выберите пункт меню "Вид/ Внешний алфавит",

повторный выбор прячет редактор.

После окончания ввода внешнего алфавита формируется первый столбец таблицы: он заполняется символами внешнего алфавита в том же порядке.

При редактировании внешнего алфавита автоматически изменяется таблица: вставляются, удаляются или меняются местами строки.

При очистке "внешнего алфавита", очищается вся таблица.

См. также:

Устройство машины Тьюринга

содержание


Информационная лента машины Тьюринга
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Информационная лента машины Тьюринга

Лента состоит из 999 ячеек, нумерация от 1 до 999.

Ячейка с толстой рамкой, находящаяся  в центре ленты  - каретка.

Всплывающее меню ленты вызывается при щелчке правой кнопкой мыши на ленте.

Перед тем как заполнять ленту нужно ввести внешний алфавит.

При получении фокуса лентой на ней появляется курсор (синий прямоугольник).

Его можно сдвигать по ленте вправо и влево клавишами управления курсором.

Удерживая клавишу Shift и нажимая клавиши "Влево"/ "Вправо" можно выделить несколько ячеек.

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

Текущий символ внешнего алфавита - символ который отображен на кнопке "Отметить символ на ленте" панели инструментов. Если на кнопке стоит надпись "нет", значит текущим символом является пробел. Изменить текущий символ можно выбрав другой из списка, выпадающего по щелчку мыши на кнопке с направленной вниз стрелочкой ("Изменить символ") или выбрав пункт меню "Команды/Изменить символ". Новый символ сразу помещается на кнопку на панели инструментов, а также записывается в выделенные ячейки ленты.

Символы внешнего алфавита ставятся в ячейках, которые выделены.

Это можно сделать несколькими способами (лента должна быть сфокусирована):

 • нажать клавишу клавиатуры компьютера с соответствующим символом

 • выбрать пункт главного или всплывающего меню "Изменить символ" и выбрать символ из списка.

Записать текущий символ:

 • щелкнуть мышью на кнопку "Отметить символ на ленте" на панели инструментов

 • выбрать пункт главного или всплывающего меню "Отметить символ на ленте"

 • двойным щелчком мыши (в этом случае изменение происходит только в одной ячейке).

Удалить символ в выделенных ячейках:

 • клавиша "Пробел"

 • выбрать пункт главного или всплывающего меню "Изменить символ" и выбрать "нет" из списка.

Клавиши управления курсором "Вверх" или "Вниз" ставят курсор в каретку.

"Home" - курсор в начало видимой части ленты.

"End"  - курсор в конец  видимой части ленты.

"Ctrl" + "Влево" - сдвиг каретки влево

"Ctrl" + "Вправо" - сдвиг каретки вправо

Кнопки со стрелкой слева и справа от ленты - прокрутить каретку соответственно влево и вправо

Кнопки со стрелкой и вертикальной палочкой слева и справа от ленты - прокрутить каретку соответственно до крайней левой отмеченной ячейки и до крайнеи правой отмеченной ячейке.

Номера этих ячеек указываются в строке состояния как мин и макс соответственно.

Можно непосредственно поставить каретку в нужную ячейку, указав ее номер в редакторе над кареткой.

Ленту можно запомнить (пункт меню Команда/ Запомнить ленту) и затем восстановить (Команда/ Восстановить ленту).

См. также:

Устройство машины Тьюринга

содержание


Таблица машины Тьюринга
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Таблица машины Тьюринга

В нее непосредственно вписывается алгоритм решения задачи.

Прежде, чем вводить алгоритм, нужно ввести внешний алфавит.

В ячейках верхней строки записываются символы внутреннего алфавита: Q1,Q2...Qn.

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

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

Формат команды машины Тьюринга: aKq, где:

a  - новое содержание текущей ячейки (новый символ внешнего алфавита, который заносится в текущую ячейку),

K  - команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп)

q - новое внутренне состояние машины Тьюринга

Чтобы ввести команду в ячейку нужно:

1) Ввести символ внешнего алфавита

2) Ввести одну из команд лентопротяжного механизма:

    • "Влево" - ввести левую угловую скобку  "<"

    • "Вправо" - ввести правую угловую скобку ">"

    • "Cтоп" - ввести восклицательный знак "!"

3) Ввести номер нового внутреннего состояния. Нужно ввести только цифру, букву  Q вводить не надо.

Пример: чтобы ввести команду

нужно последовательно набрать на клавиатуре символы:  #  >  1 , где:

# - указание машине Тьюринга записать символ "#" в текущую ячейку ленту

> - указание машине Тьюринга сдвинуть каретку вправо

1 - указание машине Тьюринга перейти в новое внутреннее состояние Q1

Пробелы в команде игнорируются.

Чтобы указать в команде в качестве символа внешнего алфавита "пробел", нужно ввести в ячейку символ подчеркивания "_", пробел или ввести сразу команду лентопротяжного механизма.

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

Чтобы удалить, вставить, добавить столбцы, очистить строки или столбцы воспользуйтесь соответствующими пунктами главного или всплывающего меню или панелью инструментов.

содержание


Исполнение алгоритма машины Тьюринга
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Исполнение алгоритма машины Тьюринга

Запуск алгоритма на исполнение:

 • пункт главного меню Пуск/ Запустить

 • кнопка запустить на панели инструментов

При этом выполнение программы будет идти до тех пор, пока не встретиться команда стоп или не возникнет какая- нибудь ошибка.

Приостановить выполнение:

 • пункт главного меню Пуск/ Пауза

 • кнопка пауза на панели инструментов

Если выполнение не было приостановлено, то оно всегда начинается с нулевого внутреннего состояния Q0.

Если была нажата пауза, то можно продолжить выполнение  с той команды, на которой машина остановилась.

Программу можно выполнить по шагам:

 • пункт главного меню Пуск/ Пошагово

 • кнопка пошагово на панели инструментов

При этом выполнится очередная команда и выполнение приостановится.

Полностью прервать выполнение программы:

 • пункт главного меню Пуск/ Прервать

 • кнопка прервать на панели инструментов

Регулировать скорость выполнения:

 • пункт главного меню Скорость

См. также:

Порядок работы машины Тьюринга.

содержание


Ошибки машины Тьюринга
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга

При возникновении этих ошибок происходит прерывание исполнения алгоритма.

 • Данного символа нет в алфавите

 • Не указана команда

 • Неверная запись команды

 • Состояние Qi отсутствует

 • Ошибка чтения файла

 • Ошибка записи файла

содержание


МТ Данного символа нет в алфавите
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга: данного символа нет в алфавите

Встреченный в команде символ не содержится во внешнем алфавите.

См. также:

Внешний алфавит

Другие ошибки машины Тьюринга

содержание


МТ Не указана команда
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга: не указана команда

При выполнении программы машина Поста дошла до такой ячейки таблицы, в которой не указана команда.

См. также:

Команды машины Тьюринга

Таблица машины Тьюринга

Другие ошибки машины Тьюринга

содержание


МТ Неверная запись команды
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга: неверная запись команды

Команда машины Тьюринга записана неверно.

См. также:

Команды машины Тьюринга

Таблица машины Тьюринга

Другие ошибки машины Тьюринга

содержание


МТ Состояние Qi отсутствует
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга: cостояние Qi отсутствует

Указанное в команде внутреннее состояние машины Тьюринга отсутствует.

См. также:

Команды машины Тьюринга

Таблица машины Тьюринга

Другие ошибки машины Тьюринга

содержание


МТ Ошибка чтения файла
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга: ошибка чтения файла

Возможные причины:

  • это файл не машины Тьюринга

  • это файл машины Тьюринга, но был испорчен

  • какая- то другая причина

См. также:

Другие ошибки машины Тьюринга

содержание


МТ Ошибка записи файла
Algo2000

Интерпретатор машины Поста и машины Тьюринга

Ошибки машины Тьюринга: ошибка записи файла

Возможные причины:

  •  диск защищен от записи

  •  не вставлена дискета

  •  не хватает места на диске

  •  какая- то другая причина

См. также:

Другие ошибки машины Тьюринга

содержание