**Теория автоматов** занимается изучением абстрактных вычислительных устройств или "машин".  
1930 г. - Алан Тьюринг исследовал абстрактную машину. Цель: описать границу между тем, что может делать вычислительная машина и тем, что она не может делать.  
## Машина Тьюринга
**Машина Тьюринга** - это абстрактная вычислительная машина, мысленный эксперимент для решения проблемы математической логики. Она состоит из трёх элементов:
- Бесконечная лента с ячейками
- Автомат или головка для чтения и записи данных
- Программы
  
![Машина Тьюринга](../Pictures/01_01.%20Машина%20Тьюринга.png)  
Роль машины Тьюринга:
- Первая математическая модель универсальных вычислений
- Всё, что можно вычислить, описывается как машина Тьюринга
- Это самая популярная модель вычислений
- Это описание работы компьютера, которое Тьюринг дал до появления компьютеров
  
Факты о машине Тьюринга:
- Машина Тьюринга использовала двоичную систему счисления во времена преобладания десятичной
- Слово "бит" появилось в публикации в 1948 г.
- Тьюринг описал универсальный компьютер "общего назначения". В то время компьютеры разрабатывались для определенных видов работ
- Никто не доказал, что существует более эффективная модель вычисления, чем машина Тьюринга
- Полнота по Тьюрингу: если мы можем произвести определенное вычисление на машине Тьюринга, то мы можем произвести его на любом компьютере
  
**Полнота по Тьюрингу** - одно из базовых понятий в информатике. Полный по Тьюрингу язык программирования или компьютер способен имитировать машину Тьюринга.
## Теория автоматов
1940-1950 гг. - изучение простейших машин - "конечных автоматов". Предложены в качестве модели функционирования человеческого мозга  
1950 г. - Наом Хомский занялся изучением формальных грамматик. Грамматики тесно связаны с абстрактными автоматами и служат основой для составляющих ПО
#### Конечные автоматы
Являются моделью для многих компонентов аппаратного и программного обеспечения.  
Примеры использования:
- ПО для разработки и проверки цифровых схем
- ПО для сканирования больших текстовых массивов с целью поиска заданных слов, фраз, последовательностей символов (шаблонов)
- ПО для проверки разных систем, которые могут находится в конечном числе разных состояний (таких, как протоколы связи, протоколы защищенного обмена информацией)
- **Лексический анализатор** стандартного компилятора - компонент компилятора, который отвечает за разбивку исходного текста на логические единицы - лексемы (ключевые слова, идентификатор, знаки операций, знаки пунктуации и т. д.)
  
Подходы к определению и изучению автоматов:
- Макроподход - внешнее поведение автомата (абстрактные автоматы)
- Микроподход - структура автомата, его составные части (структурные автоматы)
- Практический аспект - внешнее поведение и реализация