Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 115

11.4.2. Вариант машины Тьюринга с использованием рандомизации Для того чтобы абстрактно представить способность машин Тьюринга к совершению случайного выбора, похожего на вызов генератора случайных чисел в программе, используем вариант многоленточной МТ, изображенный на рис. 11.6. Первая лента, как обычно для многоленточных машин, содержит вход. Вторая лента также начинается не- пустыми ктетками.

В принципе, вся она содержит символы 0 и 1, выбранные с вероятностью 1/2. Вторая лента называется случайной' летной. Третья и последующие, если используются, вначале пусты и при необходимости выступают как рабочие. Данный вариант МТ называется рандомизированной машиной Тьюринга. Аназнз и обоснование ожидаемого времени выполнения быстрой сортировки можно найти в следующих изданиях. О.

Е. Кпнйь Тне Аг/ о/ Сотри/ег Ргоягатттй, Го/. П!: богине аиг/ Зеагсй/ий, Адд1зов-%ее|ау, 1973. (Кнэт Д. Искусство программирования для ЭВМ. В 3 т. Т. 3: Поиск и сортировка. — Мг Мнр, 1976. См. также; Кнут Д. Искусство программирования. В 3 т. Т. 3: Поиск н сортировка. — Мг Издательский лом "Вильямс", 2000.) 500 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ Случайные биты Рабочая лента (ленты ! Рис. !!.б.

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

При таком способе отсутствует бесконечная работа, которую нужно было бы совершить перед началом работы рандомизированной МТ. Тем не менее, вторая лента оказывается покрытой случайными символами 0 и 1, поскольку эти случайные биты появляются везде, где в действительности побывала головка второй ленты МТ. Пример 11.12. Рандомизированную версию быстрой сортировки можно реализовать с помошью МТ. Важным шагом является следующий рекурсивный процесс.

Предположим, что подсписок сохранен в последовательных клетках входной ленты и выделен маркерами с обоих концов. В подсписке выбирается ведущий элемент, и подсписок делится на нижний и верхний подподсписки. Рандомизированная МТ выполняет такие действия. 1. Пусть разделяемый подсписок имеет длину нт. Используем до !оке т новых случайных битов на второй ленте, чтобы выбрать случайное число между 1 и нт; нт-й элемент подсписка становится ведушим.

Отметим, что, возможно, вероятности выбора чисел от 1 до га не равны„поскольку е может не быть степенью 2. Однако, если взять, например, ~2 !ояттн1битов с ленты 2, рассмотреть нх как число в диапазоне от 0 до т', взять остаток от деления на т и прибавить 1, то все числа от 1 до га будут иметь вероятность, достаточно близкую к !/тн, чтобы быстрая сортировка выполня- лась корректно.

2. Поместить ведуший элемент на ленту 3. 3. Просмотреть список, выделенный на ленте 1, копируя элементы, которые не больше ведушего, на ленту 4. 11.4. КЛАССЫ ЯЗЫКОВ, ОСНОВАННЫЕ НА РАНДОМИЗАЦИИ 501 4, Снова просмотреть подсписок на ленте 1, копируя элементы, которые больше ведущего, на ленту 5. 5. Скопировать ленты 4 и затем 5 в пространство на ленте 1, ранее занятое выделенным подсписком. Поместить маркер между двумя подподсписками. 6.

Если подподсписки (хотя бы один из них) содержат более одного элемента, рекурсивно отсортировать их по этому же алгоритму. Заметим, что данная реализация быстрой сортировки требует О(н!одп) времени, хотя вычислительным устройством является МТ, а не обычный компьютер. Однако главное в этом примере — не время работы, а использование случайных битов на второй ленте для организации случайного поведения машины Тьюринга. ьз 11.4.3. Язык рандомизирооанной машины Тьюринга Нам привычна ситуация, в которой машина Тьюринга (в частности, КА или МП- автомат) допускает некоторый язык, даже если он пуст или совпадает со всем множеством цепочек во входном алфавите. Имея дело с рандомизированными МТ, нужно быть более аккуратным с тем, что значит допускание входа такой машиной; становится возможным, что МТ вообще не допускает никакого языка.

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

Поскольку экземпляров такого содержимого бесконечно много, при вычислении этой вероятности нужно быть осторожным. Вместе с тем, в любой последовательности переходов, приводящей к допусканию, используется лишь конечная часть случайной ленты, поэтому вероятность любой случайной последовательности равна 2, если лз — число клеток случайной ленты, когда-либо просмотренных и повлиявших на переходы МТ. Следующий пример иллюстрирует вычисления в одном очень простом случае. Пример11.13.Функция переходов рандомизированной МТ М представлена на рис. 11.7. М использует только входную и случайную ленты.

Она ведет себя очень про- сто, не изменяя ни одного символа на лентах и сдвигая головки только вправо 7 Подчеркнем, что рандомизированная МТ из примера 11.12 не является распознающей. Она преобразовывает вход, и от того, что было на случайной ленте, зависит время выполнения этого преобразования, а не его результат. б02 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОВЛЕМ (направление 1!) нли оставляя на месте (Б). Хотя формально запись переходов рандомизированной МТ не была определена, содержимое таблицы на рис. 11.7 должно быть понятно. Каждая строка таблицы соответствует состоянию, а каждая колонка — паре символов ЛУ, где К вЂ” символ, обозреваемый на входной ленте, а 1' — на случайной.

Клетка г)(lеВЕ таблицы означает, что МТ переходит в состояние д, записывает У на входной ленте, К вЂ” на случайной, сдвигает головку на входной ленте в направлении Е1, а на случайной — в направлении Е. Рис. 11. 7. Функция переходов рандомизированной машины Тьюринга Опишем вкратце поведение М при входной цепочке ш, состоящей из символов О и 1. В начальном состоянии це машина М обозревает первый случайный бит и в зависимости от его значения (О или!) выполняет одну из двух проверок, связанных с зу. Если случайный бит равен О, то М проверяет, состоит ли и только из символов О или только из символов 1. В этом случае М больше не смотрит на случайные биты и оставляет вторую ленту без изменений.

Если первый бит зу равен О, то М переходит в состояние г)н В этом состоянии она движется вправо через нули, но останавливается, не допуская, если видит 1. Если в этом состоянии она достигает пробела на входной ленте, то переходит в допускающее состояние д,. Аналогично, если первый бит ш равен 1, и первый случайный бит равен О, то М переходит в состояние г);, в нем она проверяет, что все биты зу равны 1, и допускает, если это так.

Теперь рассмотрим, что делает М, если первый случайный бит равен 1. Она сравнивает зу со вторым и последующими случайными битами, допуская только тогда, когда они совпадают с первым и последующими битами и, соответственно. Таким образом, в состоянии е)е, обозревая 1 на второй ленте, М переходит в состояние ~уь Отметим, что при этом она сдвигает вправо головку на случайной ленте, оставляя на месте головку на входной. Далее в состоянии г), она проверяет совпадение содержимого двух лент, сдвигая обе головки вправо. Если в некоторой позиции она находит несовпадение, то останавливается без допускания, а если достигает пробела на входной ленте, то допускает. Вычислим вероятность допускания определенных входов. Сначала рассмотрим однородный вход, в котором встречается только один символ, например, О', где 1> 1. С вероятностью 112 первый случайный бит равен О, и если так, то дальнейшая проверка одно- 503 11.4.

КЛАССЫ ЯЗЫКОВ, ОСНОВАННЫЕ НА РАНДОМИЗАЦИИ родности будет успешной, и 0' допускается. Однако с той же вероятностью 1/2 первый бит равен 1. В этом случае 0' допускается тогда и только тогда, когда все случайные биты со второго по (и+ 1)-й равны О. Это возможно с вероятностью 2 '. Итак, общая вероятность допускания 0' равна -+ — 2'= — +2 ' 1 1, 1 2 2 2 Теперь рассмотрим вариант неоднородного входа и, содержащего как нули, так и единицы, например 00101. Этот вход не допускается, если первый случайный бит равен О. Если же первый бит равен 1, то вероятность допускания составляет 2 ', где / — длина входа.