Машина Тьюринга: различия между версиями

Формально абстрактный автомат определяется как пятерка

 

 

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, <math>\delta : S \times X \rightarrow S</math> — функция переходов, <math>\lambda : S \times X \rightarrow Y</math> — функция выходов.

Абстракный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом абстрактный автомат определяет семейство инициальных автоматов

 

 

Для уточнения свойств абстрактных автоматов введена [[w:классификация абстрактных автоматов|классификация]].

 

{{Рамка}}

== Алан Тьюринг ==

'''Тьюринг, Алан Матисон''' (23 июня 1912 — 7 июня 1954) — английский математик, логик, криптограф, изобретатель Машины Тьюринга.