XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 91
Текст из файла (страница 91)
Тем самым будет прочитано второе слагаемое до ближайшего пробела, затем применением команд (8)-(10) будут стерты лишние „палочки", машина вернется к маркеру начала ленты и остановится в заключительной конфигурации. Если же второе слагаемое равно 0 (есть однобуквенное слово 0), то после выполнения команды (5) применяется команда (14), и затем посредством применения команд (15) и (16) машина сотрет две „палочки" и перейдет в заключительную конфигурацию. Запишем тогда последовательность конфигураций для прибавления нуля к произвольному числу: (Чв, ЛвОЦ...
~10) 3- (Чо*,ОЦ... ~10) ~- ~(Чв,вО,Ц"! 10) ~'(ав,+ОЦ" !,(О) ~ ~(д„оц...ц,о) ~-(д„оц...ц!,п) ~ ~-(~„+ОЦ...Ц,~П) ~-(~„+ОЦ...~,)пп) 1- 1- (дв) +Оц... > ! ппп) $-' (дв) * ОЦ... ~) 3- 1- (дв, Л,*ц... ~) 1- (в, Л,*ц... /). Разумеется, предложеннвя машина Тьюринга для сложения двух натуральных чисел не обязана быть единственной, но это и не требуется по определению вычислимости — достаточно, чтобы нашлась хотя бы одна машина, вычисляющая данную функцию. Д.7.4.
Машилъг 7ьюрилга 575 Итак, используя понятие машины Тьюринга, можно дать строгое определение функции как проиедуры (правила, алгоритма) вычисления значения функции по известным значениям ее аргументов. Тем самым понятие машины Тьюринга есть одно иэ возможных математически точных определений алгоритма. До построения какого-либо математического определения алгоритма мы имеем дело с интуитивным представлением об алгоритме. Это интуитивное понятие, не являющееся математически строгим (подобно тому как в рамках „наивной" теории множеств не является таковым понятие множества), может быть охарактеризовано следующими признаками: 1) признак детерминированности алеоритма — алгоритм есть пошагово реализуемая процедура, на каждом шаге которой однозначно определено ее продолжение (другими словами, алгоритм не допускает произвола в выборе очередного шага — в определении алгоритма через машину Тьюринга этот принцип реализуется через понятие детерминированной машины Тьюринга); 2) признак результативности алеоритма — процесс работы алгоритма с исходными данными должен завершаться через определенное конечное число шагов; 3) признак массовости алгоритвма — алгоритм должен быть применим к определенному достаточно широкому множеству входных данных.
Наряду с машиной Тьюринга известны и другие уточнения понятия,,алгоритм" (нормальные алгорифмы Маркова, рекурсивные функции, канонические системы Поста и т.п.). Оказывается, что все эти понятия в определенном смысле эквивалентны. Кроме того, в теории алгоритмов, которая занимается проблемами построения разных уточнений понятия алгоритма и вычислимости, а также сравнением между собой разных уточнений, основной гипотезой является гипотеза о том, что всякая функция, вычислимал в интуитивном смысле слова,т.е. такая, что существует алгоритм (в интуитивном смысле слова) 576 7.
КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ вычисления значений функции по известным значениям аргументов, будет вычислима и в соответствии с каким-либо точным определением вычислимости, например будет вычислима по Тьюрингу. Применительно к машинам Тьюринга зта гипотеза носит название тезиса 2'ьюринеа: любая вычислимая (в интуитивном смысле) словарная функция вычислима по Тьюрингу. В пользу тезиса Тьюринга говорит то, что до сих пор не удалось придумать вычислимую функцию, которую нельзя было бы „запрограммировать" в виде машины Тьюринга, а также то, что все известные до сих пор альтернативные уточнения понятия алгоритма можно (хотя и не так просто) свести к понятию машины Тьюринга.
Чтобы закончить обсуждение машин Тьюринга в контексте теории формальных языков, нам необходимо ввести еще два важнейших понятия — перечислимости и разрешимости. Условимся в дальнейшем машину Тьюринга со входным алфавитом У называть машиной Тьюринеа в алфавите У, а машину Тьюринга, входной алфавит которой содержит злфа; вит 1' и символы, не принадлежащие У, — машиной Тьюринеа над алфавитом 17. Договоримся также „кодировать" натуральные числа словами в алфавите Ж = (О, Ц, дав множеству М натуральных чисел следующее определение по индукции: 1) слово О есть натуральное число; 2) если известно, что слово н в алфавите Ф есть натуральное число, то слово н~ есть натуральное число; 3) никаких других натуральных чисел, кроме определенных в пп.
1 и 2, не существует. На множестве определенных таким образом натуральных чисел (как слов) естественно вводится отношение порядка: по определению, н < т, если н есть префикс т. Легко определить и обычные арифметические операции, „запрограммировав" их машинами Тьюринга (пример операции сложения разобран вьппе). д.Т.4. Машвям Тыорявга 577 Определение 7.18.
Непустое множество слов Ь в алфавите 1~ называется перечислимым (по Тьюрппгу), если существует машина Тьюринга Т над алфавитом У 010, Ц, такая, что для всякого п Е г!!Т(и) и для всякого х Е Ь имеет место х = Т(и) для некоторого и Е М. Таким образом, перечислимость языка Ь означает суще. ствование алгоритма („ запрограммированного" как машина Тьюринга), по любому натуральному числу п вычисляющего элемент Ь и такого, что любой элемент Ь может быть вычислен по некоторому натуральному числу.
Такой алгоритм есть алгоритмический („ конструктивный" ) аналог теоретико-множественного понятия нумеровав как сюрьеюиивкого ошображенил множества натуральных чисел на некоторое множество. Замечание 7.14. Пустое множество слов считается перечислимым по соглашению. Определение 7.19. Множество слов Ь в алфавите У называют разрешимым (по Уьюрппгу), если существует такая машина Тьюринга Т над алфавитом У, что для всякого х Е У' имеет место !Т(х) и Т(х) = Л, если х е Ь, и Т(х) ~ Л, если х !с Ь. Другими словами, разрешимость языка Ь означает существование вычислимого предиката, определенного на множестве слов в алфавите У и принимающего значение 1, если элемент принадлежит Ь, и значение О в противном случае. Без доказательства сформулируем следующую теорему.
Теорема 7.14. 1. Существует неперечислимый язык в некотором алфавите У. 2. Существует перечислимый, но неразрешимый язык (в некотором алфавите У). 3. Язык Ь С У' перечислим тогда и только тогда, когда он является областью применимости некоторой машины Тьюринга над алфавитом У. 4. Язык Ь С Ъ'" перечислим тогда и только тогда, когда он порождается некоторой грамматикой типа О.
578 Ч. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ 5. Язык Ь С У* разрешим тогда и только тогда, когда он порождается некоторой КЗ-грамматикой. ф Из теоремы 7.14 следует, что всякое разрешимое множество перечислимо, но обратное неверно. В силу утверждений 3 и 4 теоремы 7.14 машины Тьюринга можно рассматривать как „распознающие автоматы" для языков типа О: для каждого такого языка существует машина Тьюринга, применимая к словам данного языка, и только к ним. Заметим при этом, что язык типа О может оказаться и неразрешимым: для него может не существовать алгоритма, распознающего принадлежность ему любого наперед заданного слова.
Это значит, что для грамматик типа О проблема принадлежности в общем случае не является разрешимой. Эта проблема, однако, как следует из утверждения 5 теоремы 7.14, разрешима для любого языка, порождаемого КЗ-грамматикой (см. 7.2), в частности для любого КС-языка. Утверждение 1 теоремы 7.14 означает, что существуют языки, которые не могут принципиально быть порождены какой- либо грамматикой.
Примером такого языка может служить множество так называемых конструктивных действительных чисел'. Пример перечислимого, но неразрешимого языка может быть построен следующим образом. Пусть У вЂ” алфавит, а р — конечное бинарное отношение на множестве У+ непустых слов в алфавите У. Определим язык Ьр в алфавите У 01*, 1), где символы * и 1 не принадлежат У: ор 1з1 (91*Я2 (92* ° ° *ЖвЬа: и ~1 1, х1х2...Яе = У1У2 ° ° ° 11 и (% = ~~ пЦ(Я',Уе) Е Р1 ° Доказывается, что язык Ьр в общем случае неразрешим, т.е. не существует алгоритма, который для любого наперед заданного отношения р (при Я ) 2) распознавал бы слова языка Ьр. "См.: К1рекер Б.А. 579 Вопросы язадачя Проблема распознавания слов языка Ьр известна в теории алгоритмов под названием проблемы соотпеетстпеиб Постно (над алфавитом т').
Неразрешимость проблемы соответствий в общем случае не исключает того, что для каких-то конкретных алфавитов и конечных бинарных отношений на множестве непустых слов эту проблему можно решить. Например, пусть т'" = (а, Ь), а р = ((аЬа, аЬ), (Ь, аЬ)'1. Нетрудно показать, что в данном слУчае Ье — — ((аЬа1аЬ*61аЬ)": т» > Ц. Вопросы и задачи 7.1. Доказать, что следующая грамматика, заданная систе. мой правил вывода, порождает любую цепочку вида а", и > 1: Т.2.
Доказать, что следующая грамматика, заданная системой правил вывода, порождает любое слово в алфавите (а,61 вида тяте: 7.3. Доказать, что любая праволинейная грамматика может быть задана эквивалентной регулярной грамматикой. Т.4. Постройте КЗ-грамматику, порождающую язык: а) Ьт = (апЬтеа" 6™: тп, и > Ц; б) Ьэ = (а"Ь"а": т» > Ц. пе Я-» аСА, А -+ оэЕА ~ Р, ЕР-» РР, ЕР -+ РазЕ, Я -» С.Р, С-» аСА~ЬСВ~Л, Р-»Л, АР -+ аР, ВР -+ ЬР. Еа -+ аЕ, Са-+аС, СР -+ Са, СР-+ Л. Аа ~ аА, АЬ-+ ЬА, Ва-+аВ, ВЬ-+ ЬВ, 580 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЭЫКИ 7.5. Какой язык порождает грамматика Я -+ аБВа ~ аба, аВ -+ Ва, ЬВ -+ ЬЬ? 7.6. Построить леволинейную грамматику для языка идентификаторов, которые должны содержать от одного до шести символов и начинаться с одной из букв 1, ~, Й, 1, та, и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
