Машина Тьюринга

ID работы - 614903
математика (контрольная работа)
количество страниц - 11
год сдачи - 2012

---

СОДЕРЖАНИЕ:

---

Содержание

1. Машина Тьюринга 3
2. Алгоритмически неразрешимые проблемы 8
Литература 12

---

ВВЕДЕНИЕ:

---

1. Машина Тьюринга
Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью «О вычислимых числах в приложении к проблеме разрешения», которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов.
Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача до-казательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как «проблему разрешимости» - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.
Статья Тьюринга как раз и давала ответ на эту проблему - вторая про-блема Гильберта оказалась неразрешимой. Но значение статьи Тьюринга выходило далеко за рамки той задачи, по поводу которой она была написана.
Приведем характеристику этой работы, принадлежащую Джону Хоп-крофту: «Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга».
Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.
.
Пpогpамма для машины Тьюpинга состоит из последовательности инстpукций. Каждая инстpукция имеет вид
CurrentState CurrentSymbol NextSymbol NextState Move
где
CurrentState - текущее внутpеннее состояние,
CurrentSymbol - обозpеваемый символ,
NextSymbol - символ, котоpый пишется в обозpеваемую ячейку,
NextState - последующее внутpеннее состояние.
Move - напpавление сдвига головки ('L' или 'R' ), 'L' означает сдвиг головки влево, 'R' - сдвиг головки впpаво на одну ячейку.
Пpедполагается, что в обе стоpоны от введенной последовательности символов находится бесконечное количество символов пpобел (пробел будем обозначать символом "b").
Hачальное внутpеннее состояние - "A", конечное внутреннее состояние - "Z".
Работа ма

---

СПИСОК ЛИТЕРТУРЫ:

---

Литература
1. Любченко В.С. Новые песни о главном-II//Мир ПК. 1998. №7. с.112.
2. Успенский В.А. Машина Поста. 2-е изд., испр. М.: Наука, 1988. 96 с. (Популярные лекции по математике).
3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ. М.: Мир, 1983. 256 с.
4. Кузьминский М. Вышел Merced из тумана//Computerworld Россия.1997. №47. С.31.
5. Хамби Э. Программирование таблиц решений. М.: Мир, 1976. 86 с.
6. Глушков В.М. Введение в кибернетику. Киев: Изд-во АН Укр ССР. 1964. 324 с.
7. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984. 264 с.
8. Краснов С.А. Транспьютеры, транспьютерные вычислительные системы и Оккам//Вычислительные процессы и системы / Под ред. Г.И. Марчука. Вып. 7. М.: Наука., 1990. 352 с.
Цена: 1000.00руб.