Формализация понятия алгоритма
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: бесплатный решебник, методы дипломной работы
| Добавил(а) на сайт: Камилла.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
из состояния p перейти в состояние q,
переместиться на следующую ячейку влево если w=Л, - вправо если w=П или остаться на месте если w=Н.
Правило начала: каретка всегда размещается над последним, считая слева направо, символом слова на ленте и находится в специальном начальном состоянии qo;
Правило окончания: есть специальное состояние, мы его будем обозначать символом ! из алфавита Q. Как только каретка переходит в состояние ! , она останавливается.
Например, если правило имеет вид ap®b!w , то после его выполнения вычисление считается законченным.
Правило расположения результата: справа от каретки до первого символа пустоты.
Дело в том, что
пустота - это тоже символ, который мы будем обозначать символом 
L.
Пример 1. Построить Машину Тьюринга, вычисляющую функцию
U(n)=n+1 , где nÎ {0,1,2,3,4,5,6,7.8.9}.
Машина Тьюринга с алфавитом D={0,1,2,3,4,5,6,7.8.9} и Q={qo, qs, !},
где qo - начальное состояние, а ! - конечное.
Нижеприведенная последовательность команд, реализует требуемую функцию.
|
№ команды |
a |
b |
|
1 |
0qo®1qsH |
0qs®0qsЛ |
|
2 |
1qo®2qsH |
1qs®1qsЛ |
|
3 |
2qo®3qsH |
2qs®2qsЛ |
|
4 Рекомендуем скачать другие рефераты по теме: шпоры на экзамен, реферат по математике. Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная