Цю статтю потрібно повністю переписати відповідно до стандартів якості Вікіпедії Ви можете допомогти переробивши її Можл

Абстрактний автомат (також абстрактна машина, абстрактний комп'ютер; англ. abstract machine) — теоретична модель апаратної або програмної обчислювальної системи, побудована на основі теорії автоматів. Використовується як у інформатиці, так і у комп'ютерній інженерії і, зазвичай, неявно базується на парадигмі дискретного часу.

Процес, у якому переходи виконуються під впливом зовнішніх дій, моделюється за допомогою автомата. Використовуючи автомати, можна моделювати багато машин, включаючи компоненти комп'ютера, також можна дослідити питання розв'язності і складності різних задач.

Основні поняття

Автомат складається з:

вхідна стрічка;
пристрій керування;
допоміжна / робоча пам'ять.

Вхідна стрічка

Її можна розглядати як лінійну послідовність кліток, або комірок, причому кожна комірка точно містить один вхідний символ з деякого скінченного вхідного алфавіту. За допомогою вхідної стрічки зображується інформація, що поступає на вхід автомата.

Вхідна голівка

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

Пам'ять

Пам'ять автомата - структура, в якій записуються, зберігаються і зчитуються додаткові дані, що використовуються автоматом при роботі. Для кожного виду автоматів строго визначено тип пам'яті. Автомат може не мати назву, - тип пам'яті часто визначає назву автомата.

Робота автомата складається з послідовності тактів. Кожен такт складається з таких дій:

Читається поточний вхідний символ.
За допомогою функції доступу досліджується пам'ять, і до неї заноситься деяка інформація.
Змінюється стан пристрою керування.
Записується вихідна інформація у комірки вхідної стрічки.
Вхідна голівка зміщується на одну комірку вліво, вправо або зберігається у початковому стані.

Поточний вхідний символ та інформація, що витягнута з пам'яті, разом з поточним станом пристрою керування визначають, яким повинен бути цей такт. Таким чином, на кожному такті визначається поточна конфігурація автомата, до якої входять:

поточний стан пристрою керування;
поточний зміст вхідної стрічки;
поточний зміст робочої пам'яті.

Конфігурація автомата змінюється на кожному такті під впливом пристрою керування.

Пристрій керування

Складається зі скінченної множини станів S = {s₀...s_n} і відображень, які залежно від попередньої конфігурації дозволяють визначити нову конфігурацію автомата, напрямок переміщення вхідної голівки (якщо вона не одностороння), інформацію на друку (якщо в автоматі передбачено функцію друку), інформацією, що заносять у пам'ять і зчитують звідти (якщо автомат має робочу пам'ять).

Можуть бути два типи пристрою керування:^[]

Недетермінований — для кожної конфігурації існує скінченна множина можливих конфігурацій(більше однієї), так що в будь-яку з них автомат може перейти на наступному кроці.
Детермінований — для кожної конфігурації існує не більше однієї можливої наступної конфігурації.

Див. також

Література

Комп'ютерна дискретна математика/М.Ф.Бондаренко, Н.В.Білоус, А.Г.Руткас. - Х.:Компанія СМІТ, 2004.-385с.