Теория автоматов

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

Теория автоматов тесно связана с теорией алгоритмов, а само понятие автомат основывается на математическом понятии алгоритма. Алгоритмом называется конечная система правил, по которым совершается преобразование дискретной информации. С понятием алгоритма вы, сами того не ведая, знакомились еще в школе. Из курса алгебры, например, хорошо известны алгоритмы (правила) решения квадратных уравнений, систем линейных уравнений, раскрытия скобок и приведения подобных членов в буквенных выражениях и т. п. Но алгоритмы широко распространены и за пределами математики. Если сформулировать все правила, которые употребляет опытный переводчик для переводов, скажем, с английского языка на русский, мы получим не что иное, как алгоритм англо-русского перевода.

Если элементарные правила шахматной игры дополнить системой стратегических правил, позволяющих в каждой позиции находить единственный, наилучший (с точки зрения данной системы правил) ход, получится алгоритм игры в шахматы.

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

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

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

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

Основная задача теории автоматов - разработка методов создания преобразователей информации для осуществления тех или иных алгоритмов, например машин для контроля и управления производственными процессами в различных отраслях промышленности, для автоматического перевода с одного языка на другой, для игры в шахматы и т. п.

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

Чтобы изменить программу, не нужно переделывать машину, достаточно пропустить через вводное устройство набор бумажных карточек с пробитыми в соответствующих местах отверстиями - перфокарты или ленту с отверстиями - перфоленту. Так вводится в машину новая программа, настраивающая ее на новый вид работы.

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

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

перейти к началу страницы