Машина Поста и машина Тьюринга

Автор работы: Пользователь скрыл имя, 25 Октября 2013 в 23:11, реферат

Описание

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.

Содержание

Машина Поста…………………………………………. 3
Введение…………………………………………....
Принцип работы…………………………………..
Объекты используемые в программе…………..
Функции используемые в программе…………..
Варианты окончания выполнения программы на машине Поста…………………………………………………...
Пример работы машины Поста…………………

Машина Тьюринга…………………………………….. 9
Введение…………………………………………….
Описание машины Тьюринга…………………....
Свойства машины Тьюринга как алгоритма….
Сложность алгоритмов……………………………
Сложность проблем………………………………..
Машина Тьюринга и алгоритмически неразрешимые проблеммы…………………………………….
Заключение…………………………………………
Пример работы машины Тьюринга…………….


3. Список используемой литературы……………………......20