Автор работы: Пользователь скрыл имя, 06 Мая 2012 в 19:29, контрольная работа
Одним из центральных понятий информатики является понятие алгоритма. Абстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. американским математиком Эмилем Леон Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой универсальных исполнителей, являющихся полностью детерминированными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» результат.
ВВЕДЕНИЕ 3
1. 1. Машина Поста. Основные понятия и операции 4
1.2. Способ задания проблемы и формулировка 1 6
2. Машина Тьюринга 8
3.Решение Задач 11
ЗАКЛЮЧЕНИЕ 13
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14