Машина Поста. Определения и построение.

Абстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. американским математиком Эмилем Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой универсальные исполнители, являющиеся полностью детерминированными, и позволяющие "вводить" начальные данные и после выполнения программ "читать" результат. Машина Поста менее популярна, хотя она значительно проще машины Тьюринга. С ее помощью можно вести обучение первым навыкам составления программ для ЭВМ.

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

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

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

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

Доказано, что классы алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.

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

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

Билет № 31

1. Программное обеспечение информационных технологий: методо-ориентированное программное обеспечение, прикладное программное обеспечение.

Современному компьютеру никак нельзя обойтись без программ. Ведь именно программы определяют возможности компьютера: что он будет делать — поможет свести бухгалтерский баланс или позволит побродить по всемирной сети Интернет. Большинство программ правильнее было бы называть программными продуктами, ведь зачастую на их создание требуется не меньше затрат, чем на производство самого компьютера. Практически любая программа, если это специально не оговорено, является коммерческим продуктом, который продается наравне с компьютерами.

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

Базовое (системное) ПО организует процесс обработки информации в компьютере и обеспечивает нормальную рабочую среду для прикладных программ. Базовое ПО настолько тесно связано с аппаратными средствами, что его иногда считают частью компьютера.

Прикладное ПО непосредственно нацелено на решение профессиональных задач пользователя.

Дата добавления: 2015-10-24