Машина поста (мп)

Простейшей ЦМ (теоретическая) является машина Поста.

Машина Поста — это хотя и абстрактная (т. е. не существующая в арсенале действующей техники), но зато очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию.

Машина Поста - математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит:

• Из неограниченной в обе стороны ленты, разделенной на ячейки;

• Из головки чтения/записи, которая может перемещаться вдоль ленты и управляется программой на специальном языке из шести команд.

Доказано, что классы алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают. Машина Поста по архитектуре и принципам работы похожа на машину Тьюринга. И машина Тьюринга, и машина Поста эквивалентны по своим возможностям. Разработаны они практически в одно и то же время (в 1936 г.) независимо друг от друга.

Структура такой машины предполагает что:

• память бесконечна

• данные распложены в последовательных ячейках

• в каждой ячейке памяти «0» или «1»

• преобразование информации происходит шагами

• каждый шаг одна команда взаимодействия с текущей ячейкой.

У машины Поста пять операций:

1. запись «1» в ячейку;

2. запись «0» в ячейку;

3. выбрать левую по порядку ячейку;

4. выбрать правую по порядку ячейку;

5. определить, что в ячейке «0» или «1».

МП более всего соответствует современным процессорам и языкам программирования. Уже только этим машина Поста привлекает к себе, так как, с одной стороны, демонстрирует эффективность и работоспособность идеи, которой уже более полусотни лет, с другой — ее рассмотрение и анализ дают понимание причин сложившегося застоя в развитии программных систем. Сегодня, например, весьма актуальной становится проблема распараллеливания процессов, которую с помощью машины Поста (да, кстати, и Тьюринга тоже) решить сложно или даже невозможно, особенно если манипулировать «чистыми» абстрактными машинами. Возможно, проблема параллелизма во времена их создания была не столь актуальной, как ныне, а потому при их «изобретении» и не учитывалась.

Рис. 2. Машина Поста

Машина Поста состоит из памяти и устройства управления, которое, следуя современной терминологии, будем называть процессором (рис. 2). Память в машине представлена разбитой на ячейки (клетки) бесконечной, или неограниченно растущей в обе стороны, лентой. Ячейки пронумерованы целыми числами ..., -3, -2, -1, 0, 1, 2, 3... Каждая ячейка может быть либо пустой, либо обозначенной меткой (например, V). Метке может соответствовать и запись в ячейку значения нуля или единицы.

Машина Тьюринга - математическое построение, предназначенное для уточнения понятия алгоритма. Машина Тьюринга состоит:

- из неограниченной в обе стороны ленты, разделенной на ячейки;

- из головка чтения/записи, которая может перемещаться вдоль ленты.

Программа для машины Тьюринга, задается в виде таблицы, определяющей команды для головки. Классификация эвм

ЭВМ делят на четыре группы:

1. ЭВМ общего применения (универсальные), которые делятся на:

• большие ЭВМ высокой производительности;

• средние ЭВМ;

• ЭВМ малой производительности.

2. ЭВМ проблемно-ориентированные – используются в относительно узкой области науки и техники. Эти ЭВМ делятся на:

• мини-ЭВМ;

• микро-ЭВМ.

3. Специализированные ЭВМ:

• управляющие ЭВМ;

• вычислительные ЭВМ.

4. ПЭВМ – персональные ЭВМ.