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

Основные принципы работы машины Поста заключаются в следующем:

• Наличие бесконечной ленты, разделённой на ячейки. videouroki.net infourok.ru Каждая ячейка может быть либо пустой (0), либо помеченной меткой (1). videouroki.net ru.ruwiki.ru Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты, которое меняется в процессе работы машины. infourok.ru
• Возможность передвижения каретки вдоль ленты влево и вправо. infourok.ru Когда она неподвижна, она стоит против ровно одной ячейки ленты, обозревает её. infourok.ru За единицу времени каретка может совершить одно из трёх действий: стереть метку, поставить метку, совершить движение на соседнюю ячейку. infourok.ru
• Работа по программе, состоящей из конечного числа строк. videouroki.net ru.ruwiki.ru В каждой команде указана строка, на которую нужно перейти. ru.ruwiki.ru Если переход не указан, то переход происходит на следующую строку. ru.ruwiki.ru
• Недопустимость некоторых действий, которые приводят к аварийной остановке машины. infourok.ru К ним относятся попытка записать метку в заполненную ячейку, стереть метку в пустой ячейке, а также бесконечное выполнение (зацикливание). infourok.ru

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