Алгоритмическая машина Поста
Основное
Машина Поста - машина, созданная Эмилем Постом в 1936-1937 гг. Основное отличие алгоритмической машины Поста от машины Тьюринга - работа с двоичным кодом. Именно поэтому машина Поста представляет наибольший интерес, так как все современные компьютеры работаю с двоичным кодом.
(Ниже представлена фотография Эмиля Поста)
(Ниже представлена фотография Эмиля Поста)
Устройство машины Поста
В машине Поста имеется бесконечная информационная лента, разделённая на ячейки. В каждой такой ячейке может либо находиться какой - либо знак (например, точка), либо отсутствовать. Вдоль этой ленты движется головка автомата, которая может передвигаться шагам.
Действия автомата:
1. Распознать пустая ли ячейка или же в ней содержится метка.
2. Стереть метку в текущей ячейке.
3. Поставить метку в текущей ячейке.
Если произвести замену меток на единицы, а пустых ячеек на нули, то мы сможем рассматривать информацию на ленте, как аналог представления информации в памяти компьютера.
Назначение машины Поста - производить любые преобразования на информационной ленте.
Действия автомата:
1. Распознать пустая ли ячейка или же в ней содержится метка.
2. Стереть метку в текущей ячейке.
3. Поставить метку в текущей ячейке.
Если произвести замену меток на единицы, а пустых ячеек на нули, то мы сможем рассматривать информацию на ленте, как аналог представления информации в памяти компьютера.
Назначение машины Поста - производить любые преобразования на информационной ленте.
Программирование на машине Поста
1. "<" - смещение головки автомата влево, переход к следующей команде.
2. ">" - смещение головки автомата вправо.
3. "? х, y" - условие. Если ячейка пуста - переход к команде "х", если в ячейке стоит метка - переход к команде "y"
4. "1" - запись метки в текущую ячейку.
5. "0" стирание метки в текущей ячейке.
6. "." - остановка программы.
2. ">" - смещение головки автомата вправо.
3. "? х, y" - условие. Если ячейка пуста - переход к команде "х", если в ячейке стоит метка - переход к команде "y"
4. "1" - запись метки в текущую ячейку.
5. "0" стирание метки в текущей ячейке.
6. "." - остановка программы.
Нормальные алгоритмы Маркова
В нормальном алгоритме Маркова используется понятие подстановки одного символа на место другого. Алгоритм определяет, какие замены символов в исходном слове следует производить, и в каком порядке это делать.
Доказано, что если задача является алгоритмически разрешимой, то для ней можно построить нормальный алгоритм Маркова.
(Ниже представлена фотография А. А. Маркова)
Доказано, что если задача является алгоритмически разрешимой, то для ней можно построить нормальный алгоритм Маркова.
(Ниже представлена фотография А. А. Маркова)