1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 15
Текст из файла (страница 15)
1Команда kСостояние:qm q0 q1r¡µ q2¦q3¦¦§ 15. Машины Тьюринга61няется следующим образом: в обозреваемую ячейку записывается символ al , затемголовка сдвигается по ленте на одну ячейку вправо (если S = R), или влево (еслиS = L), или вообще не двигается (если S — пустое слово), и затем машина переходитв состояние qk .Если при исполнении некоторой команды головке необходимо сдвинуться за левый край ленты, то в этот момент происходит автоматическое достраивание новойячейки слева, в нее записывается выделенный символ (как правило, это символ 0)и головка передвигается на достроенную ячейку.
Аналогичным образом происходитдостраивание ячеек справа.Теперь мы введем строгие, формальные определения.Определение. Машина Тьюринга — это пятерка T = hA, Q, P, q1 , q0 i, где:а) A = {a0 , a1 , . . . , an } — конечный внешний алфавит (мы будем всегда предполагать, что n > 1 и a0 = 0, a1 = 1);б) Q = {q0 , q1 , . . . , qm } — конечный алфавит внутренних состояний;в) P = {T (i, j) | 1 6 i 6 m, 0 6 j 6 n} — программа, состоящая из команд T (i, j),каждая из которых есть слово вида: qi aj → qk al , или qi aj → qk al R, или qi aj → qk al L,где 0 6 k 6 m, 0 6 l 6 n;г) q1 — начальное состояние;д) q0 — конечное состояние.Определение. Машинным словом (конфигурацией) называется любое слово видаAqi aj B, где qi ∈ Q, aj ∈ A, A и B — слова в алфавите A (возможно, пустые).qiAA ¢a3 a2 a0 a0 a1 aj a4 a0 a1 a2§A¦§B¦Машинное слово Aqi aj B — это формальное представление текущего положениявсех деталей машины: qi — текущее состояние, aj — содержимое ячейки, обозреваемой головкой в данный момент, слово A состоит из всех символов, содержащихсяв ячейках слева от обозреваемой, слово B состоит из всех символов, записанных вячейках справа от обозреваемой.
Исходя из такого интуитивного смысла, несложно определить формально, как преобразуются машинные слова за один шаг работымашины.Определение. Пусть M = Aqi aj B — машинное слово. Говорят, что машинное словоMT0 получается из M за один шаг работы машины Тьюринга T , если выполняетсяодно из условий:1) i = 0, MT0 = M .2) i > 0 и выполняется один из случаев:а) T (i, j) имеет вид qi aj → qk al , и MT0 = Aqk al B;б) T (i, j) имеет вид qi aj → qk al R, B = as B 0 , и MT0 = Aal qk as B 0 ;62Глава III.
Формализации понятия вычислимой функциив) T (i, j) имеет вид qi aj → qk al R, B = Λ, и MT0 = Aal qk a0 (достраиваетсяновая ячейка справа);г) T (i, j) имеет вид qi aj → qk al L, A = A0 as , и MT0 = A0 qk as al B;д) T (i, j) имеет вид qi aj → qk al L, A = Λ, и MT0 = qk a0 al B (достраиваетсяновая ячейка слева).(0)(k+1)Определение. Пусть M = Aqi aj B — машинное слово. Положим MT = M , MT=³´0(k)MTдля всех k ∈ ω.Говорят, что машина T перерабатывает слово M в слово M1 без достраивания(k)ячеек слева, и пишут M =⇒ M1 , если существует k ∈ ω такое, что MT = M1 и приTэтом не используется пункт (д).Говорят, что машина T перерабатывает слово M в слово M1 без достраивания(k)ячеек слева и справа, и пишут M |=⇒ M1 , если существует k ∈ ω такое, что MT = M1Tи при этом не используются пункты (в) и (д).Определение.
Говорят, что машина Тьюринга T (правильно) вычисляет частичную n-местную функцию f : dom(f ) ⊆ ω n −→ ω, если для любых x1 , . . . , xn ∈ ωвыполняются условия:а) если hx1 , . . . , xn i ∈ dom(f ), то q1 01x1 0 . . . 01xn 0 =⇒ q0 01f (x1 ,...,xn ) 00s , для некотоTрого s > 0;б) если hx1 , .
. . , xn i ∈/ dom(f ), то машина T , начав работу с машинного слова M =(k)x1xnq1 01 0 . . . 01 0, работает бесконечно, т. е. q0 не входит в MT ни для какогоk ∈ ω.Определение. Частичная функция f называется вычислимой по Тьюрингу, еслисуществует машина Тьюринга T , которая ее правильно вычисляет.Теорема 42. Частичная функция вычислима по Тьюрингу тогда и только тогда,когда она является частично рекурсивной.Доказательство. Мы приведем лишь схему доказательства.
Более подробное и детальное доказательство этой важнейшей теоремы будет предложено в курсе по математической логике.Чтобы доказать, что любая ч.р.ф. вычислима по Тьюрингу, нужно построитьмашины, вычисляющие все простейшие функции, и доказать, что функции, полученные из вычислимых по Тьюрингу функций с помощью операторов S, R, или M ,также вычислимы по Тьюрингу.Доказательство частичной рекурсивности любой функции, вычислимой по Тьюрингу, состоит из нескольких этапов:а) Сначала необходимо закодировать все команды:код(qi aj → qk al ) =< i, j, k, l, 0 >,код(qi aj → qk al R) =< i, j, k, l, 1 >,код(qi aj → qk al L) =< i, j, k, l, 2 > .§ 15.
Машины Тьюринга63б) Затем нужно закодировать все программы. Если P — программа, состоящая изкоманд c0 , . . . , cs (порядок расположения команд в программе не важен), токод(P ) =< код(c0 ), . . . , код(cs ) > .в) Далее кодируем все машинные слова. Если M = aj0 . . . ajp−1 qi ajp ajp+1 . . . ajr —машинное слово, токод(M ) =< j0 , . . . , jr , i, p > .Кодировки, введенные в пунктах (а), (б), (в), являются эффективными, по кодукоманды (программы, машинного слова) можно однозначно восстановить видсамой команды (программы, машинного слова).г) Кодом вычисления на машине Тьюринга T , начатого в конфигурации M , назовем натуральное число < код(M0 ), .
. . , код(Mt ) >, где M = M0 , M1 , . . . , Mt —машинные слова, такие, чтоM0 =⇒ M1 =⇒ . . . =⇒ Mt ,TTT(k)причем Mk = MT для каждого k ∈ {0, . . . , t}, слово Mt содержит вхождение q0 ,а остальные слова Mi (i < t) не содержат q0 (другими словами, в конфигурацииMt произошла остановка машины).(k)Если для любого k ∈ ω слово MT не содержит q0 , т. е.
машина не останавливается, то код вычисления не определен.д) Для фиксированного k ∈ ω определим (k+2)-местный T -предикат Клини:Tk (e, x1 , . . . , xk , y) ⇐⇒ e — код некоторой программы P, а y — кодвычисления на машине Тьюринга с программой P,начатого в конфигурации q1 01x1 0 . . . 01xk 0.Необходимо доказать, что предикат Tk рекурсивен.е) Определим одноместную функцию U следующим образом:U (y) = z ⇐⇒ y — код вычисления, оканчивающегося на машинномслове вида q0 01z 00s для некоторого s > 0, т.
е. z — результатэтого вычисления.Необходимо доказать, что функция U рекурсивна.ж) Наконец, если f (x1 , . . . , xk ) вычислима на машине Тьюринга по программе с кодом e, то нужно доказать, что имеет место представление в нормальной форме,т.
е.f (x1 , . . . , xk ) = U (µy[Tk (e, x1 , . . . , xk , y)]).Отсюда будет следовать, что f — ч.р.ф.64Глава III. Формализации понятия вычислимой функцииСуществует несколько модернизаций и обобщений машин Тьюринга. Наиболее известной и естественной модернизацией является многоленточная машина Тьюринга,т. е.
машина, которая имеет k (k > 1) лент и такое же число считывающих головок.Однако вычислительные возможности таких машин не отличаются от возможностейобычных машин Тьюринга.Другое обобщение — недетерминированные машины Тьюринга, т. е. машины,в программе которых для некоторых состояний qi и некоторых внешних символовaj могут присутствовать несколько различных команд, начинающихся с символовqi aj → . .
. К машинам такого типа мы еще вернемся в главе, посвященной теориисложности вычислений.§ 16.Нормальные алгорифмы МарковаВ данном параграфе будет предложено краткое введение в теорию нормальных алгорифмов Маркова, которые являются еще одной (в нашем курсе — уже четвертой)формализацией понятия вычислимости. Этот подход основан на том, что любые наборы данных и любые программы для алгоритмов, работающих с этими данными,могут быть представлены в виде некоторых текстов и даже в виде слов (если считать пробелы между словами, знаки препинания и символы перехода на новую строку полноправными буквами алфавита), а сам алгоритм может быть рассмотрен какпроцесс преобразования слов.Таким образом, алгорифмы Маркова — это словарные алгоритмы, принцип действия которых напоминает работу формальных грамматик: так же как и в грамматиках, алгорифмы Маркова преобразуют слова путем замены одних подслов на другие.Однако есть ряд существенных отличий.
По сравнению с формальными грамматиками нормальные алгорифмы Маркова имеют входные данные и зависящие от нихвыходные данные. Кроме этого, действия нормального алгорифма на каждом шагестрого детерминированны. Эта детерминированность достигается с помощью следующих двух принципов. Во-первых, на каждом шаге работы алгорифма для слова wоднозначно определены подслово u и то вхождение u в w, которое будет подвергаться замене на некоторое другое слово. Во-вторых, однозначно определено то правилоподстановки u → v, с помощью которого осуществляется подобная замена. Заметимтакже, что на некоторых входных словах нормальные алгорифмы Маркова могутработать бесконечно, никогда не останавливаясь.Перейдем теперь к точным формулировкам (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
