Об алгоритмической полноте некоторых языков программирования (1106265)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

А.А. ВылитокОб алгоритмической полноте некоторых языков программированияВ данной заметке рассматривается вопрос, являются ли алгоритмически полнымиследующие языки программирования:1) машинный язык для УМ-3 (трехадресная учебная машина);2) язык ассемблера (например, MASM без макросов);3) язык Паскаль (стандарт ISO);4) язык Си (стандарт ISO).Алгоритмическая полнота языка (или полнота по Тьюрингу) предполагает, что нанем можно выразить любой алгоритм, представимый машиной Тьюринга.

Длядоказательства полноты языка по Тьюрингу достаточно показать, как на данном языкесмоделировать работу машины Тьюринга. Отметим, что кроме моделированияфункциональных возможностей машины по чтению, записи, сдвигу головки на лентеи смены состояния, важно, чтобы язык никак не ограничивал потенциальную длинуленты, поскольку известно, что существуют задачи сколь угодно ёмкие по памяти (хотяконкретная реализация языка вправе накладывать ограничения, но это будут ограниченияреализации, а не самого языка). Иными словами, в языке должна присутствоватьабстракция потенциальной бесконечности.Машинный язык для УМ-3 не является алгоритмически полным. Это следует изтого, что формат команд УМ-3 предполагает адреса фиксированного размера, а значитразмер адресного пространства (памяти) ограничен самим языком и потенциальнобесконечную ленту в памяти смоделировать невозможно.

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

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

Целые типыограничены (конечное множество значений), указатель отождествляется с адресом,постулируется возможность хранить адрес в целочисленной переменной (int или long —зависит от реализации), откуда следует ограниченность множества значений указателей,а стало быть, и ограниченность адресного пространства Си-машины. То есть язык Си, каки язык ассемблера, ориентирован на архитектуру с конечной памятью. Файл не являетсятипом данных языка Си, в отличие от Паскаля. Это вещь из окружения, для работыс которой есть операции над потоками в виде набора библиотечных функций.

Тип fpos_t,принятый в стандарте Си для позиционирования файлов, постулируется как «отличный отмассива тип данных (object type)». Следовательно, множество значений этого типаконечно, а значит, максимальная длина файла в языке Си ограничена сверху.Для иллюстрации понятия алгоритмического языка в курсе «Алгоритмыи алгоритмические языки» более подходит язык Паскаль, ибо он не ограничен какой-либомашинной архитектурой (и его алгоритмическая полнота не вызывает сомнений),в отличие от Си, явно нацеленного на архитектуру современных вычислительных машин,обусловливающую семантические ограничения множества значений типов данных. ЯзыкСи по своей сути — «высокоуровневый ассемблер»: по форме он похож на Паскаль, а посмыслу — на язык ассемблера.

Такой язык хорошо подходит для задач курса«Операционные системы», когда студенты уже знакомы с «Архитектурой ЭВМ и языкомассемблера».Можно указать и другие алгоритмически полные языки, например, Лисп, Пролог,Рефал, Хаскель и им подобные, «пришедшие из математики»..

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы