Машина Поста
Машина Поста
Машина Поста - математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит:
- из неограниченной в обе стороны ленты, разделенной на ячейки;
- из головка чтения/записи, которая может перемещаться вдоль ленты и управляется программой на специальном языке из шести команд.
Доказано, что классы алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.
Источник: Финансовый словарь проекта «Финам», проект www.finam.ru/dictionary