ТЕЗИС ТЬЮРИНГА


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

УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА


Систему команд машины Тьюринга можно интерпретировать как описание работы некоторого устройства или как программу. До сих пор мы воспринимали машину Тьюринга как программу, выступая в роли некоторого устройства, интерпретирующего эту программу. Все ли одинаково выполняют эту интерпретацию?

ВЫЧИСЛИМОСТЬ И РАЗРЕШИМОСТЬ ПО ТЬЮРИНГУ


Стоит задача определения результативности алгоритма, которая является необходимым условием для реализации. Определение. РЕЗУЛЬТАТИВНОСТЬ – есть получение результата за конечное время (конечное число шагов).

О проблеме остановки.


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

Теорема Райса.


Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.

НЕДЕТЕРМИНИРОВАННАЯ МАШИНА ТЬЮРИНГА.


Определение. ДАТЕРМЕНИРОВАННОЙ МАШИНОЙ ТЬЮРИНГА называется такая машина Тьюринга, у которой отображение множества декартового произведения множеств алфавита ленты и состояния устройства управления в множество декартового произведения множеств алфавита ленты, состояния устройства управления и множества перемещения ленты – функционально, то есть не существует двух одинаковых команд в множестве с одинаковой левой частью.

СЕТИ ПЕТРИ


Сеть Петри представляет собой модель дискретных систем. Дадим неформальное определение сети Петри.

ФУНКЦИОНИРОВАНИЕ СЕТИ ПЕТРИ.


1. “Возбуждение переходов”. Те переходы, которые имеют входящие дуги от позиций, содержащих метки, возбуждаются, то есть способны к функционированию (срабатыванию). В примере возбуждаются преходы .

МАГАЗИННЫЙ АВТОМАТ


Определение. МАГАЗИННЫМ АВТОМАТОМ называется формальная система состоящая из 5 (6) объектов , где — конечный алфавит входных знаков;

О КС грамматике и магазинном автомате.


Для любого языка, порождаемого КС грамматикой существует магазинный автомат, возможно недетерминированный, распознающий (принимающий) строки этого языка. То есть для любого существует такой , что .

О магазинном автомате и КС языке.


Если — язык, принимаемый некоторым, возможно недетерминированным магазинным автоматом , то этот язык может быть порожден КС грамматикой, то есть существует грамматика , такая что .

Понятия и определения


определение: 1. Конечный автомат будем представлять как пятерку объектов: -, где входной алфавит ; — алфавит (множество) состояний содержит n элементов, начиная с нуля ; — выходной алфавит ; -отображения (функция) переходов ; — отображения (функция) выходов

Минимизация конечных автоматов


Формулировка: Для любого конечного автомата существует неотличимый от него минимальный автомат единственный с точностью до изоморфизма, имеющий состояний, если множество состояний автомата разбивается на классов эквивалентности . 

Алгоритм Мили (алгоритм эквивалентных состояний)


a) Пусть задан автомат и известно, что число его состояний . b) Зададим начальное приближение классов эквивалентности и сделаем это следующим образом: два состояния и относим в один класс эквивалентности , если и только если для всех входных знаков . 

Детерминация автоматов


Алгебра регулярных событий. Пусть заданы два языка и над некоторым алфавитом . Введем три операции: 1. объединение языков 2. конкатенация языков  

Теорема Клини


Утверждение: Для любого регулярного выражения существует конечный автомат представляющий (распознающий, порождающий) язык, задаваемый этим выражением.

О детерминации источников


Определение 2:асинхронный автомат (источник) — называется такой конечный автомат (источник) у которого все состояния (вершины) устойчивы по каждому входному знаку.

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТОВ


Самый отдаленный пункт… к чему-нибудь да близок, а самый близкий – от чего-нибудь да отдален. Козьма Прутков.

Комбинационный автомат


Определение: Комбинационный автомат- это конечный автомат, у которого выходной знак зависит от входного, и не зависит от состояния автомата. 

Теорема о структурном синтезе


Пусть задан некоторый конечный автомат К Вопрос : Как представить автомат в виде автоматной сети, возможно состоящий из более простых автоматов, чем исходных ? 

Синтез асинхронных автоматов


Определение: Асинхронным автоматом называется конечный автомат все составляющие которого, устойчивы по всем входным знакам. Это означает, что для всех состояний и .

О синтезе асинхронных автоматов


Определение: Произвольный асинхронный автомат может быть представлен ( реализован ) автоматной сетью, состоящей из двух комбинационных автоматов ? и ? ( без линии задержки ).