Машина тьюринга четность числа

3645 теория автоматов в задачах

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

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

2.1. Схема МТ. Назначение компонентов

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

Рис. 2.1. Машина Тьюринга

2.2. Работа МТ

Работа МТ – это последовательность тактов, каждый из которых включает четыре действия:

— считывание головкой символа с ленты;

— изменение внутреннего состояния МТ;

— запись нового символа на место считанного (это может быть и стирание

прежнего символа либо МТ оставляет старый);

— сдвиг головки на одну ячейку(влево или вправо).

Работа МТ описывается системой из 3-х уравнений:

2.3. Примеры машин Тьюринга

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

Источник

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

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

Заслуженный участник

Последний раз редактировалось Deggial 16.11.2013, 09:37, всего редактировалось 1 раз.

формулы поправил

А что это за вид? Обычно же вид такой: .

Последний раз редактировалось cool.phenon 10.05.2013, 11:55, всего редактировалось 1 раз.

Этот вид предложил преподаватель, впоследствии такой же я обнаружил в учебнике «Введение в дискретную математику» Яблонского.

Ну тут тоже вроде похоже, только вместо использую 0.

А вот тут можно поподробнее? Не очень понятно, как это конкретно делается. Вообще не понятно, как на этом языке реализовать условие. Предполагаю

A вот умножать- что- то совсем глухо. Не могли бы вы поподробнее объяснить?

Заслуженный участник

Последний раз редактировалось Sonic86 10.05.2013, 13:55, всего редактировалось 1 раз.

Так, я домыслю: , — состояния МТ, — шаги.

Заслуженный участник

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

Вот, попробовал нечто другое.

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

Но вот тут у меня проблема, допустим, сложил один раз, но дальше мне уже нужно знать, сколько именно единиц слева или справа нужно приписать, а этого в машине Тьюринга никак не напишешь. Что здесь можно сделать?

Заслуженный участник

Последний раз редактировалось Sonic86 10.05.2013, 17:39, всего редактировалось 4 раз(а).

А зачем писать запятые?

Заслуженный участник

Последний раз редактировалось cool.phenon 10.05.2013, 18:24, всего редактировалось 3 раз(а).

Заслуженный участник

(О структурном подходе.)

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

Научный форум dxdy

Правила форума

В этом разделе нельзя создавать новые темы.

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

Заслуженный участник

Последний раз редактировалось arseniiv 10.05.2013, 18:56, всего редактировалось 1 раз.

Заслуженный участник

Xaositect
Ага, значит, нужно все скопированные единицы влево, а еще по одной дописывать справа, я правильно Вас понял?

Заслуженный участник

Последний раз редактировалось Sonic86 10.05.2013, 19:28, всего редактировалось 6 раз(а).

Заслуженный участник

Последний раз редактировалось cool.phenon 10.05.2013, 19:29, всего редактировалось 1 раз.

Заслуженный участник

Последний раз редактировалось Sonic86 10.05.2013, 20:04, всего редактировалось 5 раз(а).

Заслуженный участник

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

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

Содержание

Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:

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

Определение [ править ]

Определение машины [ править ]

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

Определение процесса работы [ править ]

Особо следует рассмотреть случай переходов по пробельному символу:

Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

Результат работы [ править ]

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

Примеры машин Тьюринга [ править ]

Прибавление единицы [ править ]

Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:

[math]0[/math]	[math]1[/math]	[math]B[/math]
[math]S[/math]	[math]\langle R, 1, \downarrow \rangle[/math]	[math]\langle S, 0, \rightarrow \rangle[/math]	[math]\langle R, B, \leftarrow \rangle[/math]
[math]R[/math]	[math]\langle R, 0, \leftarrow \rangle[/math]	[math]\langle R, 1, \leftarrow \rangle[/math]	[math]\langle Y, B, \rightarrow \rangle[/math]

Проверка того, является ли слово палиндромом [ править ]

[math]0[/math]	[math]1[/math]	[math]B[/math]
[math]S[/math]	[math]\langle F_0, B, \rightarrow \rangle[/math]	[math]\langle F_1, B, \rightarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]F_0[/math]	[math]\langle F_0, 0, \rightarrow \rangle[/math]	[math]\langle F_0, 1, \rightarrow \rangle[/math]	[math]\langle B_0, B, \leftarrow \rangle[/math]
[math]F_1[/math]	[math]\langle F_1, 0, \rightarrow \rangle[/math]	[math]\langle F_1, 1, \rightarrow \rangle[/math]	[math]\langle B_1, B, \leftarrow \rangle[/math]
[math]B_0[/math]	[math]\langle R, B, \leftarrow \rangle[/math]	[math]\langle N, 1, \downarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]B_1[/math]	[math]\langle N, 0, \downarrow \rangle[/math]	[math]\langle R, B, \leftarrow \rangle[/math]	[math]\langle Y, B, \downarrow \rangle[/math]
[math]R[/math]	[math]\langle R, 0, \leftarrow \rangle[/math]	[math]\langle R, 1, \leftarrow \rangle[/math]	[math]\langle S, B, \rightarrow \rangle[/math]

Варианты машины Тьюринга [ править ]

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

Многодорожечная машина Тьюринга [ править ]

Машина Тьюринга с полубесконечной лентой [ править ]

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

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

Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. [math]\triangleleft[/math]

Многоленточная машина Тьюринга [ править ]

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

Универсальная машина Тьюринга [ править ]

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

Источник

Машина тьюринга четность числа

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

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

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

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

A= — внешний алфавит, служит для записи исходных данных

Q= — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = (В нашем случае A=<0, 1>)

Допустимые действия Машины Тьюринга таковы:

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

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

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

Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = . В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «

Источник

Утверждение (Тезис Чёрча-Тьюринга):