Języki, automaty i obliczenia/Wykład 14: Języki maszyn Turinga i typu (0). Rozstrzygalność

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Języki maszyn Turinga i rodzina

Powstaje naturalne pytanie o związki pomiędzy klasą języków rozpoznawanych przez maszyny Turinga a klasami zadanymi poprzez gramatyki. Odpowiemy na to pytanie w tej części wykładu.

Twierdzenie 1.1

Każdy język akceptowany przez maszynę Turinga jest typu (0).

Dowód

Niech będzie językiem akceptowanym przez maszynę Turinga , o której założymy, że , jeśli para należy do dziedziny funkcji przejść maszyny Turinga. Założenie to nie ogranicza ogólności rozważań. Wyróżnimy pewien podzbiór zbioru stanów , którego elementy, jak wskazuje oznaczenie, skojarzone są ze stanami końcowymi. Do zbioru należy każdy stan , dla którego istnieje ciąg stanów dla taki, że dla oraz , gdzie . Zauważmy, iż wraz ze stanem do zbioru należą wszystkie elementy ciągu .

Określamy teraz gramatykę . Zbiór symboli nieterminalnych zawiera wyłącznie następujące symbole:

  1. dla każdego stanu i symbole
  2. dla każdej litery symbole i
  3. wszystkie elementy zbioru
  4. symbole nie należące do

Zbiór praw składa się z praw wymienionych poniżej:

  1. , , jeśli dla pewnego , ,
  2. , dla każdego ,
  3. , , , , jeśli i ,
  4. , , , , jeśli i ,
  5. , , , , jeśli ,
  6. , , jeśli istnieją dla , takie że , dla oraz ,
  7. , , jeśli istnieją dla takie, że , dla oraz ,
  8. dla wszystkich ,
  9. , , jeśli (porównaj założenie na początku dowodu),
  10. , jeśli .

Określona powyżej gramatyka jest gramatyką typu (0). Rozważmy teraz dowolne słowo , dla którego istnieje wyprowadzenie w gramatyce ze stanu początkowego przy użyciu praw 1-7. Słowo zawiera dokładnie jeden z następujących symboli lub . Pierwsza litera słowa oznaczona jest markerem z lewej strony, a ostatnia litera słowa oznaczona jest markerem ze strony prawej. Ponadto żadna z liter występujących pomiędzy pierwszą a ostatnią nie jest oznaczona markerem . Z każdym takim słowem kojarzymy konfigurację poprzez zastąpienie symbolu przez oraz przez dopisanie symbolu po lewej lub prawej stronie znaczonej przez ten marker litery, zgodnie z jego występowaniem. Jeśli np. , to skojarzona konfiguracja jest postaci . Zauważmy, że jeśli słowa i są w powyższej formie, to fakt, iż , jest równoważny stwierdzeniu, że z konfiguracji skojarzonej ze słowem maszyna Turinga może przejść (bezpośrednie następstwo) do konfiguracji skojarzonej ze słowem . Każdy krok obliczenia realizowanego przez ma swój odpowiednik - krok w wyprowadzeniu w gramatyce . Z tym, że wobec praw 6 i 7 sekwencja obliczeń

jest traktowana jako jeden krok w obliczeniu prowadzonym przez maszynę Turinga. Analogicznie traktujemy sekwencję z markerem występującym po lewej stronie. Ze stanu początkowego gramatyki można wyprowadzić wszystkie słowa , dla których konfiguracja jest równa , dla pewnego oraz maszyna Turinga realizuje obliczenie:

Wynika to z praw 1 i 2 skonstruowanej gramatyki . Z kolei prawa typu 9 służą do zastąpienia symboli nieterminalnych typu przez litery terminalne, a prawa typu 8 eliminują symbole nieterminalne typu . A zatem dla niepustego słowa spełniona jest równoważność

gdzie oraz . Prawo 10. zapewnia, że powyższa równoważność prawdziwa jest także dla słowa pustego . A to kończy dowód tego twierdzenia.

End of proof.gif

Język nazywamy rekurencyjnie przeliczalnym, jeśli istnieje efektywny algorytm wyliczający wyłącznie słowa z . Przez efektywny algorytm rozumiemy skończony zbiór instrukcji, który w jednoznaczny sposób opisuje działanie tego algorytmu. Klasę języków rekurencyjnie przeliczalnych oznaczamy symbolem .

Zauważmy, że każda gramatyka typu (0) jest algorytmem wyliczającym wyłącznie słowa z . Dla każdej liczby naturalnej można bowiem rozważyć skończony zbiór wyprowadzeń w , rozpoczynających się od symbolu początkowego i o długości równej . Z tego zbioru można z kolei wybrać wyłącznie te wyprowadzenia, które kończą się słowem nad alfabetem terminalnym gramatyki i tylko te słowa dodawać do listy składającej się na język . Są to, jak łatwo zauważyć, wszystkie słowa języka i nic ponadto. A zatem

Twierdzenie 1.2

Każdy język typu (0) jest językiem rekurencyjnie przeliczalnym, czyli .

Język nazywamy rekurencyjnym, jeśli istnieje efektywny algorytm rozstrzygający dla każdego słowa jego przynależność do języka . Klasę języków rekurencyjnych oznaczamy symbolem .

Klasa języków kontekstowych zawiera się istotnie w klasie języków rekurencyjnych, o czym przekonuje poniższe twierdzenie.

Twierdzenie 1.3

Każdy język kontekstowy jest językiem rekurencyjnym, czyli

Dowód

Niech będzie dowolnym językiem kontekstowym. Istnieje więc gramatyka kontekstowa taka, że . Bezpośrednio z definicji gramatyki kontekstowej wynika, iż słowo puste wtedy i tylko wtedy, gdy . Załóżmy teraz, że dane jest słowo , o którym mamy zadecydować, czy należy do języka . W tym celu rozważmy wszystkie ciągi słów

o tej własności, że są parami różne, dla , oraz . Ilość takich ciągów jest skończona i słowo wtedy i tylko wtedy, gdy wśród powyższych ciągów znajdziemy choć jeden taki, że tworzy wyprowadzenie w gramatyce . Czyli

Ponieważ ilość ciągów podlegających rozważaniom jest skończona oraz ponieważ stwierdzenie, czy pomiędzy dowolnymi słowami zachodzi relacja , sprowadza się do przeszukania skończonego zbioru praw , efektywnie rozstrzygniemy, czy należy do języka , czy też nie.

End of proof.gif

Uzyskane dotąd rezultaty możemy podsumować następująco:

W określeniu języka rekurencyjnie przeliczalnego oraz języka rekurencyjnego wystąpiło pojęcie efektywnego algorytmu, efektywnej procedury. Pojęcie to, intuicyjnie dość jasne, nie zostało precyzyjnie określone. Co za tym idzie, dla matematycznie poprawnych definicji języka rekurencyjnie przeliczalnego i języka rekurencyjnego należałoby sformalizować pojęcie algorytmu. W dotychczasowych rozważaniach intuicja efektywnej procedury była o tyle wystarczająca, że naszym celem było wskazanie istnienia takiej procedury. W sytuacji, gdyby naszym celem było wykazanie, że taka procedura nie istnieje, formalizacja tego pojęcia byłaby wręcz konieczna. We wszystkich takich przypadkach powszechnie przyjmuje się, że maszyna Turinga jest właśnie taką formalizacją. Na zdefiniowaną w poprzednim wykładzie maszynę Turinga można spojrzeć jako na algorytm, efektywną procedurę dającą odpowiedź pozytywną lub negatywną w zależności od akceptacji lub nieakceptowania słowa wejściowego. Proces obliczenia prowadzony przez maszynę Turinga zgadza się z intuicyjnym rozumieniem algorytmu. O tym, że każda efektywna procedura jest reprezentowana przez pewną maszynę Turinga, mówi, powszechnie przyjęta jako prawdziwa, teza Churcha.

Teza Churcha

Każda efektywna procedura (algorytm) da się opisać przez maszynę Turinga.

Konsekwencją przyjęcia tezy Churcha jest inkluzja . Biorąc pod uwagę udowodnione powyżej twierdzenia, mamy:

co ostatecznie prowadzi do równości .

Rodziny i - zamkniętość na działania

Dla kompletności tej części wykładu przedstawimy własności zamkniętości rodziny języków kontekstowych i języków typu (0) ze względu na najczęściej używane operacje. W niektórych przypadkach dowody dotyczące obu klas są takie same. W dowodach posłużymy się specjalną postacią gramatyk, a mianowicie taką, w której symbole terminalne występują tylko po prawej stronie. Prawdziwe bowiem jest twierdzenie

Twierdzenie 2.1

Dla każdej gramatyki istnieje równoważna gramatyka tego samego typu taka, że każda produkcja, w której występuje symbol terminalny , jest postaci .

Elementarny dowód tej własności pozostawiamy jako zadanie domowe.

Twierdzenie 2.2

Rodziny i są zamknięte ze względu na:

  1. sumę mnogościową,
  2. iloczyn mnogościowy,
  3. katenację,
  4. iterację ,
  5. odbicie zwierciadlane.

Dowód

1. Niech dla będą gramatykami typu (odpowiednio typu ) takimi, że . I niech . Określamy gramatykę typu (typu ) generującą język .

Jeśli , to przyjmujemy:

Zauważmy, że wówczas w żadnej z gramatyk nie ma prawa wymazującego. Jeśli natomiast , to konstruujemy gramatykę dla języków i , jak powyżej, a następnie dodajemy nowy symbol początkowy i prawa .

2. Przecięcie udowodnimy tylko dla języków typu . Dowód dla języków kontekstowych został przeprowadzony wcześniej.

Niech dla będą gramatykami typu takimi, że . Niech . Określamy gramatykę typu generującą język , przyjmując:

gdzie: , a do zbioru należą prawa:
(1)
(2) dla
(3) dla
(4) dla
(5)
Przy pomocy prawa (1) i wszystkich praw ze zbioru można wygenerować zbiór słów:

Z dowolnego słowa należącego do tego zbioru, korzystając z praw (2)-(4), można wyprowadzić słowo wtedy i tylko wtedy, gdy . Korzystając z prawa (5), dostajemy słowo . A więc .

3. Niech dla będą tak jak poprzednio gramatykami typu ( ) takimi, że oraz spełniającymi warunki powyższego twierdzenia. Niech . Określamy gramatykę odpowiednio typu ( ) generującą język .

Jeśli , to przyjmujemy:

Jeśli , to oznaczamy . Wówczas:

Wykorzystując poprzednią konstrukcję i zamkniętość ze względu na sumę w każdym z tych przypadków, otrzymujemy gramatykę generującą katenację języków i .

4. Niech będzie gramatyką typu (typu ) taką, że symbole terminalne nie występują po lewej stronie żadnej produkcji z . Załóżmy też, że . Gramatyka

gdzie

generuje język . Jeśli , to usuwamy prawo wymazujące i dla języka konstruujemy gramatykę . Z faktu, że , wynika, że również .

5. Jeśli jest gramatyką typu (typu ) taką, że , to gramatyka , gdzie generuje język .

End of proof.gif

Zauważmy na koniec, że rodzina nie jest zamknięta ze względu na uzupełnienie. Stwierdzenie to wynika z przyjęcia jako obowiązujacej tezy Churcha, która w tym wypadku implikuje równość rodziny języków i rodziny języków rekurencyjnie przeliczalnych oraz z faktu, iż istnieje język rekurencyjnie przeliczalny, którego uzupełnienie nie jest rekurencyjnie przeliczalne. Ten ostatni fakt podajemy bez dowodu. Dodajmy, że własność zamkniętości ze względu na uzupełnienie dla rodziny przez długi czas pozostawała problemem otwartym. Dopiero w roku 1987 udowodniono, iż własność ta jest spełniona dla języków kontekstowych. Podsumowanie własności zamkniętości ze względu na działania dla różnych klas języków hierarchii Chomsky'ego zawarte jest w poniższej tabeli:

          3       2       1       0   
          T       T       T       T   
          T       T       T       T   
          T       T       T       T   
          T       N       T       N   
          T       N       T       T   

Na koniec podamy twierdzenie o wzajemnych relacjach pomiędzy rodzinami języków z hierarchii Chomsky'ego. Dowód tego twierdzenia wynika w części z definicji typów gramatyk wprowadzonych na wykładzie 2, a w części z udowodnionych własności poszczególnych rodzin języków z hierarchii Chomsky'ego (zakładając obowiązywanie tezy Churcha).

Twierdzenie 2.3

Rodziny języków hierarchii Chomsky'ego spełniają następujące relacje:

Problemy rozstrzygalne

W poprzednim wykładzie uzasadniliśmy, że dla każdej deterministycznej maszyny Turinga jesteśmy w stanie wskazać taką, która akceptuje dany język i jednocześnie zatrzymuje się tylko na słowach akceptowanych. Wymagało to przejścia przez maszynę niedeterministyczną, a następnie jej symulację na maszynie deterministycznej. Z tego powodu ograniczamy się w dalszej części wykładu tylko do tego typu maszyn Turinga (akceptacja=stop). Jak to uzasadniono wcześniej, przy założeniu tezy Churcha, maszyna Turinga może być rozpatrywana jako matematycznie ścisła definicja algorytmu.

Pojęcie rozstrzygalnego problemu zostało wprowadzone wcześniej, na innym wykładzie, i jest ono znane. Przypomnijmy więc tylko, że rozstrzygalność, czy też nierozstrzygalność, odnosi się do pewnej klasy, którą tworzą określone przypadki ustalonego problemu. Jeśli istnieje algorytm, który rozwiązuje taki problem dla wszystkich przypadków w tej klasy, to mówimy, że problem jest rozstrzygalny (w tej klasie). Zatem taki algorytm jest uniwersalnym sposobem rozwiązywania problemu dla wszystkich danych wejściowych określających poszczególne przypadki w tej klasie. Jak łatwo zauważyć dla ustalenia rozstrzygalności problemu wystarczy się opierać na intuicyjnym pojęciu algorytmu. Są jednak takie problemy, dla których nie istnieje, w rozważanej klasie przypadków, uniwersalny sposób ich rozwiazywania. Takie problemy nazywamy nierozstrzygalnymi w danej klasie. Aby wykazać nierozstrzygalność jakiegoś problemu, nieodzownym jest sformalizowanie pojęcia algorytmu. Standardowo taką formalizacją jest, o czym wspomniano już wcześniej, maszyna Turinga.

Zwróćmy uwagę, że maszyna Turinga akceptuje języki, gdy tymczasem przyzwyczajeni jesteśmy, że algorytmy (programy) rozwiązują pewne, niekiedy bardzo skomplikowane, problemy (określone przy pomocy list, kolejek, grafów itp.). Zwracamy zatem uwagę na fakt, że w przypadku maszyny Turinga musimy wykonać wstępne umowne kodowanie naszego problemu. W tym przypadku rozważany język określa te spośród "sensownych" kodowań, które stanowią rozwiązanie postawionego problemu. Z drugiej strony maszyna, akceptując słowo , może informować nas o tym, że wynikiem obliczeń numerycznych na danych zakodowanych w rzeczywiście jest liczba zakodowana w itp.

Dla ilustracji powyższych dywagacji rozważmy problem skończoności w klasie jezyków regularnych. Problem ten jest rozstrzygalny, bo w oparciu o lemat o pompowaniu można skonstruować algorytm, który dla dowolnego języka regularnego rozstrzygnie, czyli odpowie twierdząco lub przecząco na pytanie o jego skończoność. W tym przypadku można np. przyjąć, że jako słowo wejściowe podajemy zakodowany opis gramatyki generującej język.

Nierozstrzygalność algorytmiczna problemu w ustalonej klasie nie oznacza, podkreślmy, niemożliwości rozwiązania konkretnego zadania z tej klasy. Nierostrzygalność oznacza niemożliwość rozwiązania za pomocą tego samego algorytmu, tej samej metody, wszystkich przypadków tego problemu należących do danej klasy.

W zamieszczonej poniżej tabeli przedstawiamy najczęściej rozważane pod kątem rozstrzygalności problemy z dziedziny języków formalnych w ramach hierarchii Chomsky'ego. Litera R oznacza rozstrzygalność problemu, N nierostrzygalność, a znak - pojawiający się przy problemie jednoznaczności oznacza, że problemu tego nie formułuje się dla gramatyk kontekstowych i typu (0):

własność (3) (2) (1) (0)
należenie R R R N
inkluzja R N N N
równoważność R N N N
pustość R R N N
nieskończoność R R N N
jednoznaczność gramatyki R N - -

Najczęściej używaną metodą dowodzenia nierozstrzygalności problemu jest redukcja tego problemu do innego, powiedzmy , dla którego nierozstrzygalność została ustalona wcześniej. Redukcja taka prowadzi do sformułowania implikacji:

jeśli byłby rozstrzygalny, to i byłby rozstrzygalny.

A ponieważ to ostatnie (następnik implikacji) nie jest prawdą, więc problem nie jest rozstrzygalny.

Należy w tym miejscu podkreślić fakt, że dowody nierozstrzygalności problemów uniwersalnych (takich jak problem Posta rozważany dalej) wiążą się z konstrukcją odpowiednich maszyn Turinga, kodowaniem problemu, a następnie dowodem uzasadniającym, że problem jest rzeczywiście nierozstrzygalny. Tematyka ta wykracza poza ramy wykładu. Z tego też powodu ograniczymy się tutaj do zaprezentowania jednego ze znanych problemów nierozstrzygalnych bez dowodu nierozstrzygalności.

Najczęściej występującym w literaturze problemem nierozstrzygalnym jest, bez wątpienia, problem Posta przedstawiony poniżej.

 

Problem Posta

Dla dowolnego alfabetu , o co najmniej dwóch elementach ( ), załóżmy, iż dana jest, tak zwana, lista słów, a dokładniej: par słów gdzie , . Mówimy, że taka lista ma własność Posta (problem Posta ma rozwiązanie), jeśli istnieje ciąg indeksów taki, że

Jest to w ogólnym przypadku problem nierozstrzygalny.

Problem ten można sformułować równoważnie następująco. Niech będzie alfabetem interpretowanym jako zbiór indeksów, a dowolnym alfabetem. Niech będą dowolnymi homomorfizmami. Problem Posta, inaczej sformułowany, polega na odpowiedzi na pytanie, czy istnieje słowo takie, że .

Dwa kolejne przykłady ilustrują technikę redukcji pewnych problemów do problemu Posta. W efekcie uzyskujemy nierozstrzygalność w sposób opisany powyżej.

Twierdzenie 3.1

W klasie gramatyk bezkontekstowych problem niejednoznaczności jest nierozstrzygalny.

Dowód

Udowodnimy, że problem jest nierozstrzygalny dla gramatyk bezkontekstowych generujących języki nad alfabetem dwuelementowym . Oznaczmy i określmy homomorfizm , przyjmując oraz . Niech będzie ciągiem dowolnie wybranych i ustalonych słów. Dla dowolnej liczby naturalnej niech . Określony poniżej język

jest językiem bezkontekstowym, jako generowany przez gramatykę , dla której

oraz .

Niech teraz i oznaczają ciągi dowolnie wybranych i ustalonych słów i . Tworzą one listę słów . Zatem zasadne jest postawienie pytania, czy lista ta ma własność Posta. Niech oraz będą gramatykami bezkontekstowymi określonymi tak jak powyżej. Gramatyka , gdzie jest bezkontekstowa. Gramatyka ta jest niejednoznaczna wtedy i tylko wtedy, gdy . Ten ostatni warunek równoważny jest istnieniu liczb takich, że , czyli własności Posta listy .Ostatecznie więc rozstrzygalność problemu niejednoznaczności w klasie gramatyk bezkontekstowych prowadziłaby do rozstrzygalności własności Posta.

End of proof.gif

Dla drugiego przykładu przyjmijmy jako alfabety oraz określmy język

Ustalmy listę Posta nad alfabetem , gdzie . Wprowadzamy teraz języki nad alfabetem , przyjmując:

oraz definiujemy język

Określone powyżej języki nad alfabetem mają własności konieczne do zastosowania lematu, który przytoczymy bez dowodu.

Lemat 3.1

Języki są bezkontekstowe.

Dla języków i uzasadnienie ich bezkontekstowości jest proste poprzez konstrukcję odpowiednich gramatyk. Aby uzyskać bezkontekstowość ich uzupełnień, należy podzielić rozważane języki na rozłączne podzbiory i konstruować gramatyki bezkontekstowe dla tych wyróżnionych podzbiorów, a w końcu wykorzystać fakt, że suma języków bezkontekstowych jest językiem bezkontekstowym.

Zauważmy teraz, że istnienie rozwiązania problemu Posta nad alfabetem jest równoważne temu, że .

Jeśli bowiem , gdzie , to oczywiście . Jeśli ciąg jest rozwiązaniem problemu Posta, to też. Zatem jeśli , to język jest nieskończony.

Wobec nierozstrzygalności problemu Posta wnioskujemy, że nierozstrzygalny jest problem pustości i problem nieskończoności przecięcia w klasie języków bezkontekstowych.