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

13

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?

turing-machines computation-models

— Anonimowy
źródło

12

Podejrzewam, że możesz nie mieć jasnego pojęcia, co rozumiemy przez „język”. Czy możesz powiedzieć, co według ciebie jest „językiem”?

— Eric Lippert,

Dlaczego musisz to wiedzieć? Jak myślisz, w jaki sposób może to zmienić?

— babou

29

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.

— David Richerby
źródło

6

„Z definicji” jest dokładnie tym, co powiedziałbym.

— Dave Clarke

1

@DaveClarke Oczywiście jest to z definicji. Ale wydaje mi się to trochę krótkie, ponieważ mówi również, że możemy zmienić naszą definicję, aby TM akceptowała dwa języki lub dowolną liczbę. Właściwie nie zgadzam się ze stwierdzeniem Davida Richerby'ego, że nie ma mechanizmu, za pomocą którego TM mogłaby zaakceptować dwa języki: dzieje się tak tylko dlatego, że decydujemy się je zignorować i moglibyśmy zrobić inaczej. Dlatego pytanie nie jest w pełni udzielone, imho, jeśli nie wyjaśnimy, co to uzasadnia.

— babou

2

Myślę, że problemem jest język używany do opisu samego „języka”. Maszyna Turinga przyjmuje wszystko w postaci łańcucha bez względu na naszą definicję języka. TM definiuje język na podstawie tego, co akceptuje, nie jest to to samo, co nasze (ludzkie) rozumienie języka. Dlatego ta odpowiedź jest dobra i brzmi „... w pełni udzielona odpowiedź”.

— David Barker,

2

Zgadzam się z Davidem, OP prawdopodobnie czytał gdzieś, że maszyny Turinga akceptują tylko jeden język i próbuje zrozumieć, co to oznacza. Biorąc pod uwagę, że prawdopodobnie pochodzi on z normalnego źródła, możemy założyć, że używali normalnej definicji „języka” zdefiniowanej w teorii obliczeniowej, a nie żadnej innej definicji. Definicja może być dowolna, ale jest to dobrze zrozumiana i uzgodniona arbitralna definicja.

— Cort Ammon

3

Maszyna Turinga, która akceptuje dwa języki, to maszyna Turinga, która akceptuje język będący połączeniem dwóch języków.

— Simon Richter

9

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.

— Ran G.
źródło

Drobna uwaga: nie powiedziałbym, że TM generuje „tak lub nie”, ponieważ pomija to nieterminację. Uproszczenie to może powodować dalsze problemy w przyszłości.

— chi

4

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.

— Babou
źródło

Uważam, że pierwszy akapit jest nieco mylący. Jestem skłonny założyć się, że OP nie pyta o to, dlaczego tak definiujemy, ale nawet nie wiedzieli, że tak jest. „Moglibyśmy mieć bardziej wyrafinowane definicje, ale pytanie brzmi, czy miałoby to służyć celowi” sprawia, że wydaje się, że musisz znać cel koncepcji, zanim będziesz w stanie pojąć jej nazwę - moim zdaniem, to źle sposób na naukę.

— ciekawe,

OP twierdzi, że chce wiedzieć, dlaczego TM rozpoznaje tylko jeden język, aby zrozumieć coś innego. Odpowiadam mu, robią tak, ponieważ my je definiujemy w ten sposób. Dodam, co prawda, że moglibyśmy użyć różnych definicji, ale nie zmieniłoby to teorii. Jest to sposób na powiedzenie mu, że cokolwiek on szuka, wybór definicji jest nieistotny i że można zdefiniować rozpoznawalność obejmującą dokładnie te same zbiory. Powodem wyboru definicji jest wygoda i płodność, dlatego ewoluują one wraz z upływem czasu, a także sposób nazwania lub odnotowania pojęć.

— babou

Ok, to ma sens. Myślę, że przede wszystkim sprzeciwiam się użyciu „wyrafinowanego” - implikuje to, że pożądana jest mniej prosta definicja.

— ciekawe,

3

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.

— Atsby
źródło

2

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.

— co ciekawe
źródło

2

Witamy w informatyce ! Twoja odpowiedź jest (IMO) prawidłowa, ale nie sądzę, żeby stanowiła uzupełnienie wcześniej istniejących odpowiedzi. Mamy wiele pytań bez odpowiedzi i odpowiedź na jedno z nich byłaby o wiele bardziej interesująca i produktywna niż powtarzanie istniejących odpowiedzi.

— David Richerby,

1

Dzięki! Właściwie nie widziałem początkowo akceptowanej odpowiedzi (którą uważam za dobrą), ponieważ była ona tak krótka, i czułem, że inne odpowiedzi nie odpowiedziały na pytanie w prosty sposób.

— ciekawe,

1

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ą).

— Raphael
źródło

0

$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}$

— użytkownik3730788
źródło

Nie jest konieczne, aby udowodnić, że baza danych rozpoznaje tylko jeden język: jest to natychmiastowe z definicji „rozpoznaj”. Biorąc pod uwagę tę definicję, nie jest nawet jasne, co to znaczy, że TM akceptuje więcej niż jeden język (jak przypuszczasz w pierwszym zdaniu) lub czy jakakolwiek dedukcja z takiego założenia (jak w trzecim zdaniu) jest prawidłowa. Dowód sprzeczności działa tylko wtedy, gdy odliczenia są wodoszczelne: w tym przypadku błędem może być założenie o tym, jak zachowuje się TM, która rozpoznaje TM, a nie założenie, że taka maszyna istnieje.

— David Richerby

-2

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.

— Joe Cash
źródło

2

Ale maszyna Turinga nie rozpoznaje obu języków, chyba że w rzeczywistości są takie same. Rozpoznanie L1 oznacza, że nie akceptuje żadnego łańcucha poza L1; rozpoznanie L2 oznacza, że nie akceptuje niczego poza L2. Jeśli L1 i L2 są różne, nie może rozpoznać obu.

— David Richerby

-3

ż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.

— vzn
źródło

4

{⟨ M, x ⟩ ∣ M accepts x}

$\{\langle M,x\rangle\mid M\text{ accepts }x\}$

⟨ - ⟩

$\langle-\rangle$

a czym to się różni od tego, co napisano?

— vzn

2

Rozpoznawanie kodowania języków to nie to samo, co rozpoznawanie języków.

— David Richerby

tak dokładnie, jak podano

— 2015 r

1

{(m, x) ∣ m = ⟨ M ⟩, \dots}

$\{ (m, x) \mid m = \langle M \rangle, \dots \}$

x

$x$

m

$m$