https://camokathomelab.servebeer.com/mediawiki/index.php?action=history&feed=atom&title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0Машина Тьюринга - История изменений2026-07-18T01:36:25ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://camokathomelab.servebeer.com/mediawiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0&diff=8566&oldid=previmported>43K1C7: откат правок 84.32.49.213 (обс.) к версии EyeBot2025-12-19T07:31:30Z<p><a href="/mediawiki/index.php?title=%D0%92%D0%9F:%D0%9E%D1%82%D0%BA%D0%B0%D1%82&action=edit&redlink=1" class="new" title="ВП:Откат (страница не существует)">откат</a> правок <a href="/mediawiki/index.php/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D0%BA%D0%BB%D0%B0%D0%B4/84.32.49.213" title="Служебная:Вклад/84.32.49.213">84.32.49.213</a> (<a href="/mediawiki/index.php?title=UT:84.32.49.213&action=edit&redlink=1" class="new" title="UT:84.32.49.213 (страница не существует)">обс.</a>) к версии EyeBot</p>
<p><b>Новая страница</b></p><div>[[Файл:Maquina.png|thumb|right|Художественное представление машины Тьюринга]]<br />
'''Маши́на Тью́ринга''' — абстрактный исполнитель (абстрактная вычислительная машина), математическая модель вычислений, предложенная [[Тьюринг, Алан Матисон|Аланом Тьюрингом]] в [[1936 год в науке|1936 году]] для [[формализация|формализации]] понятия [[алгоритм]]а.<br />
<br />
Машина Тьюринга является расширением [[конечный автомат|конечного автомата]] и, согласно [[тезис Чёрча — Тьюринга|тезису Чёрча — Тьюринга]], способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления является достаточно элементарным.<br />
<br />
То есть всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга{{sfn|Нефёдов|с=97|1992}}.<br />
<br />
Машина Тьюринга изначально была разработана как теоретический инструмент для изучения границ [[теория вычислимости|вычислимости]] и [[математическое доказательство|доказательства]] [[алгоритмическая разрешимость|невозможности существования алгоритмов]] для решения некоторых задач. Со временем она стала фундаментальной [[модель]]ю в [[теория сложности алгоритмов|теории сложности алгоритмов]], служит удобным инструментом для [[теория алгоритмов|формального исследования алгоритмов]]. С её помощью можно оценивать [[временная сложность алгоритма|временную сложность выполнения алгоритмов]] и объём памяти, требуемый для вычислений, включая абстрактные оценки, применимые к [[компьютер|реальным вычислительным системам]]<ref>{{Cite web |url=https://cyberleninka.ru/article/n/mashiny-tyuringa |title=Машины Тьюринга |access-date=2023-10-14 |archive-date=2024-01-05 |archive-url=https://web.archive.org/web/20240105195832/https://cyberleninka.ru/article/n/mashiny-tyuringa |url-status=live }}</ref>.<br />
<br />
== Устройство ==<br />
В состав машины Тьюринга входит неограниченная в обе стороны ''лента'' (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки{{sfn|Нефёдов|с=94|1992}}{{sfn|Эббинхауз|с=24|1972}}, и ''управляющее устройство'' (также называется ''головкой записи-чтения''), способное находиться в одном из ''множества состояний''. Число возможных состояний управляющего устройства конечно и точно задано.<br />
<br />
Управляющее устройство может перемещаться влево и вправо по ленте, оставаться в неподвижном положении, читать и записывать в ячейки символы некоторого конечного [[Алфавит (формальный язык)|алфавита]]. Выделяется особый ''пустой'' символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.<br />
<br />
Управляющее устройство работает согласно ''правилам перехода'', которые представляют алгоритм,<br />
''реализуемый'' данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку<br />
новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как ''терминальные'', и переход в любое из них означает конец работы, остановку алгоритма.<br />
<br />
Машина Тьюринга называется ''детерминированной'', если каждой комбинации состояния и<br />
ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется ''[[Недетерминированная машина Тьюринга|недетерминированной]]''.<br />
<br />
== Описание машины Тьюринга ==<br />
Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина. Они имеют вид: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub> (если головка находится в состоянии q<sub>i</sub>, а в обозреваемой ячейке записана буква a<sub>j</sub>, то головка переходит в состояние q<sub>i1</sub>, в ячейку вместо a<sub>j</sub> записывается a<sub>j1</sub>, головка делает движение d<sub>k</sub>, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q<sub>i</sub>, a<sub>j</sub>> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать начальное и конечное состояния, начальную конфигурацию на ленте и расположение головки машины.<br />
<br />
== Пример ==<br />
{{см. также|Ханойская башня#Решение для машины Тьюринга}}<br />
Пример машины Тьюринга для умножения чисел в [[Унарная система счисления|унарной системе счисления]].<br />
Запись правила перехода «q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>R/L/N» следует понимать так: q<sub>i</sub> — состояние, при котором выполняется это правило, a<sub>j</sub> — данные в ячейке, в которой находится головка, q<sub>i1</sub> — состояние, в которое нужно перейти, a<sub>j1</sub> — что нужно записать в ячейку, R/L/N — команда на перемещение.<br />
<br />
Машина работает по следующему набору правил:<br />
<br />
{| class="standard" align="center"<br />
|+<br />
! |<br />
! |q<sub>0</sub><br />
! |q<sub>1</sub><br />
! |q<sub>2</sub><br />
! |q<sub>3</sub><br />
! |q<sub>4</sub><br />
! |q<sub>5</sub><br />
! |q<sub>6</sub><br />
! |q<sub>7</sub><br />
! |q<sub>8</sub><br />
|-----<br />
!|1<br />
| q<sub>0</sub>1→q<sub>0</sub>1R<br />
| q<sub>1</sub>1→q<sub>2</sub>aR<br />
| q<sub>2</sub>1→q<sub>2</sub>1L<br />
| q<sub>3</sub>1 → q<sub>4</sub>aR<br />
| q<sub>4</sub>1→q<sub>4</sub>1R<br />
|<br />
|<br />
| q<sub>7</sub>1→q<sub>2</sub>aR<br />
|<br />
|-----<br />
!|×<br />
| q<sub>0</sub>×→q<sub>1</sub>×R<br />
|<br />
| q<sub>2</sub>×→q<sub>3</sub>×L<br />
|<br />
| q<sub>4</sub>×→q<sub>4</sub>×R<br />
|<br />
| q<sub>6</sub>×→q<sub>7</sub>×R<br />
|<br />
| q<sub>8</sub>×→q<sub>9</sub>×N<br />
|-----<br />
!|=<br />
|<br />
|<br />
| q<sub>2</sub>=→q<sub>2</sub>=L<br />
|<br />
| q<sub>4</sub>=→q<sub>4</sub>=R<br />
|<br />
|<br />
| q<sub>7</sub>=→q<sub>8</sub>=L<br />
|<br />
|-----<br />
!|a<br />
|<br />
|<br />
| q<sub>2</sub>a→q<sub>2</sub>aL<br />
| q<sub>3</sub>a→q<sub>3</sub>aL<br />
| q<sub>4</sub>a→q<sub>4</sub>aR<br />
|<br />
| q<sub>6</sub>a→q<sub>6</sub>1R<br />
| q<sub>7</sub>a→q<sub>7</sub>aR<br />
| q<sub>8</sub>a→q<sub>8</sub>1L<br />
|-----<br />
!|*<br />
| q<sub>0</sub>*→q<sub>0</sub>*R<br />
|<br />
|<br />
| q<sub>3</sub>*→q<sub>6</sub>*R<br />
| q<sub>4</sub>*→q<sub>5</sub>1R<br />
|<br />
|<br />
|<br />
|<br />
|-----<br />
!|<br />
|<br />
|<br />
|<br />
|<br />
|<br />
| q<sub>5</sub> →q<sub>2</sub>*L<br />
|<br />
|<br />
|<br />
|+<br />
|}<br />
<br />
Описание состояний:<br />
{| class="standard" border="1" cellpadding="5" cellspacing="0" align="center"<br />
| colspan="2" |''Начало''<br />
|-<br />
! width="50" |q<sub>0</sub><br />
| начальное состояние. Ищем «x» справа. При нахождении переходим в состояние q1<br />
|-<br />
! |q<sub>1</sub><br />
| заменяем «1» на «а» и переходим в состояние q2<br />
|-<br />
| colspan="2" |''Переносим все «1» из первого числа в результат''<br />
|-<br />
! |q<sub>2</sub><br />
| ищем «х» слева. При нахождении переходим в состояние q3<br />
|-<br />
! valign="top"|q<sub>3</sub><br />
| ищем «1» слева, заменяем её на «а» и переходим в состояние q4.<br />
В случае, если «1» закончились, находим «*» и переходим в состояние q6<br />
|-<br />
! |q<sub>4</sub><br />
| переходим в конец (ищем «*» справа), заменяем «*» на «1» и переходим в состояние q5<br />
|-<br />
! |q<sub>5</sub><br />
| добавляем «*» в конец и переходим в состояние q2<br />
|-<br />
| colspan="2" |''Обрабатываем каждый разряд второго числа''<br />
|-<br />
! |q<sub>6</sub><br />
| ищем «х» справа и переходим в состояние q7. Пока ищем, заменяем «а» на «1»<br />
|-<br />
! valign="top"|q<sub>7</sub><br />
| ищем «1» или «=» справа,<br />
при нахождении «1» заменяем его на «а» и переходим в состояние q2<br />
<br />
при нахождении «=» переходим в состояние q8<br />
|-<br />
| colspan="2" |''Конец''<br />
|-<br />
! |q<sub>8</sub><br />
| ищем «х» слева. При нахождении переходим в состояние q9. Пока ищем, заменяем «а» на «1»<br />
|-<br />
! |q<sub>9</sub><br />
| терминальное состояние (остановка алгоритма)<br />
|}<br />
<br />
Умножим с помощью МТ 3 на 2 в единичной системе.<br />
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).<br />
<br />
Начало. Находимся в состоянии q<sub>0</sub>, ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.<br />
<br />
1-й шаг. Смотрим по таблице правил, что будет делать машина, находясь в состоянии q<sub>0</sub> и над символом «*». Это правило из 1-го столбца 5-й строки — q<sub>0</sub>*→q<sub>0</sub>*R. Это значит, что мы переходим в состояние q<sub>0</sub> (то есть не меняем его), символ станет «*» (то есть не изменится) и смещаемся по введённому нами тексту «*111x11=*» вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q<sub>0</sub>1 (1-й столбец 1-я строка) обрабатывается правилом q<sub>0</sub>1→q<sub>0</sub>1R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ «х». И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.<br />
<br />
Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву «а», и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на «а» и дописывания такого же количества единиц в конце строки (слева от крайнего правого «*»). Затем меняем все «а» до знака умножения «х» обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой «а» и снова переносим единицы. Когда до знака «=» не окажется единиц — значит, умножение завершено.<br />
<br />
[[Файл:prot.gif|Протокол|center]]<br />
<br />
== Полнота по Тьюрингу ==<br />
{{main|Полнота по Тьюрингу}}<br />
Можно сказать, что машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам перехода преобразует входные данные с помощью последовательности ''элементарных действий''.<br />
<br />
Элементарность действий заключается в том, что действие меняет лишь небольшой фрагмент данных в памяти (в случае машины Тьюринга лишь одну ячейку), и число возможных действий конечно. Несмотря на простоту машины Тьюринга, на ней можно вычислить всё, что можно вычислить на любой другой машине, осуществляющей вычисления с помощью последовательности элементарных действий. Это свойство называется ''полнотой''.<br />
<br />
Один из естественных способов доказательства того, что алгоритмы вычисления, которые можно реализовать на одной машине, можно реализовать и на другой, это имитация первой машины на второй.<br />
<br />
Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины <math>D</math> и входные данные <math>X</math>, которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные <math>X</math>.<br />
<br />
Как было сказано, на машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.<br />
<br />
На машине Тьюринга можно имитировать [[Машина Поста|машину Поста]], [[Нормальный алгоритм|нормальные алгоритмы Маркова]] и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются ''полными по Тьюрингу'' (Turing complete).<br />
<br />
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но тем не менее всегда конечна. Теоретический предел количества информации, которая может находиться внутри заданной поверхности, с точностью до множителя <math>1 / \ln{2}</math> равен [[Энтропия|энтропии]] [[Чёрная дыра|чёрной дыры]] с той же площадью поверхности.<br />
<br />
== Варианты машины Тьюринга ==<br />
Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.<br />
<br />
=== Машина Тьюринга, работающая на полубесконечной ленте ===<br />
В качестве примера такого сведения рассмотрим следующую теорему: ''Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте (то есть на ленте, бесконечной в одну сторону).''<br />
<br />
Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых, произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:<br />
<br />
[[Файл:mt1.jpg|center]]<br />
<br />
Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:<br />
<br />
[[Файл:mt2.jpg|center]]<br />
<br />
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:<br />
<br />
[[Файл:mt3.jpg|center]]<br />
<br />
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.<br />
<br />
== См. также ==<br />
* [[Муравей Лэнгтона]] (двумерная машина Тьюринга)<br />
* [[Универсальная машина Тьюринга]]<br />
* [[Недетерминированная машина Тьюринга]]<br />
* [[Вероятностная машина Тьюринга]]<br />
* [[Квантовая машина Тьюринга]]<br />
* [[Диаграмма Тьюринга]]<br />
* [[Машина Минского]]<br />
;Другие абстрактные исполнители и формальные системы вычислений<br />
* [[Нормальный алгоритм|Нормальный алгоритм Маркова]] ([[продукционное программирование]])<br />
* [[Машина Поста]] ([[автоматное программирование]])<br />
* [[Частично рекурсивная функция]]<br />
<br />
== Примечания ==<br />
{{Примечания}}<br />
<br />
== Литература ==<br />
* {{книга<br />
|заглавие = Введение в теорию автоматов, языков и вычислений<br />
|часть = Глава 8. Введение в теорию машин Тьюринга<br />
|оригинал = Introduction to Automata Theory, Languages, and Computation<br />
|автор = [[Хопкрофт, Джон|Джон Хопкрофт]], Раджив Мотвани, Джеффри Ульман<br />
|ссылка =<br />
|isbn = 0-201-44124-1<br />
|страниц = 528<br />
|год = 2002<br />
|издание =<br />
|место = М.<br />
|издательство = [[Вильямс (издательство)|Вильямс]]<br />
}}<br />
* {{книга | автор = Карпов Ю. Г. | заглавие = Теория автоматов | ISBN = 5-318-00537-3 | издательство = Питер | год = 2003}}<br />
* {{книга | автор = Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г. | заглавие = Машины Тьюринга и рекурсивные функции | место = М. | издательство = Мир | год = 1972 | страниц = 262 | isbn = | ref = Эббинхауз}}<br />
* {{книга | автор = Нефёдов В. Н., Осипова В. А. | заглавие = Курс дискретной математики | место = М. | издательство = МАИ | год = 1992 | страниц = 260 | isbn = | ref = Нефёдов}}<br />
<br />
== Ссылки ==<br />
{{Навигация<br />
|Викиучебник = Машина Тьюринга<br />
}}<br />
* [http://postnauka.ru/video/10777 Машина Тьюринга] // Лекция [[Шень, Александр Ханиевич|Александра Шеня]] в проекте [[ПостНаука]] (06.04.2013)<br />
<br />
{{rq|<br />
{{нет сносок|дата=2009-07-01}}<br />
{{стиль статьи|дата=2019-01-03}}<br />
}}<br />
{{Формальные языки}}<br />
{{ВС}}<br />
<br />
[[Категория:Теория алгоритмов]]<br />
[[Категория:Теория сложности вычислений]]<br />
[[Категория:Модели вычислений]]<br />
[[Категория:Формальные методы]]<br />
[[Категория:Информационные машины]]<br />
[[Категория:Алан Тьюринг]]</div>imported>43K1C7