Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Машина Тьюринга-ПостаМашина Тьюринга-Поста (МТ) - абстрактный универсальный исполнитель, предложенный в 1936 году Аланом Тьюрингом из Кембриджского университета (и независимо от него для Эмилем Постом) формализации понятия алгоритма. Абстрактность заключается в том, что исполнитель представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. 1.Внешний алфавит: конечное множество, элементы которого называются буквами (символами). Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. 2. Внутренний алфавит: конечное множество состояний автомата. Одно из состояний должно быть начальным (запускающим программу). Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма. 3. Таблица переходов: описание поведения автомата в зависимости от состояния и считанного символа. Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия: 1. Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой). 2. Перемещаться влево и вправо по ленте. 3. Менять свое внутреннее состояние. Команда для машины Тьюринга представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Команда может содержать не все эти составляющие.
|