turingmarkov

Turing machine and markov algorithm emulator.


License
WTFPL
Install
pip install turingmarkov==0.1.1

Documentation

turingmarkov

Emulator of turing machine and markov algorithm.

TODO

  • Нормальные машины Тьюринга
  • Пустые слова в НАМ

Quickstart

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

# python3 -m pip install --upgrade turingmarkov

Данная программа работает как интерпретатор или компилятор машины Тьюринга и нормальных алгоритмов Маркова. Простейший способ запустить программу - набрать в консоли:

$ turingmarkov run turing [имя файла].turing
$ turingmarkov run markov [имя файла].markov

Где [имя файла] - файл с исходным кодом машины Тьюринга или алгоритма Маркова соответствено. Подробнее про формат файлов читайте ниже.

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

Ограничения: в НАМ пробельные символы игнорируются, МТ не работает для пустых строчек.

Компиляция

Также программа может работать в режиме компилятора и перерабатывать формальное описание алгоритма в программу на Python.

$ turingmarkov compile turing [имя файла].turing
$ turingmarkov compile markov [имя файла].markov

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

Взаимодействие с системой ejudge

Для установки в систему ejudge:

  1. Установите пакет через python3 -m pip install --upgrade turingmarkov.
  2. Залогиньтесь под пользователем ejudge.
  3. Склонируйте репозиторий с исходными кодами.
  4. Находясь в корневом каталоге репозитория, выполните команду make install-ejudge-binding.
  5. Выполните команду ejudge-configure-compilers и убедитесь, что компиляторы Turing Machine и Markov Algorithm найдены (показаны их версии).
  6. Перезапустите ejudge (через ejudge-control).

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

Краткие теоретические сведения

Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

Описание

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

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

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

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина.

Они имеют вид: a[i],q[k] -> a[i1],d[j],q[k1] Если головка находится в состоянии q[k], а в обозреваемой ячейке записана буква a[i], то:

  1. В ячейку вместо a[i] записывается a[i1].
  2. Головка делает движение d[j], которое имеет три варианта: на ячейку влево L, на ячейку вправо R, остаться на месте N.
  3. Головка переходит в состояние q[k1].

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

Работа МТ состоит из однотипных тактов. Каждый такт состоит в выполнении одной команды. Предполагается, что первоначально МТ находится в состоянии 0. Таким образом, если задать информацию на ленте и положение головки, работа МТ определяется однозначно. Работа МТ считается завершенной, если выполнилась заключительная команда. Полученное последнее cодержимое ленты является результатом работы МТ.

В эмуляторе МТ для обозначения пустого символа используетя знак подчёркивания. Конечное состояние обозначается символом !.

Для записи правил используется таблица. Каждая строка символизирует состояние. Каждый столбец - обозреваемый символ из алфавита A. На пересечении столбца и строки записана правая часть правила, сотоящая из трех элементов a[i1],d[j],q[k1], разделенных запятыми. Символ или состояние могут быть пропущены - это означает, что они не меняются. Если вы уверены, что какой-то комбинации состояние+символ никогда не встретится, можете поставить в соответствующую клетку знак минус -, но тогда машина остановится с ошибкой, если ей будет нужно обработать это правило. Столбцы разделяются пробельными символами. Строки - символом переноса строки.

Примеры

Пример 1

К непустовму входному слову в алфавите {a, b, c} приписать справа букву a.

    a    b    c     _
0  ,R,  ,R,  ,R,  a,N,!

В начале МТ ищет правую границу входного слова, а затем пишет a в пустую ячейку и останавливается.

Пример 2

К числу, записанному в двоичной записи, добавить 1.

      0      1      _
0    ,R,    ,R,    ,L,1
1   1,N,!  0,L,   1,N,!

В начале МТ ищет правую границу входного слова, а затем переходит в состояние q1 и идёт влево, увеличивая разряды на 1, пока не встретит 0, либо пустой символ _.

Пример 3

Из входного слова в алфавите {a, b, c} удалить все буквы a.

      a      b     c      _      #
0    ,R,    ,R,   ,R,   #,L,1    -
1    ,L,    ,L,   ,L,    ,R,2   ,L,
2   _,R,   _,R,3 _,R,4   ,R,!  _,R,!
3    ,R,    ,R,   ,R,   b,L,1   ,R,
4    ,R,    ,R,   ,R,   c,L,1   ,R,

Так как МТ не позволяет менять некоторую подстроку на другую произвольную подстроку, при решении подобных задач используют приём построения новой копии слова. В начале МТ ставит символ # в конце слова, чтобы разграничить исходное слова от строящегося. Затем МТ циклически переносит по одному символу из начала входного слова в конец так, чтобы перенеслись все буквы, за исключением букв a. Таким образом, все буквы a просто стираются. По окончании работы МТ удаляет # и останавливается на новом слове. Команда ,R,! в состоянии 2 позволяет избежать зацикливания при пустом входном слове.

Нормальные алгоритмы Маркова

Краткие теоретические сведения

Нормальный алгоритм Маркова (НАМ) - один из стандартных способов формального определения понятия алгоритма. Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений.

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

Описание

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.

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

  1. Простыми формулами подстановки называются слова вида L-> D, где L и D — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки).
  2. Аналогично, заключительными формулами подстановки называются слова вида L => D, где L и D — два произвольных слова в алфавите алгоритма.

При этом предполагается, что вспомогательные буквы -> и => не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

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

Дана входная строка:

  1. Проверить формулы в порядке следования сверху вниз, присутствует ли левая часть формулы во входной строке.
  2. Если такой формулы не найдено, алгоритм останавливается.
  3. Если найдена одна или несколько формул, то самая верхняя из них используется для замены: самое левое вхождение левой части формулы во входной строке заменяется на правую часть формулы.
  4. Если только что примененная формула была терминальной, то алгоритм останавливается.
  5. Снова переходим к шагу 1.

Заметим, что после применения очередной формулы поиск следующей начинается с самой верхней формулы.

Примеры

Пример 1

В произвольном слове, состоящем из букв {a, b, c}, все подряд стоящие одинаковые буквы заменить одной буквой (например, слово abbbcaa преобразовать в abca). Схема НАМ. имеет вид:

aa -> a
bb -> b
cc -> c

Применение этой схемы с слову abbbcaa последовательно даст слова: abbbca, abbca и abca, после чего выполнение НАМ завершится.

Пример 2

Удвоить слово, состоящее из одинаковых символов (для определенности — x). Т.е. слово x надо преобразовать в xx, слово xx — в xxxx и т.д.

Схема НАМ для этого примера намного сложнее, чем для примера 1. Нельзя написать x -> xx, т.к. в этом случае на каждом шаге НАМ к слову будет добавляться символ x и этот процесс будет бесконечным. Необходимо контролировать удвоение каждого символа слова так, чтобы каждый символ удвоился только один раз. Для это введём маркер, с помощью которого будем обеспечивать контекст применения удваивающего правила.

#x -> xx#
#  =>
   -> #

Последнее правило вводит "маркер" # (или "курсор"), который с помощью первого правила "перескакивает" через текущий символ слова и удваивает его. Применение этой схемы, например, к слову "xx" последовательно даст слова (в скобках указан номер применяемой формулы подстановки):

(3) #xx
(1) xx#x
(1) xxxx#
(2) xxxx

Пример 3

Дано слово в алфавите {a, b, c}. Упорядочить буквы входного слова в лексикографическом порядке.

ba -> ab
ca -> ac
cb -> bc

References

  1. http://cmcmsu.no-ip.info/1course/alg.schema.mt.htm
  2. https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0
  3. https://en.wikipedia.org/wiki/Turing_machine
  4. http://cmcmsu.no-ip.info/1course/alg.schema.nam.htm
  5. https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
  6. https://en.wikipedia.org/wiki/Markov_algorithm