Автор работы: Пользователь скрыл имя, 30 Ноября 2014 в 22:32, реферат
Число возможных состояний этого устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них , на которых записаны входные данные.
Устройство машины Тьюринга
Описание машины Тьюринга
Пример машины Тьюринга
Варианты машины Тьюринга
Машина Тьюринга,работающая на бесконечной ленте
Двумерные машины Тьюринга
Список использованной литературы
1 Рощин А.Г., Половов
Р.М. Теория автоматов. Часть I. Тексты лекций
- Москва: МГТУ ГА, 2001. - 76 с.
2. Фалевич Б.Я. Теория
алгоритмов. – М.: ИНФРА-М, 2006. – с.324.
3. Фалина Н.М. Машина
Тьюринга // Информатика. - №26. – 2005. – с.12-15
4. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1
5.Карпов Ю. Г. Теория автоматов. — ISBN 5-318-00537-3
6. http://it.kgsu.ru/TI_5/falg_
7.· http://ru.wikipedia.org/
8. http://ru.wikipedia.org/wiki/