Основы построения ЭВМ. Основные определения. Вычислительная машина. Функция Аккермана – тест для компьютера

<1>

  ВВЕДЕНИЕ.

1. Основы построения ЭВМ. Основные определения.

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

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

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

Основой построения (появления) ЭВМ явилась следующая   совокупность (последовательность) формализаций:

a)  множество задач (по-видимому, все задачи обработки информации) может быть решено в численном виде; ход их решения представляет последовательность сравнительно простых действий над числами;

b)  числа могут быть представлены в различных системах счисления и зашифрованы (закодированы);

c)  действиям   над числами соответствуют логические преобразования над кодами;

d)  коды могут быть представлены в виде электрических сигналов;

e)  разработаны методы логического преобразования кодов, в виде обработки электрических сигналов, однозначно соответстующие действиям над числами.

<2>

Любая современная наука стремится поставить решение своих задач на формальные рельсы. Тем самым удаётся конструктивнее решать основные научные проблемы, задачи анализа и синтеза. Следовательно, нужно уметь формально описывать и преобразовывать специальную информацию. Наиболее развитой наукой в этом смысле является математика. Она имеет богатые средства для описания задач с помощью формальных понятий и средств, т.е. набор операций по их преобразованию.

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

Такой «инструкцией» в вычислительной технике является алгоритм.

Большой вклад в теорию развития алгоритмов и формулирования четкого понятия алгоритма внес Тьюринг. Его гипотетическая (абстрактная) машина формализовала понятие алгоритма (1936 г.). Он доказал, что любой алгоритм в принципе может быть реализован при помощи универсального дискретного устройства. Предложенная им схема абстрактного автомата получила название машины Тьюринга. Параллельно с Тьюрингом сходную модель абстрактной вычислительной машины предложил и исследовал Пост. Тем самым теоретически была доказана возможность и целесообразность создания автоматической ЦВМ. Необходимо было ждать только подходящей технической базы.

Работы Тьюринга и Поста были связаны с проблемой вычислимости функций. В качестве решения этой проблемы был сформулировано положение, получившее наименование тезис Чёрча.

Кроме моделей абстрактных вычислителей математиками были предложены алгоритмически трудно формализуемые функции. Самой знаменитой из них является функция Аккермана.

<3>

Функция Аккермана – тест для компьютера.

Функция Аккермана индуктивно задана на парах неотрицательных целых чисел:

;

где m, n больше или равно 0.

Следовательно:

;

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

Функция Аккермана одной переменной:

Особую оригинальную конструкцию формального представления алгоритма создал советский математик Л.А. Марков (1954 г.).

Идеи Тьюринга, Поста, Маркова представляют тот фундамент, на котором строится здание теоретического программирования, строится теория алгоритмов, и развиваются другие направления, имеющие прямое отношение к информатике, если под этим понимать предмет, объединяющий вычислительную технику и математику, программное оборудование ЭВМ.

Свойства алгоритмов:

1. Определенность (однозначность), не оставляющая места произволу.

2. Массовость, т.е. возможность исходить из любых исходных данных.

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

<4>

Основные требования к записи алгоритмов:

–  наглядность;

–  обозримость;

–  однозначность толкования;

–  обеспечение различной степени детализации.

Используются следующие формы представления алгоритма:

1.  Текстуальная.

2.  Операторная.

3.  Графическая.

4.  В терминах алгоритмического языка.

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