Czy istnieje niezdecydowany skończony język skończonych słów?

10

Czy istnieje potrzeba, aby $L\subseteq \Sigma^*$ była nieskończona, aby była nierozstrzygalna?

Chodzi mi o to, że jeśli wybierzemy język $L'$ jako ograniczoną skończoną wersję $L\subseteq \Sigma^*$ , to znaczy $|L'|\leq N$ ( $N \in \mathbb{N}$ ), a $L' \subset L$ . Czy jest możliwe, $L'$ być język nierozstrzygalny?

Widzę, że istnieje problem „Jak wybrać $N$ słów, dla których $\in$ $L' "$ dla którego musimy ustalić regułę wyboru, które będą pierwszymi $N$ elementami $L'$ , rodzajem „skończonej” operacji gwiazdy Kleene . Celem jest znalezienie języka nierozstrzygalnego bez potrzeby posiadania nieskończonego zestawu, ale nie widzę go.

Edytuj notatkę:

Chociaż wybrałem odpowiedź, wiele odpowiedzi i wszystkie komentarze są ważne.

formal-languages computability undecidability Hernan_eche
źródło

Wydaje się, że są tutaj (przynajmniej) trzy pytania. Skoncentruj się na jednym i edytuj pozostałe.

Raphael

Usunąłem odniesienia do zestawu mocy, ponieważ tutaj nie ma to znaczenia;

P (S)

$\mathcal{P}(S)$ jest skończony wtedy i tylko wtedy, gdy

S

$S$ jest skończony.

Raphael

@Raphael Jest w porządku, ale wspominam o ustawieniach zasilania, ponieważ czasami czytam „nie ma żadnych przypuszczeń z na , więc musi istnieć nierozstrzygalny język”. $\mathbb{N}$ $\mathcal{P}(\mathbb{N})$ Chciałbym zrozumieć, dlaczego to nie działało ze skończonym zestawem , z z skończonym, zamiast potrzebować , dlatego wstawiam

L^{'}

$L'$

| L^{'} | \leq N

$|L'|\leq N$

N

$N$

N

$\mathbb{N}$

P (S)

$\mathcal{P}(S)$

Hernan_eche

1

O ile mi wiadomo, istnienie nierozstrzygalnych języków nie wynika bezpośrednio z nieistnienia takiej przypuszczenia; potrzebujesz jeszcze trochę drobnych kawałków. To by było kolejne cudowne pytanie! Dlaczego nie zapytasz? Na tej podstawie powinieneś zobaczyć, dlaczego argument nie przenosi się na języki skończone.

Raphael

3

Skończony język jest rozstrzygalny, kropka, koniec historii. Jest na to dowolna liczba algorytmów. Jeśli nalegasz na klasyczny model maszyny Turinga, możesz to zrobić w ten sposób, choć mniej wnikliwie. Nie trzeba przywoływać automatów skończonych ani zwykłych języków ani żadnego innego modelu automatu, ponieważ w rzeczywistości są one nadmierne, bez żadnej dodatkowej przejrzystości w stosunku do maszyn Turinga.

David Lewis

15

Tak, musi być nieskończony, aby być niezdecydowanym. $L$

Podsumowując odpowiedzi Raphaela i Sama, powinieneś pomyśleć o „rozstrzygalnej” jako rzeczy, którą program komputerowy może rozwiązać. Wymagany program jest bardzo prosty, wystarczy wypisać „Tak” dla elementów w , lub inaczej powiedzieć „nie”. $L$

Im bardziej „złożony” jest , tym dłuższy program musisz napisać. Innymi słowy, im dłużej uruchamiasz program, możesz sprawdzić więcej rzeczy ... Jeśli więc ktoś poda język który jest skończony, powiedz , możesz napisać następujący program: $L$ $L$ $L=\{ a_1, a_2, \ldots, a_n\}$

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Teraz, jeśli ktoś da ci większy (jeszcze skończony), po prostu napiszesz dłuższy program. Jest to zawsze prawdą, a każdy skończony będzie miał swój własny program. Jedynym „interesującym” przypadkiem jest to, co dzieje się, gdy jest nieskończony - twój program nie może być nieskończony. $L$ $L$ $L$

Kwestia „nierozstrzygalności” jest jeszcze bardziej interesująca: te (nieskończone) , które nie mają programu, który działałby dla nich poprawnie. Wiemy, że takie języki muszą istnieć, ponieważ istnieje znacznie więcej (nieskończonych) języków niż liczba programów o skończonej (ale nieograniczonej) długości. $L$ $L$

Ran G.
źródło

+1 To jest bardzo jasna odpowiedź, chciałbym, żebyś poszerzył punkt, powiedziałeś „jeśli ktoś przyniesie ci większy (jeszcze skończony), po prostu napiszesz dłuższy program” *, ale myślę, że przeciwnie, biorąc pod uwagę ** ustalony ** skończony zestaw programów , co jeśli nie możesz napisać dłuższego programu, myślę, że niektóre przypisują skończony zestaw, wyłączy TAK, a niektóre nie . Jako , to niektóre przypisania będą odpowiadały funkcjom wskaźnika ale * większość $L$ $P$ $|P|=K$ $\in L$ $\mathcal{P}(P) \gt K$ $\in L$ $P$ nie będzie!, Ponieważ możliwych języków

2^{K}

$2^K$

> K

$\gt K$ możliwe programy, wtedy pojawią się nierozstrzygalne problemy. Czy się mylę? dlaczego?

Hernan_eche

1

w rzeczywistości, jeśli ograniczysz rozmiar programu do wówczas istnieje co najwyżej różne programy, które poprawnie klasyfikują co najwyżej różne języki (nieskończone lub nie). Dla tego konkretnego zestawu programów istnieją nierozstrzygalne języki, a nawet skończony. Ale jest to słabsze stwierdzenie, ponieważ rozważasz tylko ograniczony zestaw programów (np. , masz tylko 2 możliwe programy; oczywiście nie będą one w stanie wiele zrobić i zawiodą w prawie każdym języku )

| P | = k

$|P|=k$

O (2^{k})

$O(2^k)$

O (2^{k})

$O(2^k)$

| P | = 1

$|P|=1$

L

$L$

Ran G.

Dzięki, wiem, że jest słabszy stwierdzenie, ale to śmiały, że nie może być skończone i nieskończone nierozstrzygalny Języki i myślę, że ten szczególny przypadek musi być włączone w Twojej odpowiedzi, parte „Tak, istnieje zapotrzebowanie na L być nieskończona być nierozstrzygalnym ”. pod pewnymi warunkami nie wydaje się potrzebna .

Hernan_eche

6

Nie dokładnie. Termin „nierozstrzygalny” ma określone znaczenie: nie może być rozstrzygany przez standardową maszynę Turinga. Tak więc, aby być undecidable, musi być nieskończone. To, czego chcesz, to nie inny termin, a mianowicie „niepodlegający rozstrzygnięciu przez ”. Nazwij to drugie niezdecydowanym. Zatem dla jakiegokolwiek skończonego nie ma potrzeby, aby był nieskończony, aby być nierozstrzygalnym. Tylko nie myl (lub niewłaściwie używaj ) i nierozstrzygalne

L

$L$ undecidable

P

$P$

P

$P$

P

$P$

L

$L$

P

$P$ undecidable

P

$P$

Ran G.

10

Nie jestem pewien, czy dobrze rozumiem pytanie, ale każdy skończony język jest regularny. Nie ma zwykłych języków, których nie można rozstrzygnąć, dlatego też nie ma języków skończonych, których nie można rozstrzygnąć. Wszystkie te stwierdzenia są dobrze znane, a dowody można znaleźć w Hopcroft i Ullman .

Sam Jones
źródło

8

Jeśli Twój język jest skończony, możesz wykonać wyszukiwanie tabeli na sztywno zakodowanej tabeli zawierającej wszystkie słowa w . Trudno to zapisać jako maszynę Turinga, ale w innych równoważnych modelach jest to całkiem jasne. $L'$ $L'$

W rzeczywistości skończone automaty są wystarczające. Skonstruuj automat dla w następujący sposób: $L'$

Dla każdego utwórz liniowy łańcuch stanów, który akceptuje . $w \in L'$ $w$
Utwórz nowy stan początkowy . $q_0$
Połącz ze stanami początkowymi wszystkich automatów zbudowanych w 1. za pomocą -transitions. $q_0$ $\varepsilon$

Tak skonstruowany automat oczywiście akceptuje . Dlatego jest regularne, a tym samym obliczalne (przez ). $L'$ $L'$ $\mathrm{REG} \subsetneq \mathrm{RE}$

Zauważ, że pewne rozumowanie dotyczy współistnienia , czyli ; po prostu zakodować elementy nie w . $L'$ $\big|\overline{L'}\big| < \infty$ $L'$

Raphael
źródło

2

Aby być w ogóle interesującym (w celu myślenia o obliczalności) problem decyzyjny musi mieć nieskończenie wiele odpowiedzi „tak” i nieskończenie wiele odpowiedzi „nie”. Takie problemy decyzyjne odpowiadają dokładnie tym, że języki zawierają nieskończenie wiele ciągów znaków nad alfabetem, a także wykluczają nieskończenie wiele ciągów znaków nad alfabetem.

Wszystko inne można w prosty sposób zakodować w skończonej ilości informacji (w najgorszym przypadku po prostu duża lista ciągów w języku lub nie w języku), a zatem można je obliczyć za pomocą prostych DFA / wyrażeń regularnych. Mam nadzieję, że powinno być oczywiste, że dla każdej skończonej listy ciągów możesz od razu zapisać wyrażenie regularne, które po prostu OR wszystkie ciągi.

Dowcip mojej wykładowcy Teorii Obliczeń polegał na tym, że problem „czy Bóg istnieje?” jest obliczalny - jest albo obliczany przez maszynę, która natychmiast akceptuje, lub maszynę, która natychmiast odrzuca; po prostu nie wiemy, który!

Ben
źródło

Czy istnieje niezdecydowany skończony język skończonych słów?

Odpowiedzi: