Алгоритмическая машина Поста

Основное

Машина Поста - машина, созданная Эмилем Постом в 1936-1937 гг. Основное отличие алгоритмической машины Поста от машины Тьюринга - работа с двоичным кодом. Именно поэтому машина Поста представляет наибольший интерес, так как все современные компьютеры работаю с двоичным кодом.

(Ниже представлена фотография Эмиля Поста)
Big image

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

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

Действия автомата:
1. Распознать пустая ли ячейка или же в ней содержится метка.
2. Стереть метку в текущей ячейке.
3. Поставить метку в текущей ячейке.

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

Назначение машины Поста - производить любые преобразования на информационной ленте.

Программирование на машине Поста

1. "<" - смещение головки автомата влево, переход к следующей команде.
2. ">" - смещение головки автомата вправо.
3. "? х, y" - условие. Если ячейка пуста - переход к команде "х", если в ячейке стоит метка - переход к команде "y"
4. "1" - запись метки в текущую ячейку.
5. "0" стирание метки в текущей ячейке.
6. "." - остановка программы.

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

В нормальном алгоритме Маркова используется понятие подстановки одного символа на место другого. Алгоритм определяет, какие замены символов в исходном слове следует производить, и в каком порядке это делать.

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

(Ниже представлена фотография А. А. Маркова)
Big image