Размещено на http://www.allbest.ru/

Министерство образования и науки, молодежи и спорта Украины

Запорожский колледж радиоэлектроники

Запорожского национального технического университета

РЕФЕРАТ

по предмету

Математическая логика и теория алгоритмов

Тема:

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

Выполнил Гавранек И.К.

Студент группы ПМ 10-1

Проверил преподаватель Яловая Е.А.

2013

Содержание

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

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

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

Читающая и пишущая головка может читать буквы рабочего алфавита А = {a₀, а₁, ...,а_t}, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква a₀ - «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты - текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты. При этом возможна ситуация выхода за левый край ленты (ЛК), которая является аварийной (недопустимой), или машинного останова (МО), когда машина выполняет предписание об остановке.

Порядок работы МТ (с рабочим алфавитом a₀, а₁ ..., а_t и состояниями q₀, q₁, ..., q_s) описывается таблицей машины Тьюринга. Эта таблица является матрицей с четырьмя столбцами и (s + 1)(t + 1) строками. Каждая строка имеет вид

q_ia_jv_ijq_ij, 0 <= i < s, 0 <= j <= t, гдеq_ijпринадлежит {q₀,q₁,…, q_s}

Здесь через v_ij обозначен элемент объединения алфавита {a₀, а₁, ..., а_t} и множества предписаний для лентопротяжного механизма:

· l - переместить ленту влево,

· r - переместить ленту вправо,

· s - остановить машину;

· v_ij - действие МТ, состоящее либо в занесении в ячейку ленты символа алфавита a₀, а₁, ..., а_t либо в движении головки, либо в останове машины;

· q_ij является последующим состоянием.

МТ работает согласно следующим правилам: если МТ находится в состоянии q_i, головка прочитывает символ a_j в рабочей ячейке. Пусть строка a_ia_jv_ijq_ij, начинающаяся с символов q_ia_j, встречается только один раз в таблице. Если v_ij - буква рабочего алфавита, то головка стирает содержимое рабочей ячейки и заносит туда эту букву. Если v_ij - команда rили l для лентопротяжного механизма, то лента сдвигается на одну ячейку вправо или влево (если не происходит выход за край ленты) соответственно. Если v_ij = s, то происходит машинный останов.

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

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

Рассмотрим примеры нескольких схем машины Тьюринга.

вычислительный машина тьюринг алгоритм

1. Алгоритм прибавления единицы к числу в десятичной системе счисления

Дана десятичная запись числа n (т.е. представление натурального числа n в десятичной системе счисления). Требуется получить десятичную запись числа n+1.

Очевидно, что внешний алфавит МТ должен состоять из десяти цифр 1 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и символа пробела _. Эти цифры записывают по одной в ячейке (подряд, без пропусков).

Оказывается достаточным иметь два внутренних состояния машины: q₁ и q₂.

Предположим, что в начальный момент головка находится над одной из цифр j числа, а машина находится в состоянии q₁. Тогда задача может быть решена в два этапа: движения головки к цифре единиц числа (во внутреннем состоянии q₁) и замене этой цифры на единицу большую (с учетом переноса 1 в следующий разряд, если это 9, j во внутреннем состоянии q₂). Соответствующая схема МТ может иметь вид:

2. Алгоритм записи числа в десятичной системе счисления

Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Требуется записать в десятичной системе число этих меток (пересчитать метки).

Суть алгоритма может состоять в том, что к числу 0, записанному на ленте в начале работы машины, машина добавляет 1, стирая метку за меткой, так что вместо нуля возникает число 0+k.

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

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

Предположим, мы расширили определение МТ, добавив определенное состояние q_* устройства управления машины. Будем говорить, что если устройство управления переходит в состояние q₀ для заданного входного слова x, то машина допускает x; если устройство переходит в состояние q_*, то машина запрещает x. Такую машину будем называть машиной Тьюринга с двумя выходами. Могут быть рассмотрены многочисленные варианты машины Тьюринга, имеющие некоторое конечное число лент. В каждой клетке этих лент может находиться один из символов внешнего алфавитаА = {а₀, а₁, ..., а_n}. Устройство управления машиной в каждый момент времени находится в одном из конечного множества состояний Q = {q₀, q₁, ..., q_m). Для k-ленточной машины конфигурация ее в i-й момент времени описывается системой k-слов вида:

первый индекс соответствует моменту времени, второй - номеру ленты, третий - номеру клетки, считая слева направо. Говорят, что машина выполняет команду

Если, находясь в состоянии q₁, и обозревая ячейки с символами а_a1, ..., a_ak, машина переходит в состояние q_j, заменяя содержимое ячеек соответственно символами а_b1, ..., a_bk, то после этого ленты соответственно сдвигаются в направлениях k₁, ..., k_k.

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

· различные символы должны заменяться различными кодовыми группами, но один и тот же символ должен заменяться всюду, где бы он не встретился, одной и той же кодовой группой;

· строки кодовых записей должны однозначно разбиваться на отдельные кодовые группы;

· должна иметься возможность распознать кодовые группы, соответствующие командам Л, П, С, различать кодовые группы, соответствующие символам внешнего алфавита и внутренним состояниям.

Для сравнения структур различных машин и оценки их сложности необходимо иметь соответствующую меру сложности машин. К.Шеннон предложил рассматривать в качестве такой меры произведение числа символов внешнего алфавита и числа внутренних состояний. Большой интерес вызывает задача построения универсальной машины Тьюринга наименьшей сложности.

Может быть рассмотрено еще одно обобщение машин Тьюринга: их композиции. Операции композиции, выполняемые над алгоритмами, позволяют образовывать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга - алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них: произведение, возведение в степень, итерацию.

Пусть заданы машины Тьюринга T₁ и Т₂, имеющие общий внешний алфавит A = {a₀, a₁, …, а_m} и внутренние состояния Q₁ = {q₀, q₁, ..., q_n} и Q₂ = {q₀, g₁, ..., q_t} соответственно. Композицией или произведением машины T₁ и машины Т₂ будем называть машинуТ с тем же внешним алфавитом A = {a₀, a₁, …, а_m} и набором внутренних состояний Q = {q₀, q₁, …,q_n, q_n+1, …, q_n+t} и программой, эквивалентной последовательному выполнению программ машин Т₁ и Т₂:

T = T₁ * Т₂

Таким же образом определяется операция возведения в степень: n-й степенью машины T называется произведение T ... Т с n сомножителями.

Операция итерации применима к одной машине и определяется следующим образом. Пусть машина Т₁ имеет несколько заключительных состояний. Выберем ее r-е заключительное состояние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина является результатом итерации машины Т₁: T = Т₁.

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

При этом вначале строится какая-либо простая змейка в пространстве, проходящая через все его «кубики», подобно тому, как изображённая на рисунке спираль обходит все клетки плоскости, а дальше машина Тьюринга ходит по одномерной ленте, но понимает её как эту змейку. Конечно же, число шагов и сложность самой машины при этом возрастают, но с теоретической точки зрения это неважно.

Так что, когда теоретик Вам говорит, что нечто в Принципе можно сделать, почти всегда нужно понимать его «В теории можно, а на практике вряд ли!».

Точно так же можно иметь несколько одновременно работающих головок. Если разрешить вставлять и удалять ячейки под головкой, то и это моделируется обычной машиной. А обычная машина может быть смоделирована такой, у которой всего две головки, лента пустая, за исключением маркера начала ленты, головки могут лишь двигаться, но не писать, и не могут передвигаться левее маркера начала, либо такой машиной с одной головкой, которая может лишь записывать 1 вместо 0, но не может стирать однажды написанную единицу. Результатом при этом считается номер клетки, на которой остановилась первая головка.

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

Далее, если ввести две различные ленты: одну лишь для чтения, а другую лишь для записи, причём чтение и запись необратимы (после такой операции мы принудительно сдвигаемся вправо), то получается понятие «конечного автомата», существенно более слабое, чем машина Тьюринга. В частности, наша первая сложная машина делает то, что не может сделать конечный автомат. Конечный автомат может прибавить 1 к двоичному числу лишь в том случае, если число подаётся, начиная с младшего разряда.

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

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

Источники

· http://it.kgsu.ru/TI_5/falg_004.html;

· http://ru.wikipedia.org/wiki/Машина_Тьюринга;

· http://ru.wikipedia.org/wiki/Чего_не_могут_вычислительные_машины;

Размещено на Allbest.ru