Dlaczego maszyna Turinga rozpoznaje dokładnie jeden język?

Próbuję zrozumieć istnienie języków nierozpoznawalnych. Aby to uzyskać, muszę wiedzieć, dlaczego maszyna Turinga rozpoznaje tylko jeden język, a nie wiele. Dlaczego to?

Językiem rozpoznawanym przez maszynę Turinga jest z definicji zestaw ciągów, które akceptuje. Gdy dane wejściowe są podawane do maszyny, są albo akceptowane, albo nie. Wszelkie dane wejściowe do tego komputera są zawsze akceptowane (w języku) lub zawsze nieakceptowane (nie w języku). Nie ma więc mechanizmu, za pomocą którego jedna maszyna Turinga mogłaby zaakceptować więcej niż jeden język.

Pomyśl o tym w ten sposób: TM jest jak komputer z załadowanym oprogramowaniem. Każde oprogramowanie ma jedną rzecz, prawda? Na przykład pomyśl o swoim komputerze i załóż, że ma załadowany tylko 1 program. Następnie PC + „Photoshop” robi tylko Photoshop, a PC + „Sweeper” zamiata tylko miny.

Tak więc maszyna Turinga jest bardzo prostym stworzeniem, które na każdym biegu otrzymuje pojedyncze wejście i generuje albo tak, albo nie . Na których wejściach mówi „tak”, a na „nie” - jest to ustawiane przez „program” bazy TM, określony przez jego stany i funkcję przejścia. Po ich naprawieniu „program” zostaje naprawiony, a dla każdego danego wejścia istnieje tylko jedna odpowiedź: Tak lub Nie (zaakceptuj / odrzuć). Definiuje to dokładnie jeden język = wszystkie dane wejściowe, które dają TAK, gdy są podane do TM.

Z drugiej strony, zestaw z wszystkich baz jest równoznaczne z zestawem komputerowym + „oprogramowania” ze wszystkich możliwych programów. Teraz można zdecydować o większej liczbie języków - ale każda konkretna baza TM decyduje (lub rozpoznaje) tylko jeden język.

Maszyna Turinga działa tak jak oni, ponieważ my decydujemy się na ich zdefiniowanie. Moglibyśmy mieć bardziej wyrafinowane definicje, ale pytanie brzmi, czy służy to celowi, czy pozwala nam robić więcej rzeczy. O ile wiemy, odpowiedź brzmi „nie”.

$L_1$$L_2$$L_1$$L_2$$L_i$

$L_1$$L_2$

Chodzi o to, że do wykonania teorii można użyć wszelkiego rodzaju wariantów. Próbowano również bardzo różnych podejść do modelowania tego, co jest obliczeniem, takich jak rachunek lambda, logika kompinacyjna, teoria funkcji rekurencyjnych i więcej.

Zawsze wykazano, że żaden z nich nie robi niczego, czego nie da się zrobić za pomocą naszego prostego modelu, w którym TM rozpoznaje tylko jeden język. Do tego stopnia, że ​​przypuszczono, że robi wszystko, co można zrobić. Nazywa się to tezą Kościoła Turinga . Jest to podstawa teorii obliczalności, która, o ile wiemy, określa, które języki są rozpoznawalne, czy nie.

Równie dobrze moglibyśmy użyć prostego modelu, ponieważ skomplikowany utrudni nam życie bez żadnych realnych korzyści.

Oczywiście czasami używamy innych modeli, ponieważ pozwalają nam lepiej zrozumieć niektóre problemy.

Chciałbym rozwinąć jeden punkt odpowiedzi Richerby:

Gdy dane wejściowe są podawane do maszyny, są albo akceptowane, albo nie.

Powodem tego jest to, że maszyna Turinga jest deterministyczna: biorąc pod uwagę ten sam stan wejściowy i początkowy, zawsze zrobi to samo za każdym razem, gdy ją uruchomisz (albo zakończy się w tym samym stanie akceptacji lub w tym samym stanie odrzucenia, albo zapętli na zawsze ).

Dodatkowo możemy łatwo udowodnić, że każda maszyna Turing rozpoznaje dokładnie jeden język:

Załóżmy, przeciwnie, że maszyna Turinga M rozpoznaje dwa odrębne języki L1 i L2. Ponieważ L1 i L2 są różne, musi istnieć ciąg S, który jest w L1, ale nie w L2 (bez utraty ogólności - może być na odwrót, ale dowód przebiegałby w ten sam sposób z wymienionymi L1 i L2 ). Teraz uruchom M na S. Jeśli zaakceptuje, wówczas osiągnięta zostanie sprzeczność, ponieważ wtedy S będzie w L2. Jeśli nie akceptuje (odrzuca lub zapętla), dochodzi do sprzeczności, ponieważ S nie byłoby w L1.

Maszyna Turinga rozpoznaje jeden język, ponieważ taka jest definicja słowa „ rozpoznawaj” : Język, który rozpoznaje maszyna Turinga, to zbiór wszystkich ciągów / danych wejściowych, dla których maszyna Turinga akceptuje.

Odpowiedź zależy od tego, co dokładnie rozumiesz, kiedy masz na myśli „maszynę Turinga”. Każdy model obliczeniowy składa się z trzech elementów (ograniczając się tutaj do decydentów / akceptantów):

• składnia,
• semantyka,
• kryteria przyjęcia.

W przypadku maszyn Turinga składnia będzie krotką zestawu stanów, alfabetów, funkcji przejścia i tak dalej. W semantyka będzie definicja obliczeń , że jest opisanie, jak zastosować funkcję przejścia w celu uzyskania zawartości taśmy Po kilku krokach. Kryterium przyjęcia jest, aby powiedzieć „kiedy to nastąpi, możemy zatrzymać i wynik jest, że”.

Czy maszyny Turinga są dla ciebie tylko składnią i semantyką, czy też zawierasz również kryterium akceptacji? Jeśli to zrobisz, każda TM może zaakceptować wiele języków, stosując różne kryteria akceptacji; możesz nawet wymyślić kryteria akceptacji, które pozwalają na wiele akceptowanych języków (na przykład pomyśl o dwuparametrowych bazach TM). Jeśli jednak zrobisz to drugie, nie ma miejsca na poruszanie się, a zwykłe kryterium akceptacji rzeczywiście dopuszcza dokładnie jeden język na TM (tego typu).

Zwykle definicja i użycie tego terminu w TCS zawiera wszystkie trzy składniki. Ma to sens, ponieważ w szczególności zmianę kryterium akceptacji może zmienić klasę obiektów automat reprezentuje drastycznie , więc trzeba ustalić kryterium, aby wiedzieć, o czym mówimy.

Jako przykład porównaj automaty skończone i automaty Büchi . Składnia i semantyka są dokładnie takie same, ale jedno akceptuje słowa skończone, a drugie nieskończone!
Spróbuj dowiedzieć się, co się stanie, jeśli podłączysz kryterium akceptacji automatów Büchi do definicji TM.

Dlaczego więc zwykłe kryterium akceptacji jest znaczące? Dopóki ograniczysz się do języka skończonych łańcuchów, niewiele się zmieni, mając wiele języków na TM, na poziomie koncepcyjnym: nadal będziemy w stanie zaakceptować ten sam zestaw języków. Trzymamy się więc prostszego modelu. Nie oznacza to jednak, że bardziej zaangażowany model nie może być przydatny do modelowania w aplikacjach - ale wykracza to poza zakres TCS (który ma władzę ostateczną).

$M_{1}$$L_{1}$$L_{2}$$L_{1} \neq L_{2}$$s_{1}$$s_{1} \in L_{1}$$s_{1} \notin L_{2}$$M_{1}$$s_{1}$$s_{1} \notin L_{2}$$M_{1}$$s_{1}$$s \in L_{2}$$s \notin L_{1}$

$M$$L$$s \in L$$M$$s$$s$$M$$s \in L$

$s \in L \iff M$$s$

$A_{TM}$

Język to zestaw ciągów znaków. Czy połączenie dwóch języków L1 i L2 nie jest zbiorem ciągów (nazwijmy to L3), a więc byłby to inny język? Następnie, jeśli maszyna Turinga rozpozna oba języki, rozpozna L3, jeden język.

żadna inna odpowiedź nie wskazuje na istnienie Uniwersalnej Maszyny (maszyn) Turinga, jak to po raz pierwszy opisano / odkrył Turing w swoim dowodzie zatrzymania. tak, TM przyjmuje pojedynczy język, który można wyliczyć rekurencyjnie, ale UTM może rozpoznać każdy język, który można wyliczyć rekurencyjnie, jeśli jest zakodowany na wejściu wraz z łańcuchem wejściowym. więc pytanie ma jakość zen. Zarówno bazy TM akceptują tylko jeden język i wszystkie możliwe języki kodowane.