Интуитивное и точное определение алгоритма. Свойства алгоритмов. Машины Тьюринга как один из способов точного определения алгоритмов. Примеры алгоритмов, реализуемых в виде машины Тьюринга. Программная реализация машины Тьюринга.
Другие способы реализации понятия алгоритма. Нормальные алгорифмы (алгоритмы) Маркова. Программная реализация нормальных алгоритмов Маркова. Понятие о машинах Поста. Тезис Черча.
1. Машина Тьюринга с внешним алфавитом А = { 
, 1}, где - «пустой» символ определяется следующей программой:
Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент, в состоянии 
машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова):
a) 111 1;
б) 11 11а 1;
в) 111111;
г) 1 1;
д) 11 11;
е) 1;
ж) l l l l;
з) 111;
и) l l l;
к) 11 11.
Если остановка происходит, то какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается?
Дата добавления: 2015-09-12; просмотров: 50 | Поможем написать вашу работу | Нарушение авторских прав |