|
Интуитивное и точное определение алгоритма. Свойства алгоритмов. Машины Тьюринга как один из способов точного определения алгоритмов. Примеры алгоритмов, реализуемых в виде машины Тьюринга. Программная реализация машины Тьюринга.
Другие способы реализации понятия алгоритма. Нормальные алгорифмы (алгоритмы) Маркова. Программная реализация нормальных алгоритмов Маркова. Понятие о машинах Поста. Тезис Черча.
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; просмотров: 153 | Поможем написать вашу работу | Нарушение авторских прав |