Алгоритмическая полнота ЭВМ

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

Огромные возможности ЭВМ раньше всего удалось использовать там, где уже была подготовлена математическая база: в научных и инженерных расчетах в области механики, физики, астрономии.

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

Алгоритмическая полнота обеспечила ЭВМ выход за пределы научных и инженерных вычислений – к проблемам экономики и управления.

Понятие о формальных языках и порождающих грамматиках. Описание алгоритмических языков с помощью порождающих грамматик.

Формальная грамматика или просто грамматика в теории формальных языков – способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Порождающие грамматики задают правила, с помощью которых можно построить любое слово языка.

Терминал (терминальный символ) – объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»).

В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII – латинские буквы, цифры и спец. символы.

Нетерминал (нетерминальный символ) – объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.