Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


Определение 7.12. Машина Тьюринга определяется кортежем вида


[math]T=(Q,T,\star,\Box,S,L,R,q_0,q_f,\delta),[/math]

где [math]Q[/math] — конечное множество состояний; [math]V[/math] — конечный входной алфавит; [math]\star\notin V[/math] — символ, называемый маркером начала ленты; [math]\Box\notin V[/math] — символ, называемый пустым (или пробелом); [math]S,L,R\notin V[/math] — символы, называемые символами направления движения головки; [math]q_0\in Q[/math] — начальное состояние; [math]q_f\in Q[/math] — заключительное состояние; [math]\delta[/math] — функция переходов, являющаяся отображением вида


[math]\delta\colon Q\times(V\cup\{\star,\Box\})\to 2^{\{Q\times(V\cup\{\star,\Box\})\times (S,L,R)\}},[/math]

причем значение [math]\delta(q,a)[/math], коль скоро оно определено, есть конечное (возможно, и пустое) множество упорядоченных троек из соответствующего декартова произведения.


Функция переходов может быть записана в виде системы команд. Каждая команда есть слово вида


[math]qa\to rb,M,[/math]

где [math]a,b\in V\cup\{\star,\Box\}, M\in\{S,L,R\},\to\notin V\cup\{\star,\Box,S,L,R\}[/math].


Слово [math]qa[/math] (до стрелки) называется левой частью команды, а слово [math]rb,M[/math] (после стрелки) — правой частью команды.


Неформально работу машины Тьюринга можно представить следующим образом. Машина имеет устройство управления, которое может находиться в одном из состояний множества [math]Q[/math], полубесконечную ленту, разделенную на ячейки, в каждой из которой может быть записан символ из алфавита [math]V\cup\{\star,\Box\}[/math], причем крайняя левая ячейка хранит символ [math]\star[/math], и головку чтения-записи, которая в каждый момент дискретного времени обозревает какую-то одну ячейку ленты. Символ [math]\Box[/math] (пробел) не следует путать с пустой цепочкой — это специальный символ, означающий пустую, т.е. не хранящую символов алфавита [math]V\cup\{\star\}[/math], ячейку ленты. Команда, записанная выше, разрешает машине Тьюринга, устройство управления которой находится в состоянии [math]q[/math], а головка обозревает ячейку, хранящую символ [math]a[/math], перевести устройство управления в состояние [math]r[/math], записав в обозреваемую ячейку символ [math]b[/math] (который может и совпадать с [math]a[/math]), и оставить головку на прежнем месте, если [math]M=S[/math], сдвинуть ее на одну ячейку влево, если [math]M=L[/math], или на одну ячейку вправо, если [math]M=R[/math].


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


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




Конфигурация машины Тьюринга


Определение 7.13. Конфигурация машины Тьюринга [math]T[/math] есть кортеж


[math](q,x,y)\in Q\times (V\cup\{\star,\Box\})^{\ast}\times (V\cup\{\star, \Box\})^{\ast}.[/math]

Из конфигурации [math]C=(q,x,ay)[/math] непосредственно выводится конфигурация [math]C'=(r,x,by)[/math], если [math]qa\to rb,~S\in\delta[/math].


Из конфигурации [math]C=(q,xc,ay)[/math] непосредственно выводится конфигурация [math]C'=(r,x,cby)[/math], если [math]qa\to rb,~L\in\delta[/math].


Из конфигурации [math]C=(q,x,acy)[/math] непосредственно выводится конфигурация [math]C'=(r,xb,cy)[/math], если [math]qa\to rb,~R\in\delta[/math].


Выводом на множестве конфигураций машины Тьюринга называется произвольная последовательность конфигураций [math]C_0,C_1,\ldots,C_n,\ldots[/math], такая, что [math](\forall i\geqslant0)[/math]([math]C_i\vdash C_{i+1}[/math] если [math]C_{i+1}[/math] существует).


Конфигурация [math]C'[/math] выводима из конфигурации [math]C[/math], если существует вывод [math]C=C_0\vdash \ldots\vdash C_n=C'[/math]. Число [math]n[/math] называется при этом длиной вывода. Все обозначения, касающиеся выводимости на множестве конфигураций машин Тьюринга, остаются такими же, как в случае конечных и магазинных автоматов.


Конфигурация есть тройка (состояние, часть цепочки на ленте до головки, часть цепочки на ленте, первый символ которой обозревается головкой). При этом, по соглашению, любая цепочка из множества [math]x^{\Box^{\ast}}[/math] (для фиксированного [math]x\in (V\cup\{\star, \Box\})^{\ast}[/math]) отождествляется с цепочкой [math]x[/math], т.е. можно отбрасывать любое число пробелов в конце слова.




Детерминированная машина Тьюринга


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


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


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


Определение 7.15. Словарная (вербальная) функция в алфавите [math]V[/math] есть произвольное частичное отображение множества слов в алфавите [math]V[/math] в себя.


Определение 7.16. Будем говорить, что машина Тьюринга [math]T[/math] применима к слову [math]p\in V^{\ast}[/math], если из конфигурации [math](q_0,\lambda,\star p)[/math] выводится конфигурация [math](q_f,\lambda,\star s)[/math] для некоторого [math]s\in V^{\ast}[/math].


Слово [math]s[/math] будем называть в этом случае результатом применения машины Тьюринга [math]T[/math] к слову [math]p[/math] и обозначать его [math]T(p)[/math]. Факт применимости машины [math]T[/math] к слову [math]p[/math] будем обозначать [math]!T(p)[/math]; если же [math]T[/math] не применима к [math]p[/math], то будем записывать [math]\lnot!T(p)[/math].


Множество всех слов [math]p[/math], таких, что [math]!T(p)[/math], называется областью применимости машины Тьюринга [math]T[/math].


Определение 7.17. Словарная функция [math]\varphi[/math] в алфавите [math]V[/math] называется вычислимой по Тьюрингу, если существует такая машина Тьюринга [math]T_{\varphi}[/math] с входным алфавитом [math]V'[/math], содержащим [math]V[/math], что


[math]x\in D(\varphi)\quad \iff\quad !T_{\varphi}(x)\land \bigl(T_{\varphi}(x)= \varphi(x)\bigr),[/math]



Пример 7.15. Рассмотрим натуральное число [math]n[/math] как слово [math]0|^n[/math] в алфавите [math]\{0,\mid\}[/math], а сложение двух натуральных чисел зададим как словарную функцию [math]ADD[/math] в алфавите [math]\{0,\mid,\dagger\}[/math], преобразующую слово [math]0|^n\dagger0|^m[/math] в слово [math]0|^{n+m}[/math]. Тогда функция [math]ADD[/math] вычислима по Тьюрингу, поскольку приведенная ниже система команд определяет машину Тьюринга для сложения двух натуральных чисел:


[math]T_{ADD}= \bigl(\{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_8\},\, \{0,\mid,\dagger\},\, \star, \Box, S,L,R,q_0,q_5, \delta\bigr),[/math]

где система команд [math]\delta[/math] имеет следующий вид:


[math]\begin{array}{lrlrlrlr}q_0\star\to q_0\star,R,& (1) &\quad q_10\to q_1|,R,& (5) &\quad q_3|\to q_4\Box,L,& (9) &\quad q_8\star\to q_5\star,S,& (13) \\[2pt] q_00\to q_00,R,& (2) &\quad q_1|\to q_2|,R,& (6) &\quad q_4|\to q_8\Box,L,& (10) &\quad q_1\Box\to q_6\Box,L,& (14) \\[2pt] q_0|\to q_0|,R,& (3) &\quad q_2|\to q_2|,R,& (7) &\quad q_8|\to q_8\Box,L,& (11) &\quad q_6|\to q_7\Box,L,& (15) \\[2pt] q_0\dagger\to q_1|,R,& (4) &\quad q_2\Box\to q_3\Box,L,& (8) &\quad q_80\to q_80,L,& (12) &\quad q_7|\to q_8\Box,L.& (16) \end{array}[/math]

Определенная таким образом машина Тьюринга, получая "на вход" слово [math]0|^n\dagger0|^m[/math], где [math]n,m\geqslant0[/math], оставаясь в состоянии [math]q_0[/math] "бежит" вдоль ленты слева направо до тех пор, пока не встретит символ [math]\dagger[/math] (играющий роль "разделителя" двух слагаемых). "Увидев" этот символ, машина перейдет в состояние [math]q_1[/math], заменив символ [math]\dagger[/math] "палочкой" [math](\mid)[/math]. Следующий затем символ 0 (первый символ второго слагаемого) заменяется "палочкой". Таким образом, после "пробега" второго слагаемого в результирующем слове будет на две "палочки" больше, чем следует. Если второе слагаемое не равно 0, то после выполнения команды (5) будет применима команда (6), а после нее — команда (7). Тем самым будет прочитано второе слагаемое до ближайшего пробела, затем применением команд (8)-(10) будут стерты лишние "палочки", машина вернется к маркеру начала ленты и остановится в заключительной конфигурации. Если же второе слагаемое равно 0 (есть однобуквенное слово 0), то после выполнения команды (5) применяется команда (14), и затем посредством применения команд (15) и (16) машина сотрет две "палочки" и перейдет в заключительную конфигурацию.


Запишем тогда последовательность конфигураций для прибавления нуля к произвольному числу:


[math]\begin{aligned}(q_0,\lambda,\star0||\ldots|\dagger0)&\vdash (q_0,\star, 0||\ldots| \dagger 0)\vdash (q_0,\star0||\ldots|\dagger0)\vdash^{\ast} (q_0,\star 0||\ldots|, \dagger0)\vdash\\[2pt] &\vdash (q_1,\star0||\ldots||,0)\vdash (q_1,\star0||\ldots|||,\Box)\vdash (q_6,\star0||\ldots||, |\Box)\vdash (q_7,\star0||\ldots|,|\Box\Box)\vdash\\[2pt] &\vdash (q_8,\star0||\ldots,|\Box\Box\Box)\vdash^{\ast} (q_8,\star,0||\ldots|)\vdash (q_8,\lambda,\star||\ldots|) \vdash (q_5,\lambda,\star||\ldots|). \end{aligned}[/math]

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




Определение функции как процедуры


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


До построения какого-либо математического определения алгоритма мы имеем дело с интуитивным представлением об алгоритме. Это интуитивное понятие, не являющееся математически строгим (подобно тому как в рамках "наивной" теории множеств не является таковым понятие множества), может быть охарактеризовано следующими признаками:


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


2) признак результативности алгоритма — процесс работы алгоритма с исходными данными должен завершаться через определенное конечное число шагов;


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


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


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


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


Условимся в дальнейшем машину Тьюринга со входным алфавитом [math]V[/math] называть машиной Тьюринга в алфавите [math]V[/math], а машину Тьюринга, входной алфавит которой содержит алфавит [math]V[/math] и символы, не принадлежащие [math]V[/math], — машиной Тьюринга над алфавитом [math]V[/math]. Договоримся также "кодировать" натуральные числа словами в алфавите [math]N=\{0,\mid\}[/math], дав множеству [math]\mathbb{N}[/math] натуральных чисел следующее определение по индукции:


1) слово 0 есть натуральное число;
2) если известно, что слово [math]n[/math] в алфавите [math]N[/math] есть натуральное число, то слово [math]n|[/math] есть натуральное число;
3) никаких других натуральных чисел, кроме определенных в пунктах 1 и 2, не существует.

На множестве определенных таким образом натуральных чисел (как слов) естественно вводится отношение порядка: по определению, [math]n\leqslant m[/math], если [math]n[/math] есть префикс [math]m[/math]. Легко определить и обычные арифметические операции, "запрограммировав" их машинами Тьюринга (пример операции сложения разобран выше).


Определение 7.18. Непустое множество слов [math]L[/math] в алфавите [math]V[/math] называется перечислимым (по Тьюрингу), если существует машина Тьюринга [math]T[/math] над алфавитом [math]V\cup\{0,\mid\}[/math], такая, что для всякого [math]n\in\mathbb{N}[/math] есть [math]!T(n)[/math] и для всякого [math]x\in L[/math] имеет место [math]x=T(n)[/math] для некоторого [math]n\in\mathbb{N}[/math].


Таким образом, перечислимость языка [math]L[/math] означает существование алгоритма ("запрограммированного" как машина Тьюринга), по любому натуральному числу п вычисляющего элемент [math]L[/math] и такого, что любой элемент [math]L[/math] может быть вычислен по некоторому натуральному числу. Такой алгоритм есть алгоритмический ("конструктивный") аналог теоретико-множественного понятия нумерации как сюръективного отображения множества натуральных чисел на некоторое множество.


Замечание 7.14. Пустое множество слов считается перечислимым по соглашению.


Определение 7.19. Множество слов [math]L[/math] в алфавите [math]V[/math] называют разрешимым (по Тьюрингу), если существует такая машина Тьюринга [math]T[/math] над алфавитом [math]V[/math], что для всякого [math]x\in V^{\ast}[/math] имеет место [math]!T(x)[/math] и [math]T(x)=\lambda[/math], если [math]x\in L[/math], и [math]T(x)\ne\lambda[/math], если [math]x\notin L[/math].


Другими словами, разрешимость языка [math]L[/math] означает существование вычислимого предиката, определенного на множестве слов в алфавите [math]V[/math] и принимающего значение 1, если элемент принадлежит [math]L[/math], и значение 0 в противном случае.




Без доказательства сформулируем следующую теорему.


Теорема 7.14. 1. Существует неперечислимый язык в некотором алфавите [math]V[/math].

2. Существует перечислимый, но неразрешимый язык (в некотором алфавите [math]V[/math]).

3. Язык [math]L\subseteq V^{\ast}[/math] перечислим тогда и только тогда, когда он является областью применимости некоторой машины Тьюринга над алфавитом [math]V[/math].

4. Язык [math]L\subseteq V^{\ast}[/math] перечислим тогда и только тогда, когда он порождается некоторой грамматикой типа 0.

5. Язык [math]L\subseteq V^{\ast}[/math] разрешим тогда и только тогда, когда он порождается некоторой КЗ-грамматикой.


Из теоремы 7.14 следует, что всякое разрешимое множество перечислимо, но обратное неверно.


В силу утверждений 3 и 4 теоремы 7.14 машины Тьюринга можно рассматривать как wраспознающие автоматы" для языков типа 0: для каждого такого языка существует машина Тьюринга, применимая к словам данного языка, и только к ним. Заметим при этом, что язык типа 0 может оказаться и неразрешимым: для него может не существовать алгоритма, распознающего принадлежность ему любого наперед заданного слова. Это значит, что для грамматик типа 0 проблема принадлежности в общем случае не является разрешимой. Эта проблема, однако, как следует из утверждения 5 теоремы 7.14, разрешима для любого языка, порождаемого КЗ-грамматикой, в частности для любого КС-языка.


Утверждение 1 теоремы 7.14 означает, что существуют языки, которые не могут принципиально быть порождены какой-либо грамматикой. Примером такого языка может служить множество так называемых конструктивных действительных чисел.


Пример перечислимого, но неразрешимого языка может быть построен следующим образом. Пусть [math]V[/math] — алфавит, а [math]\rho[/math] — конечное бинарное отношение на множестве [math]V^{+}[/math] непустых слов в алфавите [math]V[/math]. Определим язык [math]L_{\rho}[/math] в алфавите [math]V\cup\{\star,\dagger\}[/math], где символы [math]\star[/math] и [math]\dagger[/math] не принадлежат [math]V\colon[/math]


[math]L_{\rho}= \bigl\{x_1\dagger y_1\star x_2\dagger y_2\star \ldots\star x_n\dagger y_n\colon\, n\geqslant1,~ x_1x_2\ldots x_n=y_1y_2\ldots y_n,~ (\forall i=\overline{1,n}) (x_i,y_i)\in \rho\bigr\}.[/math]

Доказывается, что язык [math]L_{\rho}[/math] в общем случае неразрешим, т.е. не существует алгоритма, который для любого наперед заданного отношения [math]\rho[/math] (при [math]|V|\geqslant2[/math]) распознавал бы слова языка [math]L_{\rho}[/math].


Проблема распознавания слов языка [math]L_{\rho}[/math] известна в теории алгоритмов под названием проблемы соответствий Поста (над алфавитом [math]V[/math]). Неразрешимость проблемы соответствий в общем случае не исключает того, что для каких-то конкретных алфавитов и конечных бинарных отношений на множестве непустых слов эту проблему можно решить. Например, пусть [math]V=\{a,b\}[/math], а [math]\rho=\{(aba,ab),(b,ab)\}[/math]. Нетрудно показать, что в данном случае


[math]L_{\rho}= \bigl\{(aba\dagger ab\star b\dagger ab)^n\colon\, n\geqslant1\bigr\}.[/math]

Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved