Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 26

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 101 >> Следующая


Пусть имеется другой алфавит S3 = {Ьи ..., Ьп}, находящийся с первым во взаимно однозначном соответствии: йі Ьіш Гл. IV. Алгоритмы. Машины Тьюринга

75

Задача машины T состоит в транскрибировании любого данного 91-слова с помощью алфавита S3, причем транскрибированное слово должно быть записано на другом участке ленты, а исходное сохранено.

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

I. Для всякого і:

I. 1. <7о ai tn q{.

Находясь в начальном состоянии qo и прочитав аг- — самую правую букву исходного слова, машина пишет вместо ?j маркер т и запоминает Oi посредством перехода в состояние qt.

1.2. qi т П qt.

Находясь в состоянии qi (т. е. помня о символе ?j) и видя маркер in, T перемещает ленту вправо, оставаясь в состоянии qi.

1.3. qt # at q\.

Находясь в состоянии qi и видя пустую ячейку, машина T записывает в нее а, и переходит в состояние q\: «прочитанный перед этим символ ui скопирован».

1.4. q\ т JI q\.

Видя маркер после копирования а{ (не обязательно сразу), машина сдвигает ленту влево.

II. Для всякой пары (/,/):

II. 1. q{ at JI qt.

И. 2. q\ uj JI qj.

II. 3. q\ Ь, Л q\.

Скопировав ui и находясь в состоянии qj, машина вне зависимости от обозреваемой буквы передвигает ленту влево; при этом она остается в состоянии qj.

п. 4. g}*btr.

Дойдя до пустой ячейки, T транскрибирует а<, вписывая Ь{ в пустую ячейку, после чего переходит в состояние г — «состояние возврата».

III. Для всякого j:

III. 1. г bj П г.

III. 2. г а, П г. 76

Часть /. Предварительные сведения из логики и алгебры

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

III.3. г m # г.

T продолжает сдвигать ленту вправо до тех пор, пока не наткнется на маркер, оставленный ею там, откуда она «отправилась» искать свободные места для копирования и транскрибирования щ. Тогда она стирает маркер, оставаясь в состоянии г.

III. 4. г # Л q0.

Видя пустой символ, которым она только что заменила маркер, машина сдвигает ленту влево (так что теперь она будет обозревать очередной символ исходного слова) и возвращается в начальное состояние <7о.

Когда T закончит транскрибирование, она окажется в состоянии <7о, но сможет прочесть только какую-либо из букв bj. Поскольку ситуации (<7о, bj) не соответствует ни одна команда, машина остановится.

В этот момент на ленте будут записаны оба слова (исходное її-слово и его 33-транскрипция), разделенные пустой ячейкой.

§ 4.3. «ЧИСЛЕННЫЕ» МАШИНЫ ТЬЮРИНГА

Описанные в п. 4.2.2 машины Тьюринга позволяют реализовать алгоритмы самого общего характера. В частности, два предшествующих примера относились к «нечисленным» алгоритмам. Однако, по правде говоря, на уровне машин Тьюринга между «численным» и «нечисленным» нет существенного различия1). Когда речь идет просто о манипуляциях с символами, мы вольны давать этим символам любую интерпретацию — и числовую, и нечисловую. Если мы хотим проводить вычисления, т. е. работать с числами, то их можно изображать многими разными способами.

Для работы с целыми неотрицательными числами мы будем пользоваться абстрактным двубуквенным алфавитом її = (S0, Si}: So соответствует пустому символу, обозначаемому В\ Si соответствует палочке, обозначаемой |.

Всякое целое неотрицательное число га изображается последовательностью из га + 1 палочек. Это соглашение позволяет отличать число «нуль», изображаемое палочкой, от пустого символа,

') Для реальных вычислительных машин это различие, напротив, весьма важно (с практической точки зрения). Пригодность машины для той или иной области приложений зависит от набора «встроенных» операций: машины для количественных расчетов нуждаются в разнообразных арифметических операциях, машины для логической обработки информации — в булевых операциях, операциях типа подстановки и т. д. Гл. IV. Алгоритмы. Машины Тьюринга

77

играющего роль разделителя. Мы будем обозначать подобное изображение числа п через п; например:

0= I, T = II.....4 = 11111-

Конечная последовательность пи п2.....tih будет изображаться

следующим образом:

HiBn2B ... Bhk.

Пусть имеется выражение М, иначе говоря, цепочка в алфавите {В, |; <7ь <72, •••, <7«; п, Л]. Будем обозначать через (M) число палочек, которое она содержит.

4.3.1. Понятие вычислимой функции

Пусть Z —машина Тьюринга с состояниями <7i, q2, ... . Каждой n-ке (т\, ..., mn) неотрицательных целых чисел мы поставим в соответствие конфигурацию

O1 = qimiBm2B ... Btftn.

Если для машины Z существует вычисление, начинающееся конфигурацией осі и доходящее до заключительной конфигурации аР:

O1 ->¦ а2 -*¦ ... -> ар,

то число (ар) есть функция от Z и начальной n-ки; мы будем писать

(Op) = ^K, .... «„).

Если же вычисления, начинающегося с осі, не существует, т. е. не существует целого числа р, такого, что конфигурация аР является заключительной, то функция xP^ не определена для рассматриваемой п-ш.
Предыдущая << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed