Czy są jakieś nieskończone automaty?

W teorii automatów wszyscy od samego początku czytamy automaty jako automaty skończone. Chcę wiedzieć, dlaczego automaty są skończone? Dla jasności, co to jest w skończonym automacie - alfabet, język, ciągi znaków wyrażeń regularnych, czy co? Czy istnieją (teoretycznie) jakieś nieskończone automaty?

Wszystkie modele automatów, które zwykle napotykasz, są skończone; w przeciwnym razie byłoby ich niepoliczalnie wiele, co oznacza, że ​​nie są wychwyceni przez modele Turinga. Lub, zdaniem CS, byłyby bezużyteczne¹.

„Automaty skończone” są nazywane skończonymi, ponieważ mają tylko skończony zestaw konfiguracji (na bok ciąg wejściowy). Na przykład automaty wypychające mają stos, który może mieć dowolną treść - istnieje nieskończenie wiele możliwych konfiguracji.

Uwaga: Konfiguracje urządzeń PDA są nadal skończone! W rzeczywistości każdy model obliczeniowy, który mieści się w zakresie obliczalności Turinga, musi mieć konfiguracje w pełni reprezentowalne, w przeciwnym razie TM nie byłyby w stanie ich symulować.

1. Świadomie pomijam tutaj hiper-obliczenia dla celów tego pytania.

Pełna nazwa to „skończony stan automatów”. Najważniejsze jest to, że stan automatu może być w pełni scharakteryzowany przez element pewnego skończonego zbioru stanów dyskretnych. Oznacza to, że jeśli (odpowiedni) stan automatu obejmuje zmienną o wartości rzeczywistej, istnieje nieskończona liczba stanów potencjalnych (pomijając skończoność reprezentacji zmiennoprzecinkowych), a automat nie jest skończony.

Może się to nigdy nie zdarzyć w informatyce teoretycznej, ale nie jest to zbyt egzotyczne w dziedzinie modelowania sekwencji liczb rzeczywistych. Ukrytych modeli Markowa można użyć do modelowania sekwencji liczb jako danych wyjściowych układu probabilistycznego składającego się z jednego filtra wyjściowego dla każdego stanu (dyskretnego, skończonego) modelu Markowa ze stanami nieobserwowalnymi. Filtry obliczają następne dane wyjściowe o wartości rzeczywistej z wektora poprzednich wyników (model „autoregresyjny”), ale bazowy model Markowa jest skończony, ponieważ jego prawdopodobieństwa przejścia zależą tylko od aktualnego stanu Markowa.

Jednak w tym artykule ( pełny tekst ) opracowano odmianę, w której prawdopodobieństwo przejścia zależy również od wektora liczb rzeczywistych wcześniejszych wyników. Stan tego układu jest kombinacją dyskretnego stanu Markowa i krotki liczb rzeczywistych („model Markowa stanu mieszanego”), dlatego może być w nieskończonej liczbie różnych stanów.

Krótko mówiąc, automaty nieskończone są teoretycznie dobrze zdefiniowane, a czasem nawet spotykane.

W skończonym automacie jest dość skończoność: liczba stanów, rozmiar podstawowego alfabetu i długości ciągów znaków akceptowanych przez maszynę.

Z pewnością możesz złagodzić warunek skończoności, pozwalając, powiedzmy, maszynie mieć nieskończenie wiele stanów, ale jeśli tak, to wynikowa maszyna stanie się nieciekawa, w takim sensie, że takie maszyny mogą być zaprojektowane tak, aby w ogóle akceptować dowolny język.

W rzeczywistości w teorii automatów (która bardzo odbiega od początków Kleene, Rabina i Scotta) istnieje wiele form automatów, które nie są skończone. Wynika to z kilku powodów.

Na przykład automaty wypychające to automaty o nieskończonym zestawie konfiguracji (mają one skończoną liczbę stanów, ale w rzeczywistości należy je traktować jako „automaty nieskończone”).

Podobnie istnieją inne przykłady nieskończonych automatów, dla których przestrzeń stanu jest nieskończona, ale o dużej strukturze. Na przykład rozważa się klasę automatów, które mają jako przestrzeń stanu przestrzeń wektorową (wymiar skończony), a jako funkcje przejściowe mapy liniowe (plus niektóre rzeczy początkowe i końcowe). Są one znane jako automaty ważone nad polem bazowym (Schützenberger w 61). Można je zminimalizować i przetestować pod kątem równości. Inne przykłady obejmują automaty rejestrów ( automaty te mają skończony zestaw rejestrów i działają na nieskończonym alfabecie: mogą one porównywać litery z rejestrami i przechowywać litery w rejestrach) oraz bardziej nowoczesną formę automatów nominalnych (które mają tę samą ekspresję, ale mają lepsze podstawy i właściwości). Pustka takich automatów jest rozstrzygalna.

Ale nawet w przypadku badania automatów skończonych sensowne jest mówienie o automatach nieskończonych. Rzeczywiście, rozważmy kategorię automatycznych deterministycznych automatów skończonych, które akceptują ustalony dany język L, wyposażonych w standardowe pojęcie morfizmu automatów, wtedy kategoria ta nie ma obiektu początkowego i końcowego. Jeśli jednak mieszkasz w kategorii wszystkich deterministycznych (powiedzmy policzalnych) automatów, istnieje obiekt początkowy (automat, który ma jako stany$A^*$, jako początkowy stan puste słowo, gdy czyta literę $a$ uroczyście $u$ idzie do stanu $ua$, a stan akceptuje, jeśli należy do L). Istnieje również końcowy obiekt (który ma jako stan języki!). Istnienie tych dwóch obiektów jest jednym ze sposobów wyjaśnienia na wysokim poziomie, dlaczego deterministyczne automaty można zminimalizować i są ściśle powiązane z przystawką Myhill-Nerode.

Podsumowując, istnieją automaty nieskończone, ale modele, które są najpierw badane na wykładzie, są zawsze stanami skończonymi.

Myślę, że pytanie zakłada, że ​​nie ma automatów o nieskończonym stanie, gdy są, po prostu nie warto ich wychowywać.

W teorii automatów istnieje hierarchia uprawnień różnych modeli wirtualnych. Ten, którego się nauczyłem, miał 4 (pamiętam, że minęło już trochę czasu), ten, który znalazłem na Wikipedii, ma 5. Najsłabszy w obu automatach skończonych, a najsilniejszy to maszyny Turinga. Istnieje pewna koncepcja poziomu potężniejszego niż maszyny Turinga, który nazywa się luźno hiperkomputacją. Wiele różnych opisów maszyn wirtualnych należy do jednego z tych poziomów. Maszyny Turinga są szczególnie znane z wielu modeli o tym samym poziomie mocy obliczeniowej.

Automaty nieskończonego stanu, przynajmniej jeden formalnie zdefiniowany, spadną na jeden z tych poziomów. Może być coś interesującego w pokazaniu, jak pewna rygorystyczna definicja automatów nieskończonego stanu mieści się w jednym z tych poziomów, ale poza tym nie byłaby przydatna, biorąc pod uwagę, że o wiele lepiej zbadane maszyny wirtualne reprezentują każdy poziom . Jest podobny do tego, jak mało jest zainteresowania maszyną Turinga o miliardach taśm, ponieważ nie byłaby ona mocniejsza niż pojedyncza maszyna Turinga, ale bardziej skomplikowana w obsłudze.

Jeśli zdarzyło Ci się znaleźć nieskończone automaty stanów, które nie były równoważne z istniejącym poziomem hierarchii, może to być interesujące. Ale bez tego automaty stanów nieskończonych są już przechwytywane w ramach istniejącej hierarchii, a biorąc pod uwagę dodatkowe komplikacje związane z radzeniem sobie z nieskończonością, po prostu ich unikamy w taki sam sposób, jak unikamy nadmiernie skomplikowanych modeli maszyn Turinga.

(Naiwna) nieskończona wersja deterministycznej maszyny skończonej jest zbyt potężna . Taka rzecz mogłaby w ogóle „zapamiętać” dowolny język, więc nie można się wiele z tego nauczyć.

Na przykład nad binarnym alfabetem rozważ automat w postaci pełnego drzewa binarnego o nieskończonej wysokości. Każdy możliwy ciąg znaków, który można traktować jako dane wejściowe, odpowiada jednoznacznie węzłowi drzewa, dzięki czemu można zbudować decydujący dla dowolnego języka, po prostu tworząc odpowiednie węzły akceptujące stany.