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

Министерство образования и науки  Российской Федерации

ФГАОУ ВПО Северо-Восточный Федеральный университет им.М.К.Аммосова

Институт математики и информатики

Кафедра теории и методики обучения информатики

 

 

 

Современные средства оценки результатов

 

 

Выполнила: Дмитриева А.М,

студентка 5 курса,гр.ИНФ-09

Проверил: Антонов Ю.С.

 

 

2014

Содержание

Введение

1. Описание машины Тьюринга
2. Принцип работы машины Тьюринга
3. Заключение

Список использованной литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

В 30-е годы XX века английский математик Алан Тьюринг придумал такое странное устройство, которое теперь называют машиной Тьюринга. Идея его была в том, чтобы придумать устройство, абстрактную машину, которая может делать все, что вообще могут делать машины. Он был не единственным в этот момент, другие люди тоже в других терминах определяли похожие вещи, но в гораздо более абстрактных терминах, по крайней мере, в их работах конкретного механизма работы машины не было. Оказалось же, что это одно из самых важных открытий XX века. То, что сейчас в разных устройствах — скажем, в телевизоре и в стиральной машине, — может использоваться одна и та же микросхема процессора, — это воплощение одной из идей Тьюринга. И то, что одна и та же программа может использоваться в самых разных компьютерах, работать с самой разной аппаратурой и выглядеть одинаково, это тоже его идея. Тогда это называлось идеей хранимой программы (программа хранится в памяти и определяет поведение машины), и ещё была идея универсальной машины, — есть машина, которая может делать все, что может делать любая другая машина. Если бы не Тьюринг, наверно, это придумал бы кто-то другой, он не был единственным, кто над этим работал, но так или иначе такое абстрактное теоретическое устройство оказалось одним из самых важных изобретений в XX веке.

 

1. Описание машины Тьюринга

Машина Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство с конечным числом состояний.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

В управляющем устройстве содержится таблица переходов, которая представляет алгоритм, реализуемый данной Машиной Тьюринга. Каждое правило из таблицы предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния Машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, и недетерминированной в противном случае.

Итак, машина Тьюринга — математическая абстракция, умозрительное построение человеческого разума: в природе её нет. Или есть? Сразу приходит на ум, как работает живая клетка. Хотя бы два примера.

• Для производства белков в клетке с помощью сложно устроенного фермента — РНК-полимеразы — считывается информация с ДНК, своего рода информационной ленты машины Тьюринга. Здесь, правда, не происходит перезапись ячеек самой ленты, но в остальном процесс весьма похож: РНК-полимераза садится на ДНК и двигается по ней в одном направлении, при этом она синтезирует нить РНК — нуклеиновой кислоты, сходной с ДНК. Готовая РНК, отсоединяясь от фермента, несёт информацию к клеточным органеллам, в которых производятся белки.
• Ещё более похож на машину Тьюринга процесс исправления ошибок в ДНК — её репарация. Здесь ДНК-полимераза вместе с другими белками двигается по ленте ДНК и считывает обе её половинки (геномная ДНК, как известно, представляет собой две переплетенных нити, несущих одну и ту же информацию). Если информация в половинках не совпадает, ДНК-полимераза принимает одну из них за образец и «правит» другую.

2. Принцип работы машины Тьюринга

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. 
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

• Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.

• Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.

• Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

• Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

• Передвигаться на одну ячейку влево или вправо.

• Менять свое внутреннее состояние.

Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).

Пример работы машины Тьюринга

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова. 
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

 

 

 

 

3. Заключение

Почему надо «знать» машину Тюринга? 
Потому, что это - Начала математики, в нем вводится понятие алгоритм. Помните знаменитый тезис Тюринга: всякий алгоритм может быть реализован соответствующей машиной. Этот тезис является формальным определением алгоритма. Он позволяет доказывать существование или несуществование алгоритмов, описывая соответствующие машины Тюринга или доказывая невозможность их построения. 
Не знать машину Тюринга – значит не знать математики. 
 
Потому, что это - Начала программирования, в нем вводятся понятия алгоритм. К сожалению, у многих программистов тюринговское определение алгоритма заменяется на своё, более близкое: алгоритм – эта программа, которую пишу Я. 
Но если вы не знаете, что такое алгоритм, то как вы можете говорить, что вы запрограммировали алгоритм решения какой-либо задачи. 
 
Потому, что машины Тюринга были использованы в 40-ых годах прошлого века при разработке первых электронных вычислительных машин. 
 
Потому, что, складывая в столбик, чтобы подсчитать свои суммарные денежные затраты, например, мы фактически реализуем машину Тюринга. Действительно, как выполняется сложение в столбик:

	587
	+
	104
	________
	791

7 + 4 – мы ведь реально  не производим вычисления, не  прибавляем как школьники первого  класса к 7 палочкам еще 4 палочки. Нет, мы знаем что 7+4 = 1 и 1 «в памяти». 
 
Т.е. ее надо перенести влево как это и делается в машине Тюринга. Точно также мы складывая 8 и 0 получаем 8, но так как мы находимся в особом состоянии, которое называется «перенос единицы» мы знаем, что в нижней строке надо записать 9. 
Вместо реальных вычислений производится формальная замена одних символов другими. Но интерпретировать записанную последовательность символов «791» как число или как текст или другим образом зависит целиком от нас. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы

1. http://postnauka.ru/faq/13137
2. http://ru.wikipedia.org/wiki/Машина_Тьюринга
3. http://ru.wikibooks.org/wiki/Машина_Тьюринга
4. http://kpolyakov.narod.ru/prog/turing.htm
5. http://inf1.info/turing
6. http://www.ieee.ru/turing.shtml