Каков принцип исполнения программы Машиной тьюринга

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

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

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

Конструирование машины Тьюринга

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

Описание машины Тьюринга [ ]

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации i, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

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

Приведём пример МТ для умножения чисел в унарной системе счисления . Машина работает по следующему набору правил:

Набор правил Набор правил

q0*→q0*R	q4a→q4aR
q01→q01R	q4=→q4=R
q0×→q1×R	q41→q41R
q11→q2aR	q4*→q51R
q21→q21L	q5*→q2*L
q2a→q2aL	q6a→q61R
q2=→q2=L	q6×→q7×R
q2×→q3×L	q7a→q7aR
q31 → q4aR	q71→q2aR
q3a→q3aL	q7=→q8=L
q3*→q6*R	q8a→q81L
q4×→q4×R	q8×→q9H

Машина Тьюринга в двух словах.

Умножим с помощью МТ 3 на 2 в единичной системе:

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

Полнота по Тьюрингу [ ]

Основная статья: Полнота по Тьюрингу

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

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

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

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

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

На машине Тьюринга можно имитировать Варианты машины Тьюринга [ ]

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

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

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

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.

Двумерные машины Тьюринга [ ]

См. также [ ]

• Универсальная машина Тьюринга
• Недетерминированная машина Тьюринга
• Вероятностная машина Тьюринга
• Другие абстрактные исполнители и формальные системы вычислений [ ]

• Рекурсивная функция (теория вычислимости)
• Ссылки [ ]

Литература [ ]

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Машина Тьюринга. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

Источник: vlab.fandom.com

МАШИНА ТЬЮРИНГА. ПРИНЦИПЫ РАБОТЫ И РАЗЛИЧНЫЕ ВАРИАЦИИ Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Колесников Павел Олегович, Голубничий Артем Александрович

Статья рассказывает об истории развития машины Тьюринга и описывает её основные принципы работы. Представлены различные вариации машины Тьюринга , в том числе, описан алгоритм работы муравья Лэнгтона.

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Колесников Павел Олегович, Голубничий Артем Александрович

Об асимптотике сложности машин Тьюринга, вычисляющих некоторые бесконечные семейства функций
Полная Алгоритмическая доопределимость любых алгоритмов, работающих на ограниченной памяти
МАШИНА ТЬЮРИНГА
Детерминированные машины Тьюринга и искусственный интеллект
О сложности построения таблицы простых чисел на машине Тьюринга

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

THE TURING MACHINE. PRINCIPLES OF OPERATION AND VARIOUS VARIATIONS

The article tells about the history of the development of the Turing machine and describes its basic principles of operation. Various variations of the Turing machine are presented, including the algorithm of operation of the Langton ant.

Текст научной работы на тему «МАШИНА ТЬЮРИНГА. ПРИНЦИПЫ РАБОТЫ И РАЗЛИЧНЫЕ ВАРИАЦИИ»

Научная статья Original article

МАШИНА ТЬЮРИНГА. ПРИНЦИПЫ РАБОТЫ И РАЗЛИЧНЫЕ

THE TURING MACHINE. PRINCIPLES OF OPERATION AND VARIOUS

Голубничий Артем Александрович, Старший преподаватель кафедры ПОВТиАС ХГУ им Н. Ф. Катанова (655017 Россия, г. Абакан, ул. проспект Ленина д.92/1)

Artem A. Golubnichy, Senior Lecturer of the Department of POVTiAS of N. F. Katanov KSU (92/1 Lenin Avenue, Abakan, 655017 Russia)

Аннотация. Статья рассказывает об истории развития машины Тьюринга и описывает её основные принципы работы. Представлены различные вариации машины Тьюринга, в том числе, описан алгоритм работы муравья Лэнгтона. Abstract. The article tells about the history of the development of the Turing machine and describes its basic principles of operation. Various variations of the

Turing machine are presented, including the algorithm of operation of the Langton ant.

Ключевые слова: Машина Тьюринга, алгоритм, правила, Алан Тьюринг, бесконечная лента.

Keywords: Turing machine, algorithm, rules, Alan Turing, infinite tape.

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

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

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

Сама машина может называться недетерминированной, если существует пара «ленточный символ — состояние», и для нее существует две и более

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

Алонзо Чёрч и Алан Тьюринг утверждали, что с помощью некоторой машины Тьюринга любая интуитивно вычислимая функция является частично вычислимой. Данный тезис невозможно опровергнуть или доказать, считается, что он устанавливает «равенство» между неформальным понятием «интуитивно вычислимой функции» и формализованным понятием частично вычислимой функции [1]. Машина Тьюринга представлена на рисунке 1.

Рисунок 1 — Машина Тьюринга [2] Согласно формальным правилам, машина Тьюринга преобразует входные данные с помощью последовательности элементарных действий. Из-за того, что какое-то действие меняет лишь одну ячейку, и возможные действия не могут быть бесконечными, в этом и заключается элементарность действий. Какой бы простой не казалась эта машина, на ней возможно вычислить все, что можно было бы выполнить на другой машине, в которой вычисления происходят последовательно.

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

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

Безусловно в настоящее время имеются и программы, которые могут имитировать работу данной машины, но происходит это не в полной мере, так как бесконечную ленту с данными невозможно имитировать на персональном компьютере, у которого память является конечной. Даже с учетом развития технологий, компании с каждым годом увеличивают объемы оперативной памяти, жестких дисков, кэш процессоров, но ограничение памяти никуда не уходит, она все также является конечной [3].

Существует множество различных вариаций машин Тьюринга:

— Универсальная — такая машина может заменить любую другую машину Тьюринга;

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

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

— Машина Минского — у данной машины лента слева не надстраивается [4].

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

Если попал на черный квадрат, то муравей поворачивает на 90 градусов влево, меняет цвет квадрата на белый и делает шаг вперед;

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

На первый взгляд простые правила, приводят к сложному поведению муравья, после некоторого времени работы, случайные движения муравья, приводят к тому, что начинается строительство дороги из 104 шагов, которые повторяются бесконечно, и что самое удивительно это не зависит от начальной раскраски клеток [5]. Магистраль муравья представлена на рисунке 2.

Рисунок 2 — Магистраль муравья Лэнгтона[6] Появление машины Тьюринга внесло огромный вклад в развитии информатики, допустим в бытовых приборах могут использоваться одни и те же микросхемы процессора.

1. Алан Тьюринг и его машина | Эрудит.Онлайн | Яндекс Дзен [Электронный ресурс]. — URL:

https://zen.yandex.ru/media/id/5e50e884n638a2a18c13e31/alan-tiuring-i-ego-mashina-60d2fe3879e5ef3dd632f68f (дата обращения 17.01.2022)

2. JavaScript Is Turing Complete— Explained | by rajaraodv [Электронный ресурс]. — URL: https://medium.com/free-code-camp/javascript-is-turing-complete-explained-41a34287d263 (дата обращения 17.01.2022)

3. Машина Тьюринга [Электронный ресурс]. — URL: https://studfile.net/preview/2428911/ (дата обращения 17.01.2022)

4. Машина Тьюринга — Википедия [Электронный ресурс]. — URL: https://ru.wikipedia.org/wiki/Машина_Тьюринга (дата обращения 17.01.2022)

5. Муравей Лэнгтона — Википедия [Электронный ресурс]. — URL: https://ru.wikipedia.org/wiki/Муравей_Лэнгтона (дата обращения 17.01.2022)

6. Муравей Лэнгтона — загадочный клеточный автомат / Хабр [Электронный ресурс]. — URL: https://habr.com/ru/post/599275/ (дата обращения 17.01.2022)

1. Alan Turing and his machine | A polymath.Online | Yandex Zen [Electronic resource]. — URL: https://zen.yandex.ru/media/id/5e50e88411638a2a18c13e31/alan-tiuring-i-ego-mashina-60d2fe3879e5ef3dd632f68f (дата обращения 17.01.2022)

2. JavaScript Is Turing Complete— Explained | by rajaraodv [Electronic resource]. — URL: https://medium.com/free-code-camp/javascript-is-turing-complete-explained-41a34287d263 (дата обращения 17.01.2022)

3. Turing Machine [Electronic resource]. — URL: https://studfile.net/preview/2428911/ (дата обращения 17.01.2022)

4. Turing Machine — Wikipedia [Electronic resource]. — URL: https://ru.wikipedia.org/wiki/Машина_Тьюринга (дата обращения 17.01.2022)

5. Langton’s Ant — Wikipedia [Electronic resource]. — URL: https://ruwikipedia.org/wiki/Муравей_Лэнгтона (дата обращения 17.01.2022)

6. Langton’s Ant — a mysterious cellular automaton / Habr [Electronic resource]. — URL: https://habr.com/ru/post/599275/ (дата обращения 17.01.2022)

Для цитирования: Колесников П.О., Голубничий А.А. МАШИНА ТЬЮРИНГА. ПРИНЦИПЫ РАБОТЫ И РАЗЛИЧНЫЕ ВАРИАЦИИ // Научно-образовательный журнал для студентов и преподавателей №1/2022.

Источник: cyberleninka.ru

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

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

Введение

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

Эта научная работа послужила стимулом к более углублённому изучению цифрового исчисления и компьютерных устройств, в том числе осознание мысли, что есть проблематика в сфере вычислений, которую нельзя решить на обычных электронных вычислительных машинах пользователей

Сдай на права пока
учишься в ВУЗе
Вся теория в удобном приложении. Выбери инструктора и начни заниматься!

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

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

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

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

«Машина Тьюринга»
Готовые курсовые работы и рефераты
Решение учебных вопросов в 2 клика
Помощь в написании учебной работы

Машина осуществляет связь двух конечных рядов информационных данных, а именно алфавит знаков на входе $A = (a_0, a_1, …, a_m)$ и алфавит состояний $Q = (q_0, q_1, . q_p)$. Пассивным считается состояние $q_0$. Предполагается, что машина прекращает выполнение операций, когда считывает именно его.

Исходным состоянием является состояние $q_1$, и устройство запускается в работу, когда считывает это стартовое состояние. Слово на ленте, которое является входной информацией, расположено последовательно по одной букве в позиции. При этом, впереди него и за ним расположены нулевые квадраты.

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

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

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

1. Записать в текущую ячейку нужный знак.
2. Выполнить смену текущего состояния.
3. Переместиться в заданную сторону вдоль ленты.

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

1. Свойство дискретности. Цифровое устройство выполняет переход к очередному этапу n+1 лишь после полного завершения предыдущего. Каждый завершенный шаг определяет, каким будет следующий.
2. Свойство понятности. Машина осуществляет лишь одну операцию для выбранной ячейки. Она записывает алфавитный символ и выполняет одно перемещение в указанную сторону.
3. Свойство детерминированности. Всем позициям в машине сопоставляется только один вариант осуществления задаваемой схемы, и на всех шагах операции и их очерёдность осуществления строго определены.
4. Свойство результативности. Окончательный итог на каждом шаге вычисляет машина Тьюринга. Программа работает согласно заданному алгоритму и за не бесконечное количество выполненных этапов доходит до состояния $q_0$.
5. Свойство массовости. Каждой машине сопоставлен набор допустимых слов, которые входят в алфавит.

Функции машины Тьюринга

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

Рисунок 1. Функции машины Тьюринга. Автор24 — интернет-биржа студенческих работ

Программа для машины Тьюринга

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

Источник: spravochnick.ru