Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 32
Текст из файла (страница 32)
Элементарные шаги машины — это считывание н запись символов, сдвиг головки на ячейку влево н вправо, а также переход управляющего устройства в следующее состояние. Детерминированность машины, т,е. последовательность ее шагов, определяется следующим образОм: для любого внутреннего состояния д~ и символа а1 однозначно заданы: а) следующее состоянием',; б) символ а', который нужно записать вместо а; в ту же ячейку (стираниесимвола будем понимать как запись пустого символа Х); в) направление сдвига головки А, обозначаемое одним из трех символов: Е (влево), Р (вправо), Е (на месте).
Это задание может описываться либо системой правил (команд), имеющих вид 156 либо таблицей, строкам которой соответствуют состояния, столбцам — входные символы, а на пересечении строки д~ и столбца а~ записана тройка символов д,'.а,' йы и, наконец, блок-схемой, которую будем называть диаграммой переходов. В этой диаграмме состояниям соответствуют вершины, а правилу вида (5.1) — ребро, ведущее из йч в д,, на котором написано аг-эа,'. Йм Условие однозначности требует, чтобы для любого 1 и любого (Фг в системе команд имелась одна команда, аналогичная (5.1), с левой частью д;а;; состояние д, в левых частях команд не встречается, На диаграмме переходов это выражается условием, что из каждой вершины, кроме дь выходят ровно гп ребер, причем на разных ребрах левые части различны; в вершине ~), нет выходящих ребер.
В дальнейшем договоримся опускать символы дг и ау, если д~=дь а;=аь Полное состояние машины Тьюринга, по которому однозначно можно определить ее дальнейшее поведение, определяется ее внутренним состоянием, состоянием ленты (т. е. словом, записанным на ленте) и положением головки на ленте. Полное состояние будем называть конфигурацией, или машинным словом, и обозначать тройкой а~д;аь где д~ — текущее внутреннее состояние, а~ — слово слева от головки, а аз — слово, образованное символом, обозреваемым головкой, и символами справа от него, причем слева от а~ и справа от аз нет непустых символов. Например, конфигурация с внутренним состоянием дь в которой на ленте записано аЬсЫе, а головка обозревает й, запишется как аЬсд4е, Стандартной начальной конфигурацией назовем конфигурацию вида д~а, т.е.
конфигурацию, содержащую начальное состояние, в которой головка обозревает крайний левый символ слова, написанного на ленте. Аналогично стандартной заключительной конфигурацией назовем конфигурацию вида д,а. Ко всякой незаключительной конфигурации К машины Т применима ровно одна команда вида (5.1), которая К переводит в конфигурацию К'. Это отношение между конфигурациями обозначим К-+.К', если т из контекста ясно, а какой машине Т идет речь, индекс Т будем опускать. Если для К, и К» существует последовательность конфигураций Кь Кз,..., К„, такая, что Кг-+ т -+Кг — э-...-эК~, обозначим это К~—- :-К, Например, если в сит т г т стеме команд машины Т имеются команды ааааа — дза4Я 157 и дза,1 нд,а„то дзаза,аз-~а~дза~аз-+д4а4азаз и, следовательно, дзаза~аг=~-д~а,азам Последовательность конфигураций Кг-~.Кз-~Кг-«...
однозначно определяется исходной конт т т фигурацией К~ и полностью описывает работу машины Т, начиная с Кь Она конечна, если в ней встретится заключительная конфигурация, и бесконечна в противном случае. Пример 5.2. а. Машина с алфавитом А (1, Х), состояниями (дь д,) и системой команд д,1- д,!Р., дЯ-~-д,1к из любой начальной конфигурации будет работать бесконечно, заполняя единицами всю ленту вправо от начальной точки. б.
Для любой машины Т, если К,=РК,=,'>Ку и К;=Кп т т последовательность К,=Кг=~-Кз=:-... является бесконечной: ее отрезок К~=~-К~ будет повторяться (зациклится). Если а~д~аз=.-Р~д«()ь то будем говорить, что машина Т т перерабатывает слово а~аз в слово ~фа, и обозначать это Т(а,а~) =раж Запись Т(а) иногда будем употреблять и в другом смысле — просто как обозначение машины Т с исходными значениями а.
Для того чтобы говорить о том, что могут делать машины Тьюринга, необходимо уточнить, как будет интерпретироваться их поведение и как будут представляться данные. Исходнымн данными машины Тьюринга будем считать записанные на ленте слова в алфавите исходных данных Аисх (Аюсх»вЂ” :А) и векторы из таких слов (словарные векторы над А„.). Это значит, что для каждой машины будут рассматриваться только те начальные конфигурации, в которых на ленте записаны словарные векторы над А„,х. Запись на ленте словарного вектора (аь..., аь) назовем правильной, если она имеет вид аАагХ...
ад ~).аь (при условии, что Хт-А„„) либо а~ «а, «... * аь — ~ ° аю где «в специальный символ-разделитель, не входящий ъ А „. Для любого вектора 1'~~«х над А«,, машина Т либо работает бесконечно, либо перерабатывает его в совокупность слов (разделенных пробелами) в алфавите, который назовем алфавитом результатов и обозначим Ар„, А„, н Ар,.
могут пересекаться и даже совпадать. В ходе работы на ленте могут появляться символы, не входящие в А„„ и Ар„и образующие промежуточный алфавит А„р (содержащий, в частности, разделитель). Таким образом, алфавит ленты А=А„„((Ар««(1А,р. В простейшем случае А«„=Ар.« и А =Аис«ОЯ. 158 Пусть 1 — функция, отображающая множество векторов над А„„в множество векторов над Ар„. Машина Т правильно вычисляет функцию ), если: 1) для любых и Яу, таких, что )( Р) = %', д|11"-~д,%", где 1'« и йУ* — правильные записи У и %" соответственно; 2) для любого Р, такого, что 1(Р) не определена, машина Т, запушенная в стандартной начальной конфигурации д, Р", работает бесконечно. Если для ) существует машина Т, которая ее правильно вычисляет, функция 1' называется правильно вычислимой по Тьюрингу.
С другой стороны, всякой правильно вычисляющей машине Тьюринга, т. е. машине, которая, начав со стандартной начальной конфигурации д|а, может остановиться только в стандартной заключительной конфигурации д,б, можно поставить в соответствие вычисляемую ей функцию. Две машины Тьюринга с одинаковым алфавитом А„» будет называть эквивалентными, если они вычисляют одну и ту же функцию.
В частности, машины из примеров 5.2 эквивалентны, так как они вычисляют одну и ту же нигде не определенную (пустую) функцию. Пример 5.3. Если машина Т содержит команды д;а « - д',а',.Е и д',а,'.— д",а,'.'г(ь, то, заменив эти две команды командой д;а~-«д,'.а, аь, получим машину Т', эквивалентную Т. Путем таких преобразований можно в машине Т убрать все команды, содержащие Е, для случая, когда д',.
— незаключительное состояние; при этом может сократиться число состояний (некоторые д,. не войдут в правые части новых команд и станут недостижимыми из д~). Если д,'.— заключительное состояние, то, введя новое заключительное состояние д +1 и заменив команду д;а,— «д',.а,'.
Е на т+1 команду д~а;- д,а,. Л, д,'а1- д + а~Я...,, д'.а„- д,+1а Е (т — число букв в А), получим машину, также эквивалентную Т. Таким образом, для любой машины Т существует эквивалентная ей машина, не содержащая н командах Е; поэтому можно рассматривать машины, головки которых на каждом шаге движутся. Определения, связанные с вычислением функций, заданных на словарных векторах, даны с явным «запасом общности» и имеют в виду переработку нечисловых объектов. В дальнейшем это понадобится; однако в ближайшее время будут рассматриваться числовые функции, точнее, функции, отображающие Л в Л~, Договоримся представлять 159 натуральные числа в единичном (унарном) коде, т.е.
для всех числовых функций Аа««=(Ц либо А«««=(1, «) и число х представляется словом 1...1=1', состоящим из х единиц. Таким образом, числовая функция )(хь...., х ) правильно вычнслима по Тьюрингу, если существует машина Т, такая, что д~! "~ " !"» « ... «!""=~у,)г, когда ((хь..., х ) =у г ь ° ° ° « и Т работает бесконечно, начиная с 4~1"~ «1"» «... «1", когда ((хь ..., х ) не определена. Начав с довольно общих определений абстрактных машин, мы затем ввели при определении вычислений на этих машинах ряд ограничений, связанных с правильной записью, правильным вычислением, представлением чисел в весьма неэкономном.единичном коде и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
