Реферат по вычислительной технике на тему Машина Тьюринга

Машина Тьюринга активно применяется в сферах математики и программирования. Ее также используют для более наглядного изучения принципов построения алгоритмов.
Машина Тьюринга – это математическая абстракция, представляющая из себя вычислительную модель, которая пошагово выполняет однотипные команды. Она была предложена Аланом Тьюрингом в 40-х годах для формального определения алгоритма.
Другими словами, если решение какой-либо задачи можно реализовать с помощью машины Тьюринга, то такая задача является алгоритмически разрешимой.
Полнота по Тьюрингу – некая характеристика системы в теории вычислимости, которая означает, что с ее помощью можно реализовать любую вычислительную функцию. Другими словами, для каждой вычислимой функции существует вычисляющая ее программа. Если на языке программирования можно реализовать машину Тьюринга, то считается, что на этом языке можно написать любой алгоритм, а сам язык считается Тьюринг полным языком .
Машина Тьюринга – это вычислительная модель c конечным фиксированным множеством состояний, которая предназначена для автоматического выполнения алгоритмов обработки символов конечного фиксированного алфавита. В состав машины Тьюринга входит устройство управления, лента и головка считывания-записи.
По своей структуре машина Тьюринга состоит из четырех основных частей.
Первой частью машины Тьюринга является условно бесконечная лента, на которой находятся символы некоего алфавита. Данная лента представляет собой данные, которые впоследствии анализирует машина. Начальные данные напрямую влияют на конечный результат работы машины Тьюринга.
Далее идет головка считывания-записи, которая позволяет машине Тьюринга считывать с бесконечной ленты нули, единицы и другие символы. Она также может стирать их оттуда и при необходимости записывать заново. Таким образом, благодаря головке считывания-записи машина Тьюринга может читать ленту, а также изменять её содержимое.
Затем следует регистр состояний, а именно та его часть, которая содержит некую переменную, в зависимости от значений которой машина Тьюринга может пребывать в некотором состоянии. Состояние машины напрямую зависит от того, как и для каких целей она использует головку считывания-записи – для записи или чтения, движения или простоя, или же в других, более сложных комбинациях. Свои состояния машина Тьюринга может менять уже после взаимодействия с бесконечной лентой. У машины также всегда должно присутствовать хотя бы одно единственное состояние, а именно – начальное.
Последней основной частью машины Тьюринга является программа, или другими словами, алгоритм. Алгоритм представляет из себя некую совокупность правил, необходимых для полноценного функционирования машины. Данные правила можно описать следующими словами: если машина находится в таком-то состоянии и считывает с ленты такой-то символ, она делает то-то и переходит в такое-то состояние.
Машина Тьюринга обладает следующими свойствами, характерными также для алгоритма:
1. Дискретность – машина Тьюринга может перейти к (k+1)-му шагу только после выполнения k-го шага, так как именно k-й шаг определяет, каким будет (k+1)-й шаг.
2. Понятность – на каждом шаге в ячейку записывается символ из алфавита, затем автомат делает одно движение, и впоследствии машина Тьюринга переходит в одно из описанных до этого состояний.
3. Детерминированность – в каждой клетке таблицы машины Тьюринга записан лишь один вариант действия; на каждом шаге результат определён однозначно, следовательно, последовательность шагов решения задачи определена однозначно. Другими словами, если машине Тьюринга на вход подается одно и то же входное слово, то на выходе выходное слово каждый раз будет одним и тем же.
4. Результативность – результаты каждого шага, а также всей последовательности шагов определены однозначно. Из этого следует, что правильно написанная машина Тьюринга перейдёт в конечное состояние за конечное число шагов. Другими словами, за конечное число шагов будет достигнуто решение на поставленную задачу.
5. Массовость – каждая машина Тьюринга определена над всеми допустимыми словами из алфавита, в этом и состоит свойство массовости; каждая машина Тьюринга предназначена для решения одного класса задач, то есть, под каждую задачу пишется своя машина Тьюринга.















2 Вычисления машины Тьюринга
Машина Тьюринга является воображаемым, математическим механизмом, а не механизмом физическим. Данный механизм – абстрактная концептуальная модель. Она представляет собой бесконечную в обе стороны ленту, которая разделена на ячейки и автомата, и которая управляется программой. Ячейки (клетки) могут быть пустыми, а могут содержать один символ (единицу, ноль или, например, любой другой символ из алфавита). Абстрактная универсальная вычислительная машина состоит из безграничной памяти, в которой хранятся сведения и инструкции, и сканера, перемещающегося по ячейкам памяти, символ за символом считывающего обнаруженные сведения, а также записывающего в ячейки последующие символы. Программы для машин Тьюринга оформляются в виде таблицы, где первый столбик и строчка содержат буквы внешнего алфавита, а также возможные, допустимые внутренние состояния автомата (внутренний алфавит). Содержание таблицы представляет собой готовые команды для машины. Символ, который считывает головка в ячейке, и внутренне состояние головки устанавливают, какую команду необходимо выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице .
При вводе разных программ в память машина осуществляет различного рода вычисления. Формирование единой машины, которая имела бы фиксированную структуру и с помощью хранящихся в памяти закодированных инструкций, преобразовывалась бы из механизма, предназначенного для выполнения одной задачи, в механизм, успешно решающий совершенно другую, было действительно фантастической идеей.
Машина Тьюринга способна совершать небольшой набор базовых операций: перемещение на одну клетку влево/вправо, печать и изменение состояния. Сканер перемещается на одну клетку за раз и может напечатать символ в просканированной клетке (после удаления уже имеющегося в ней). Лента с одной стороны служит памятью, а с другой стороны и механизмом ввода-вывода, а кроме того на ней может быть «выбита» программа, состоящая из инструкций. Меняя свое состояние, машина может, как сформулировал Тьюринг, «вспомнить некоторые символы, которые она «видела (сканировала) ранее». Тьюринг не уточнил механизм изменения состояния – машина Тьюринга является абстракцией, так что описывать конкретный механизм необязательно, но его легко себе представить.
Далее, как уже говорилось выше, машина Тьюринга имеет бесконечную внешнюю память. Однако ни в одной действительно существующей машине бесконечной памяти быть не может. Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных электронно-вычислительных машин.
В наше время, когда множество людей уже владеют различными устройствами, представляющими собой физическую реализацию универсальной машины Тьюринга, его концепция вычислительной машины, функционирующей по принципу «одного окна», может показаться столь же очевидной, как и идея колеса. Но в 1936 году, когда инженеры традиционно проектировали под разные задачи отдельные машины, она произвела настоящую революцию.
Универсальная машина Тьюринга (UTM) универсальна в том смысле, что ее можно запрограммировать на выполнение любых расчетов, с которыми в принципе способен справиться человек-вычислитель – служащий, действующий в соответствии с «эффективной» или заученной процедурой. До появления электронного компьютера многие тысячи людей-вычислителей были заняты в бизнесе, на государственных предприятиях и в научно-исследовательских учреждениях. Универсальная машина имеет фиксированную таблицу инструкций, которая встроена, если так можно выразиться, «жестко вмонтирована» в нее.