рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Машина Тьюринга. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ   Понятие Конечного Автомата Возникло Из Близкого Понятия, Введ...

 

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

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

1) лента машины Тьюринга бесконечна;

2) машина Тьюринга может двигаться вдоль ленты в любом направлении.

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

Формальное определение машины Тьюринга следующее.

Определение 1:Машина Тьюринга – это пять объектов , из которых:

1) - есть конечный алфавит символов, которые могут быть записаны в ячейках и являются одновременно входными и выходными: ;

2) - есть конечное множество внутренних состояний, ;

3) -функция перехода в новое состояние, она действует из в ;

4) - функция выхода, ;

5) - функция, регулирующая движение ленты, она действует из во множество .

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

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

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

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

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

Остановка машины происходит после того, как будут выданы нужные результаты.

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

- текущее состояние машины;

- считываемый из ячейки символ;

- следующее состояние машины, ;

- символ, печатаемый в ячейке, ;

- одна из команд: .

Набор строк подобного вида называют программой работы машины Тьюринга.

В этих обозначениях описанная выше машина задается так:

,

,

,

,

,

,

,

,

Программы работы машины Тьюринга содержат все известные алгоритмические моменты (циклы, ветвления).

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

 

Теорема: Пусть - конечный автомат. Пусть и определены основные функции для всех :

,

,

Тогда машина Тьюринга ставит в соответствие входным строкам те же выходные строки, что и автомат .

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

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

Машины Тьюринга обладают большими возможностями, чем конечные автоматы. Можно, например, описать машины Тьюринга, вычисляющие разные функции от чисел, подаваемых на вход. Стандартным представлением неотрицательного числа в машине Тьюринга является последовательность из единиц, стоящих подряд. Два таких числа отделяются нулем. Например, строка ##111011## представляет упорядоченную пару чисел (3,2). Строка ##110111101## представляет собой последовательность чисел (2, 4, 1).

Пример: Следующая машина Тьюринга складывает два неотрицательных целых числа, поданных на вход:

,

,

,

,

,

,

,

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

 

– Конец работы –

Эта тема принадлежит разделу:

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Барабаш В В...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(2 семестр) (для студентов специальности «Прикладная математика», «Компьютерные системы и сети»)   У Т В Е Р Ж Д Е Н О на

Основные комбинаторные формулы.
  Существует два общих правила комбинаторики: правило сложения и правило умножения. Правило умножения: Пусть составляются всевозможные строки

Размещения.
  1) Размещения без повторений. Определение 2: Пусть имеется различных предметов.

Перестановки.
  1) Перестановки без повторений. Определение 3: Пусть - конечное множество из

Сочетания.
  1) Сочетания без повторений. Определение 3: Сочетания из элементов по

Свойства сочетаний. Бином Ньютона.
  Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след

Определение 1: Коэффициенты бинома Ньютона называются биномиальными коэффициентами.
Числовые значения биномиальных коэффициентов вычисляются по формуле числа сочетаний: . Готовые значения этих коэффициентов располагаются в с

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

Производящие функции.
  Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в ряде случаев рекуррентные соотношения трудно составить, а иногда ещё трудней решить. Часто эти труд

Алгоритм решения.
1°. Присвоить вершине метку 0. 2°. Если

Обоснование алгоритма.
Докажем, что после конечного числа применений правила 3° для каждой дуги графа станет справедливым неравенство

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

Обоснование алгоритма.
Пусть мы находимся в некоторой вершине . В исходном графе степень вершины

Потоки на транспортных сетях.
1. Основная задача теории транспортных сетей. Определение 1: Транспортная сеть есть совокупность

Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины.
1°. Перенумеровать произвольным образом вершины сети , отличные от входа

Обоснование алгоритма.
Прежде всего, заметим, что реализация алгоритма состоит из конечного числа шагов. В самом деле, п. 3° может применяться лишь конечное число раз, так как на каждом шаге величина пот

Теорема 1: Для заданной транспортной сети величина наибольшего потока равна наименьшей пропускной способности разрезов, т. е. .
Рис. 11 В качестве примера

Цикломатическое число графа. Деревья.
  Во многих прикладных задачах существенны свойства графов, связанные с существованием в графе замкнутых цепей (циклов). К рассмотрению этих вопросов мы и приступим. Все графы данного

Эйлерова характеристика. Плоские графы.
  Определение 1: Пусть задан набор отрезков гладких кривых на плоскости, причем выполнны следующие услов

Теорема 2: Графы и , где множество состоит из элементов вида , не допускают плоской реализации.
Доказательство: Отметим, что в графе нет циклов длины 3, так как любое ребро ведет из группы вершин

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

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

Автомат Мура.
  Определение:Конечным автоматом называется набор из 5 объектов , где:

Морфизмы.
  Пусть - конечный автомат. Тогда по любой входной строке длины

Эквивалентные состояния автоматов.
  В этом параграфе мы решим следующую задачу: по данному описанию автомата построить новый автомат

Теорема 1: Если , то либо , либо для подходящей строки имеем .
Доказательство: Утверждение означает, что для подходя

Не полностью описанные автоматы.
  До сих пор мы рассматривали полностью описанные автоматы. Практически функции и

Примитивно рекурсивные функции.
  Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычи

Частично рекурсивные функции.
  Оператор минимизации. Рассмотрим некоторую n - местную частичную функцию

Машины Тьюринга.
  Важный и широкий класс алгоритмов был описан Тьюрингом и Постом в 1936 - 1937 г. Алгоритмы этого класса осуществляются особыми машинами, называемыми сейчас машинами Тьюри

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги