Теория автоматов и алгоритмов: Теория автоматов. Учебное пособие Учебные издания НИУ ИТМО - Санкт-Петербургское государственное бюджетное учреждение социального обслуживания населения

Содержание

Теория вычислений. Введение в конечные автоматы / Хабр

Спойлер

Cкажу cразу, что не буду объяснять слишком формально.

Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.

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

У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.

Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.

Пример 1

По горизонтали вверху находятся возможные входные символы.

По вертикали слева находятся текущие возможные состояния.

Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.

Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.

Детерминированные конечные автоматы (deterministic finite automaton)

Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.

Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.

Пример 2

Здесь изображена диаграмма переходов для ДКА, визуализация примера 1. Состояние 3 является заключающим. По диаграмме видно, что ДКА принимает цепочку символов только в том случае, если будет последовательность из символов ‘a’, ‘b’ и ‘c’.

Недетерминированные конечные автоматы (nondeterministic finite automaton)

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

Реализация НКА

// Ячейка массива состоящая из: текущее_состояние, считаный_символ, следующее_состояние.
struct state {
	unsigned char current;
	signed char sym; // signed, для обозначения свободного перехода как -1.  
	unsigned char next;
};
// Таблица переходов для НКА на примере 2
struct state machine[] = {
	{0, 'a', 1},
	{1, 'a', 1},
	{2, 'a', 1},
	{1, 'b', 2},
	{2, 'c', 3}
};

Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.

Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.

Множества состояний — в один момент времени НКА может находится в нескольких состояниях.

Пример 3

Заключительное состояние обозначается двойным кругом.

В стартовом состоянии у нас текущим состоянием является {1}, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество {1, 2}.

Пример 4

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

Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии {2, 4}.

Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.

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

КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).

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

Добавление символов в стек — при любом переходе решает какие символы добавить в стек.

Виды:

Детерминированные — к нему применяются те же правила как к ДКА к тому же завершает работу только в заключительном состоянии.
Недетерминированные — к нему применяются те же правила как к НКА к тому же он может завершать работу в заключительном состоянии или когда стек станет пуст.

Пример 5

Шаблон: входной_символ; удаляемый_символ/добавляемый символ. На дно стека добавляется символ $ для, того, что понять когда он закончился.

Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.

ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.

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

Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.

Пример 6

Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.

Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.

Выполнение:

Если находится в состоянии 1 и прочитан нуль, записать единицу, сдвинуть вправо и перейти в состояние 2.
Если находится в состоянии 1 и прочитана единица, записать нуль, сдвинуть влево и перейти в состояние 1.
Еcли находится в состоянии 1 и прочитан пустой квадратик, записать единицу, сдвинуть вправо и перейти в состояние 2.
Если находится в состоянии 2 и прочитан нуль, записать нуль, сдвинуть вправо и остаться в состояние 2.
Если находится в состоянии 2 и прочитана единица, записать единицу, сдвинуть вправо и остаться в состояние 2.
Если находится в состоянии 2 и прочитать пустой квадратик, записать пустой квадратик, сдвинуть влево и перейти в состояние 3.

ДМТ эквивалентен НМТ, так, что они тоже не различаются.

Универсальная машина Тьюринга (universal Turing machine)

Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.

Недостатки:

Память порождаемой машины не может быть больше, чем у самой УМТ.
Нужно уметь правильно разделять пространство ленты между порождаемой машиной и УМТ, ведь их данные находятся на одной ленте.

На этом введение в автоматы закончено, теперь вы можете продолжить изучать дальнейший материал сами.

Литература:

«Теория вычислений для программистов», Том Стюарт.

Автоматов теория | это… Что такое Автоматов теория?

часть теоретической кибернетики (См. Кибернетика), объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50-х гг. 20 в. в связи с требованиями практики проектирования вычислительных машин и с разработкой математических моделей процессов переработки информации в биологических, экономических и других системах. А. т. — самостоятельный раздел математики, имеющий разнообразную проблематику и приложения.

Основными понятиями А. т. являются понятия абстрактного автомата и понятие композиции автоматов. Эти понятия являются разумными абстракциями реально существующих дискретных устройств — Автоматов. Понятие абстрактного автомата позволяет характеризовать устройство с точки зрения Алгоритма его функционирования, т. е. алгоритма переработки информации, который оно реализует. Понятие композиции автоматов позволяет характеризовать устройство с точки зрения его структуры, иными словами, даёт представление, каким образом данное устройство построено из других, более элементарных.

А. т. состоит из ряда разделов. Один из разделов: абстрактно-алгебраическая А. т. В этом разделе абстрактные автоматы изучаются с точки зрения исследования их свойств и различных способов задания. Абстрактным автоматом называют объект А = А (U, X, Y, δ, λ), состоящий из трёх непустых множеств: U — состояний, Х — входных сигналов, Y — выходных сигналов, и двух функций, осуществляющих однозначное отображение множества U×Х в U, δ (а, х) переходов и множества U×Х в Y, λ (а, x) выходов. Абстрактный автомат называется конечным, если множества U, X, Y — конечны. В абстрактно-алгебраической А. т. можно выделить теорию конечных автоматов и теорию бесконечных автоматов. Основные вопросы теории конечных автоматов можно считать решенными. Наиболее интересными результатами теории конечных автоматов являются: теорема анализа и синтеза конечных автоматов, которая даёт характеристику событий, представленных в конечных автоматах, теоремы об определяющих соотношениях в алгебре регулярных событий, оценки длины экспериментов с конечными автоматами, а также ряд результатов по исследованию алгебраических свойств абстрактных автоматов. В теории бесконечных автоматов рассматриваются различные концепции бесконечных автоматов, точнее выделяются классы бесконечных автоматов специального вида. Этот раздел важен тесной связью с общей теорией формальных языков и грамматик (см. Математическая лингвистика), а также с теорией алгоритмов (см. Алгоритмов теория). В рамках абстрактно-алгебраической А. т. наметился (конец 60-х гг.) подход к решению проблемы создания алгебры алгоритмов и построения аппарата для формальных преобразований выражений в этой алгебре, что позволяет совершенно по-новому подойти к решению такого рода задач, как эквивалентность схем алгоритмов, и даёт возможность эффективно решать оптимизационные задачи в проектировании дискретных устройств.

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

Третьим разделом А. т. является теория вероятностных автоматов и самоорганизующихся систем.

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

Лит.: Автоматы. Сб. ст., под ред. Э. Шеннона и Дж. Маккарти, пер. с англ., М., 1956; Глушков В. М, Трахтенброт Б. А, Введение в теорию конечных автоматов, М., 1962; Логика. Автоматы. Алгоритмы, М., 1963; Гилл А., Введение в теорию конечных автоматов, пер. с англ., М. 1966.

Ю. В. Капитонова.

: Теория автоматов: алгоритмический подход

: Теория автоматов: алгоритмический подход Теория автоматов: алгоритмический подход

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

Введение и цель
Часть I. Автоматы на конечных словах
Классы автоматов и преобразования
Минимизация и сокращение
Операции над множествами: реализация с DFA и NFA
Приложения I: сопоставление с образцом
Операции над отношениями: Реализация с преобразователями
Операции над конечными множествами: Реализация с минимальными DFA
Приложения II: Проверка
Автоматы и логика
Приложения III: Арифметика Пресбургера
Часть II: Автоматы на бесконечных словах
Классы омега-автоматов и преобразования
Логические операции: реализации
Проверка на пустоту: реализации
Приложения I: Верификация и временная логика
Приложения II: монадическая логика второго порядка и линейная арифметика
PDF-файл

.

Из примечаний:

Есть отличные учебники по теории автоматов, начиная от учебников для магистрантов к научным монографиям для специалистов. Почему еще один? В конце 1960-х – начале 1970-х основное применение теории автоматов была разработка лексикографических анализаторов, синтаксических анализаторов и компиляторов, и т.д. автоматы рассматривались как абстрактные машины, которые обрабатывают входные данные и принимают или отвергнуть их. Эта точка зрения глубоко повлияла на изложение теории в учебниках. В то время как результаты о выразительной силе машин, такие как леммы о накачке, эквивалентности между моделями и свойствам замыкания уделялось много внимания, конструкции на автоматах, такие как powerset или конструкция продукта, часто играли второстепенную роль в качестве средств доказывания. Чтобы привести простой пример, во многих учебниках того времени — и в более поздних учебниках, написанных в том же стиле — конструкция powerset не вводится как алгоритм, который строит DFA, эквивалентный данному NFA; вместо этого эквивалентный DFA математически определяется путем описания его набора состояний, отношения перехода и т. д. Иногда простой, но важный с вычислительной точки зрения факт, что только состояния достижимы из необходимость построения начального состояния не упоминается. С середины 19Верификация программы 80-х постепенно заменила компиляторы как движущее приложение теории автоматов. Автоматы запущены использоваться для описания поведения — и предполагаемого поведения — аппаратные и программные системы, а не их синтаксические описания. Этот сдвиг от синтаксиса к семантике имели важные последствия. В то время как автоматы для лексический или синтаксический анализ обычно включает не более нескольких тысяч состояний, автоматы для семантических описаний могут легко быть многих порядков величина больше. Эффективные конструкции и алгоритмические вопросы стали императивом, и исследования в этом направлении достигли больших успехов. В в то же время, автоматы на бесконечных словах и связь между логика и автоматы стали более актуальными. Хотя эти исследовательские разработки безусловно, повлияли на учебники, и алгоритмические вопросы постепенно получили Обратите внимание, тексты бакалавриата по-прежнему сохраняют многие концепции из прошлого. Эта книга призвана отразить эволюцию теории автоматов. Автоматы на бесконечных словах вряд ли можно рассматривать как машины, принимающие или отклонение ввода: они могли сделать это только по прошествии бесконечного времени! И Взгляд на автоматы как на абстрактные машины делает акцент на выразительности, которая уже не соответствует его актуальности для современных приложений. Мы думаем, что современная теория автоматов лучше отражает лозунг «автоматы как структуры данных». Подобно тому, как хеш-таблицы и кучи Фибоначчи являются подходящими структурами данных для устанавливает, когда нужны операции со словарем или приоритетной очередью, автоматы это правильно структуру данных для множеств и отношений, когда требуемые операции объединение, пересечение, дополнение, проекции и соединения. С этой точки зрения Алгоритмическая реализация операций должна получить всеобщее внимание, и, как как следствие, алгоритмы составляют основу этой книги. Вторая цель этих заметок связана с презентацией. Опыт говорит что теоретико-автоматные конструкции лучше всего объясняются с помощью примеров, и что примеры лучше всего представлены с помощью картинок. Автоматы включены слова наделены графическим представлением мгновенной привлекательности. В этой книге мы приложили много усилий, чтобы найти наглядные, нетривиальные примеры, графическое представление которых по-прежнему умещается на одной странице.
Вернуться к: Javier Esparza
Основы теории автоматов
Введение
Теория автоматов — захватывающая теоретическая область информатики. Он зародился в 20-м веке, когда математики начали разрабатывать – как теоретически, так и буквально – машины, которые имитировали определенные черты человека, выполняя вычисления быстрее и надежнее. Само слово автомат , тесно связанное со словом «автоматизация», обозначает автоматические процессы, осуществляющие производство конкретных процессов. Проще говоря, теория автоматов имеет дело с логикой вычислений относительно простых машин, именуемых автоматы . С помощью автоматов ученые-компьютерщики могут понять, как машины вычисляют функции и решают проблемы, и, что более важно, что означает, что функция определяется как вычислимая или вопрос описывается как разрешимая .
Автоматы — это абстрактные модели машин, которые выполняют вычисления на входе, перемещаясь по ряду состояний или конфигураций. В каждом состоянии вычисления функция перехода определяет следующую конфигурацию на основе конечной части текущей конфигурации. В результате, как только вычисление достигает приемлемой конфигурации, оно принимает этот ввод. Самый общий и мощный автомат – это Машина Тьюринга .
Основная цель теории автоматов состоит в том, чтобы разработать методы, с помощью которых ученые-компьютерщики могут описывать и анализировать динамическое поведение дискретных систем, в которых сигналы периодически дискретизируются. Поведение этих дискретных систем определяется тем, как система построена из запоминающих и комбинационных элементов. Характеристики таких машин включают:
Входы: предполагается, что это последовательности символов, выбранные из конечного набора I входных сигналов. А именно, набор I — это набор {x ₁, x, ₂, x ₃ … x _k }, где k — количество входов.
Выходы: последовательностей символов, выбранных из конечного множества Z. А именно, множество Z есть множество {y ₁ , y ₂ , y ₃ … y _m } 5 m
9 } 5 m
9 } — количество выходов.
Состояний: конечное множество Q , определение которого зависит от типа автомата.
Существует четыре основных семейства автоматов :
Конечный автомат
Автоматы толкателя
Линейно-ограниченные автоматы
Машина Тьюринга
Приведенные выше семейства автоматов можно интерпретировать в иерархической форме, где автомат с конечным числом состояний является простейшим автоматом, а автомат Тьюринга — наиболее сложным. Основное внимание в этом проекте уделяется автомату с конечным числом состояний и машине Тьюринга. Машина Тьюринга — это машина с конечным числом состояний, но обратное неверно.
[наверх]
Конечные автоматы
Захватывающая история того, как конечные автоматы стали отраслью информатики, иллюстрирует широкий спектр их приложений. Первыми, кто рассмотрел концепцию конечного автомата, была группа биологов, психологов, математиков, инженеров и некоторые из первых ученых-компьютерщиков. Всех их объединял общий интерес: моделировать мыслительный процесс человека, будь то в мозгу или в компьютере. Уоррен МакКаллох и Уолтер Питтс, два нейрофизиолога, первыми представили описание конечных автоматов в 1919 году.43. Их статья под названием «Логическое исчисление, имманентное нервной деятельности» внесла значительный вклад в изучение теории нейронных сетей, теории автоматов, теории вычислений и кибернетики. Позже двое ученых-компьютерщиков, Г.Х. Мили и Э. Ф. Мур обобщили теорию на гораздо более мощные машины в отдельных статьях, опубликованных в 1955-56 гг. Автоматы с конечным числом состояний, машина Мили и машина Мура, названы в честь их работы. В то время как машина Мили определяет свои выходные данные через текущее состояние и входные данные, выходные данные машины Мура основаны только на текущем состоянии.
Уоррен Маккалох и Уолтер Питтс (источник)
. Автоматы представляют собой абстрактные машины, состоящие из набора состояний (набор Q), набора входных событий (набор I), набора выходных событий (набор Z) и функции перехода состояний. Функция перехода состояния принимает текущее состояние и входное событие и возвращает новый набор выходных событий и следующее состояние. Поэтому его можно рассматривать как функцию, которая отображает упорядоченную последовательность входных событий в соответствующую последовательность или набор выходных событий.
Функция перехода состояний: I → Z
Автоматы с конечным числом состояний являются идеальными вычислительными моделями для небольшого объема памяти и не поддерживают память. Эта математическая модель машины может достигать только конечного числа состояний и переходов между этими состояниями. Его основное применение – анализ математических задач. Конечные машины также используются не только для общих вычислений, но и для распознавания обычных языков.
Чтобы полностью понять концептуально конечный автомат, рассмотрим аналогию с лифтом:
Лифт – это механизм, который запоминает не все предыдущие запросы на обслуживание, а текущий этаж, направление движения (вверх или вниз) и набор еще не удовлетворенных запросов на обслуживание. Таким образом, в любой данный момент времени работающий лифт будет определяться следующими математическими терминами:
Состояния: конечное множество состояний для отражения прошлой истории запросов клиентов.
Входные данные: ограниченный набор входных данных, в зависимости от количества этажей, на которые может попасть лифт. Мы можем использовать множество I, размер которого равен количеству этажей в здании.
Выходы: ограниченный набор выходов, в зависимости от потребности лифта подниматься или опускаться, в соответствии с потребностями клиентов.
Автомат с конечным числом состояний формально определяется как 5-кортеж (Q, I, Z, ∂, W), такой что:
Q = конечное множество состояний
I = конечное множество входных символов
Z = конечное множество выходных символов
∂ = отображение I x Q в Q, называемое функцией перехода состояния, т. е. I x Q → Q
W = отображение W из I x Q в Z, называемое выходной функцией
A = набор состояний принятия, где F является подмножеством Q
Из приведенной выше математической интерпретации можно сказать, что автомат с конечным числом состояний содержит конечное число состояний. Каждое состояние принимает конечное число входных данных, и у каждого состояния есть правила, описывающие действия машины для любого входного значения, представленные в функции отображения переходов состояний. В то же время ввод может привести к изменению состояния машины. Для каждого входного символа существует ровно один переход из каждого состояния. Кроме того, любой набор из пяти кортежей, который принимается недетерминированными конечными автоматами, также принимается детерминированными конечными автоматами.
При рассмотрении конечных автоматов важно иметь в виду, что механический процесс внутри автомата, который приводит к вычислению выходов и изменению состояний, не подчеркивается и не углубляется в детали; вместо этого он считается «черным ящиком», как показано ниже:
Имея конечный постоянный объем памяти, внутренние состояния конечного автомата не имеют дополнительной структуры. Их можно легко представить с помощью диаграмм состояний, как показано ниже:
gif”/>
(из Automata, стр. 7)
Диаграмма состояний иллюстрирует работу автомата. Состояния представлены узлами графов, переходы стрелками или ветвями , а соответствующие входы и выходы обозначены символами. Стрелка, входящая слева в q ₀, показывает, что q ₀ является начальным состоянием автомата. Перемещения, не связанные с изменением состояния, обозначены стрелками по бокам отдельных узлов. Эти стрелки известны как автопетли .
Существует несколько типов конечных автоматов , которые можно разделить на три основные категории:
акцепторы : либо принимают ввод, либо нет
распознаватели : либо распознавать ввод, либо нет
преобразователи : генерировать выходные данные из заданного ввода
Автоматы с конечным числом состояний применяются в различных областях. Они могут работать с языками с конечным числом слов (стандартный случай), бесконечным числом слов (автоматы Рабина, автоматы Бирхе), различными типами деревьев и в аппаратных схемах, где вход, состояние и выход являются битовыми. вектора фиксированного размера.
[наверх]
Конечное состояние против машин Тьюринга
Простейшим автоматом, используемым для вычислений, является конечный автомат. Он может вычислять только очень примитивные функции; следовательно, это не адекватная вычислительная модель. Кроме того, неспособность конечного автомата обобщать вычисления снижает его мощность.
Ниже приведен пример, иллюстрирующий разницу между автоматом с конечным числом состояний и машиной Тьюринга:
Представьте себе современный процессор. Каждый бит в машине может находиться только в двух состояниях (0 или 1). Следовательно, существует конечное число возможных состояний. Кроме того, при рассмотрении частей компьютера, с которыми взаимодействует ЦП, существует конечное число возможных входных данных от компьютерной мыши, клавиатуры, жесткого диска, различных слот-карт и т. д. В результате можно сделать вывод, что ЦП может моделировать как конечный автомат.
Теперь рассмотрим компьютер. Хотя каждый бит в машине может находиться только в двух разных состояниях (0 или 1), внутри компьютера в целом существует бесконечное количество взаимодействий. Становится чрезвычайно сложно моделировать работу компьютера в рамках ограничений конечного автомата. Однако более высокоуровневые, бесконечные и более мощные автоматы могли бы выполнить эту задачу.
Всемирно известный ученый-компьютерщик Алан Тьюринг разработал первую «бесконечную» (или неограниченную) модель вычислений: машину Тьюринга в 1936, чтобы решить Entscheindungsproblem . Машину Тьюринга можно рассматривать как конечный автомат или блок управления, оснащенный бесконечным хранилищем (памятью). Его «память» состоит из бесконечного числа одномерных массивов ячеек. Машина Тьюринга — это, по сути, абстрактная модель современного компьютерного исполнения и хранения данных, разработанная для того, чтобы дать точное математическое определение алгоритму или механической процедуре.
Алан Тьюринг (источник)
В то время как автомат называется конечным , если его модель состоит из конечного числа состояний и функций с конечными строками ввода и вывода, бесконечные автоматы имеют «аксессуар» — либо стопка или лента, которые можно перемещать вправо или влево и которые могут соответствовать тем же требованиям, что и машина.
A Машина Тьюринга формально определяется множеством [Q, Σ, Γ, δ, q ₀ , B, F], где
Q = конечное множество состояний, из которых одно состояние q ₀ является начальным состоянием
Σ = подмножество Γ, не включая B, представляет собой набор из входных символов
Γ = конечное множество допустимых символов ленты
δ = функция следующего перемещения , функция отображения из Q x Γ в Q x Γ x {L,R}, где L и R обозначают направления влево и вправо соответственно
q ₀ = в наборе Q как начало состояние
B = символ Γ, как пробел
F ⊆ Q набор из конечных состояний
Таким образом, основное различие между машиной Тьюринга и двусторонними конечными автоматами (FSM) заключается в том, что машина Тьюринга способна изменять символы на своей ленте и моделировать выполнение и хранение на компьютере.