Понятие автомата.

Понятие алгоритма вводилось до сих пор чисто интуитивно. Понятие автомата позволяет уточнить понятие алгоритма. А это, в свою очередь, позволяет решить вопрос об алгоритмической разрешимости той или иной проблемы. В частности с помощью машины Тьюринга американским ученым Черчем (1903-1992) был получен результат при решении проблемы распознавания выводимости в математической логике: для любых заданных формул R и S в логическом исчислении определить существует ли дедуктивная цепочка, ведущая от R к S или нет.

Теорема Черча.

Проблема распознавания выводимости алгоритмически неразрешима.

Автоматы, изучаемые в последующих разделах, можно рассматривать как механизмы, состоящие из блока управления, который может пребывать в различных состояниях (внутренние состояния автомата), а также входного и выходного каналов. Входной канал воспринимает (считывает) сигналы из внешней среды, а выходной канал выдает сигналы во внешнюю среду. Природа состояний и сигналов безразлична, их можно рассматривать как некоторые символы (буквы), образующие соответственно алфавит состояний (или внутренний алфавит) – Q, входной алфавит – X, и выходной алфавит – Y. Каждая команда может быть записана в виде

(*)

где q_i , q_j – внутренние состояния автомата, x_r – входной символ, у_s – выходной символ.

Пусть на некотором такте t₀ блок управления установлен в состояние q_i, и входной канал воспринимает символ x_r. Если в программе имеется команда (*), то в этом же такте выходной канал выдает символ x_r, а к следующему такту t₀ + 1 блок управления перейдет в состояние q_j . Если такой команды нет, то автомат блокируется. В этом и заключается функционирование автомата. Множество внутренних состояний автомата является его внутренней памятью.

Таким образом, автомат – это пятерка (Q, X, Y, Ψ, Φ), где Q, X, Y – алфавиты, Ψ – функция переходов отображение Q X в Q, Φ – функция выходов (отображение Q X в Y). Пусть зафиксировано некоторое состояние автомата. Тогда рекуррентные соотношения

где q(t), q(t + 1) Q, x(t) X, y(t) Y, дополненные начальным условием q(1) = q₀, задают оператор T, который преобразует всякую конечную последовательность входящих символов

x = x(1) x(2) ...x(r) в некоторую последовательность выходных символов

y = Tx = y(1) y(2) .... y(r) .