[Bvbz d

  • 18 сент. 2012 г.
  • 2994 Слова
Министерство Образования РФ
Сибирский Межрегиональный Колледж Строительства и Предпринимательства

Реферат на тему:
«Машина Тьюринга»

Выполнил:
студент
Ильин Д.М.
Гр.СДМ-12-1
Проверил:
преподаватель
Панина В.Е.

Иркутск
2012
Содержание
Введение…………………………………………………………………………3
1. Описание машины Тьюринга………………………………………………. 4
1.1 Свойства машины Тьюринга какалгоритма…………………………….. 7
2. Сложность алгоритмов………………………………………………………8
2.1 Сложность проблем…………………………………………………………9
3. Машина Тьюринга и алгоритмически неразрешимые проблемы..............12
Заключение……………………………………………………..……………….17
Список литературы……………………………………………………………..19

Введение
Машина Тьюринга - это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещаетсявдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика, как состояние, которое может выражаться целым числом от нуля до некоторой максимальной величины. В зависимости от состояния машина Тьюринга может выполнить одно из трех действий: записать символ в ячейку, передвинуться на одну ячейку вправо или влево и установить внутреннее состояние.Устройство машины Тьюринга чрезвычайно просто, однако на ней можно выполнить практически любую программу. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.
В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенныхклассов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.

1. Описание машины Тьюринга
Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью "О вычислимых числах в приложении к проблеме разрешения", которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов.
Предыстория создания этой работысвязана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как "проблему разрешимости" - нахождение общего метода, для определения выполнимости данного высказывания на языкеформальной логики.
Статья Тьюринга как раз и давала ответ на эту проблему - вторая проблема Гильберта оказалась неразрешимой. Но значение статьи Тьюринга выходило далеко за рамки той задачи, по поводу которой она была написана.
Приведем характеристику этой работы, принадлежащую Джону Хопкрофту: "Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь отинтуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названнойвпоследствии машиной Тьюринга".
Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.
Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:
конечное множество состояний – Q, в которых может находиться машина Тьюринга;конечное множество символов ленты – Г;
функция δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние qi, заменяет символ gi на символ gj и...
tracking img