В чём заключается принцип работы машины Поста?

Принцип работы машины Поста заключается в том, что работа машины определяется программой, состоящей из конечного числа строк. ru.wikipedia.org ru.ruwiki.ru Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). ru.wikipedia.org videouroki.net

Машина Поста состоит из каретки (или считывающей и записывающей головки) и бесконечной в обе стороны ленты, разделённой на ячейки. ru.wikipedia.org videouroki.net Каждая ячейка ленты может находиться в двух состояниях — быть либо пустой (0), либо помеченной меткой (1). ru.wikipedia.org videouroki.net

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

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

Работа машины Поста определяется шестью типами команд: ru.wikipedia.org

1. V j — поставить метку, перейти к j-й строке программы. ru.wikipedia.org ru.ruwiki.ru
2. X j — стереть метку, перейти к j-й строке. ru.wikipedia.org ru.ruwiki.ru
3. ← j — сдвинуться влево, перейти к j-й строке. ru.wikipedia.org ru.ruwiki.ru
4. → j — сдвинуться вправо, перейти к j-й строке. ru.wikipedia.org ru.ruwiki.ru
5. ? j1; j2 — если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке. ru.wikipedia.org ru.ruwiki.ru
6. ! — конец программы («стоп», останов). ru.wikipedia.org ru.ruwiki.ru

После запуска программы возможны варианты: работа может закончиться невыполнимой командой, командой «стоп» или никогда не закончиться. ru.wikipedia.org videouroki.net