Maszyny Turinga z pojedynczą taśmą z wejściem chronionym przed zapisem rozpoznają tylko zwykłe języki

Oto problem:

Udowodnij, że maszyny Turinga z pojedynczą taśmą, które nie mogą pisać na części taśmy zawierającej łańcuch wejściowy, rozpoznają tylko zwykłe języki.

Moim pomysłem jest udowodnienie, że ta konkretna baza TM jest odpowiednikiem DFA.

Używanie tej TM do symulacji DFA jest bardzo proste.

Jednak gdy chcę użyć tego DFA do symulacji TM, napotykam problem. W przypadku przejścia TM DFA może zdecydowanie symulować, odczytując taśmę po prawej stronie i wykonując to samo przejście stanu.$\delta(q,a)=(q',a,R)$

Dla nie mogę wymyślić, jak użyć tego DFA lub NFA do symulacji ruchu w lewo, ponieważ DFA czyta tylko w lewo i nie ma stosu ani czegoś do przechowywania.$\delta(q,a)=(q',a,L)$

Czy powinienem rozważyć inny sposób? Czy ktoś mógłby dać mi jakieś wskazówki? Dzięki.

Wprowadzenie

Pomyślałem, że może być błąd w pierwotnym stwierdzeniu pytania, a PO nie było już w pobliżu, by go zapytać. Więc założyłem, że taśma jest wszędzie tylko do odczytu, i napisałem pierwszy dowód oparty na tym założeniu, motywowany faktem, że TM ma pełną moc Turinga poza wejściową częścią taśmy, jeśli może ją zapisać, co powoduje fałsz przekonanie, że może rozpoznać dowolny język RE.

Jednak tak nie jest: ograniczenie zapisu na części wejściowej taśmy oznacza, że ​​z danych wejściowych można wyodrębnić tylko skończoną informację, ograniczoną liczbą stanów na wejściu i wyjściu z tej części taśmy (w połączeniu z strona wejścia i wyjścia). Instruowanie należy przypisać za uwagę w komentarzu, że istnieje problem z rozpoznawaniem dowolnego języka RE, ponieważ nie można wykonać kopii danych wejściowych bez PISZTEGO zapisu w oryginalnym obszarze wprowadzania,

Dlatego napisałem drugi dowód, który zakłada, że ​​tylko sekcja wejściowa taśmy jest tylko do odczytu, reszta jest dozwolona do odczytu i zapisu.

Trzymam tutaj oba dowody, ponieważ pierwszy pomógł mi znaleźć rozwiązanie, chociaż nie jest konieczne zrozumienie drugiego dowodu, jest bardziej złożony i jest objęty drugim dowodem. Można go pominąć. Jednak słabszy dowód ma tę zaletę, że jest konstruktywny (aby uzyskać FSA równoważny maszynie Turinga), podczas gdy bardziej ogólny wynik nie jest konstruktywny.

Daję jednak pierwszy ostatni i mocniejszy wynik. Jestem nieco zaskoczony, że nie byłem w stanie znaleźć tego wyniku, nawet bez dowodu, w innym miejscu w sieci lub pytając kompetentnych użytkowników, a wszelkie odniesienia do opublikowanych prac byłyby mile widziane.

Zawartość:

• Maszyny Turinga, które nie nadpisują danych wejściowych, akceptują tylko zwykłe języki. Ten dowód nie jest konstruktywny.

• Maszyny Turing z taśmami tylko do odczytu akceptują tylko zwykłe języki. Może być pomijany jako poprzedni dowód, ale stosuje inne podejście, które ma tę zaletę, że jest konstruktywne.

Maszyny Turinga, które nie nadpisują danych wejściowych, akceptują tylko zwykłe języki

Pamiętamy, że chociaż TM nie zastępuje danych wejściowych, a zatem jest odczytywana tylko na danych wejściowych, TM może odczytywać i zapisywać na pozostałej części taśmy . Dowód opiera się na fakcie, że zachowanie obserwacyjne TM na nieznanych danych wejściowych może dać tylko skończoną liczbę różnych przypadków. Stąd, chociaż TM ma pełną moc Turinga, polegając tylko na pozostałej części taśmy, jej informacje na wejściu, którym może być dowolny ciąg w , są skończone, więc może obliczać tylko na skończonej liczbie różnych przypadków. To daje odmienne spojrzenie na skończony charakter zwykłych języków, bardziej behawioralny niż strukturalny.$\Sigma^*$

Zakładamy, że TM akceptuje, kiedy wejdzie w stan akceptacji.

Dowód.

Definiujemy obliczenia z ograniczeniami wejściowymi (IRC) jako obliczenia TM (tylko do odczytu), dzięki czemu głowica TM pozostaje na wejściowej części taśmy, z wyjątkiem ewentualnie ostatniego przejścia, które może przenieść ją do komórki bezpośrednio w na lewo lub na prawo od obszaru wprowadzania.

Lewe wejście ograniczone obliczenia jest IRC, który rozpoczyna się w skrajnej lewej symbol wejścia. Prawo wejście ograniczone obliczenia jest IRC, który rozpoczyna się w skrajnej prawej symbol wejścia.

Najpierw udowodnimy, że w przypadku obliczeń ograniczonych przy wprowadzaniu z lewej strony, które rozpoczynają się w stanie , następujące języki są normalne:$p$

• język ciągów wejściowych tak, że istnieje lewe obliczenie wejściowe ograniczone, rozpoczynające się w stanie p , które kończy się na pierwszej komórce po lewej stronie lewego wejścia symbolu w stanie q ;$K_{Lp\to Lq}$$p$$q$

• język ciągów wejściowych tak, że istnieje lewe obliczenie wejściowe ograniczone, rozpoczynające się w stanie p , które kończy się na pierwszej komórce po prawej stronie najbardziej prawego symbolu wejściowego w stanie q ;$K_{Lp\to Rq}$$p$$q$

• język ciągów wejściowych taki, że istnieje lewostronne obliczenia wejściowe, zaczynające się od stanu p , który osiąga stan akceptacji.$A_{Lp}$$p$

I podobnie, dla obliczeń ograniczonych dla prawego wejścia rozpoczynających się w stanie , następujące podobnie zdefiniowane języki są regularne: K R p → L q , K R p → R q i A R p .$p$$K_{Rp\to Lq}$$K_{Rp\to Rq}$$A_{Rp}$

6 dowodów opiera się na fakcie, że dwukierunkowe niedeterministyczne automaty skończone (2NFA) rozpoznają zbiory regularne (patrz Hopcroft + Ullman 1979, str. 36-41 i wykonanie 2.18 strona 51). 2NFA działa jak TM tylko do odczytu na taśmie ograniczonej do jej wejścia, zaczynając początkowo od lewego skrajnego symbolu i akceptując, przechodząc poza prawy koniec w stanie akceptującym.

W każdym z 6 przypadków dowód wykonuje się przez zbudowanie 2NFA, który naśladuje obliczenia o ograniczeniach wejściowych, ale z pewnymi dodatkowymi przejściami, aby upewnić się, że może zacząć od lewej komórki i zaakceptować język, wychodząc z skrajnego prawego końca w akceptującym stan. Dla języki, pierwotny stan akceptacji bazy TM są zmieniane na stany prowadzące do zatrzymania nieakceptowalnych obliczeń. W dwóch przypadkach może być konieczne dodanie dodatkowej komórki z nowym symbolem zabezpieczającym po lewej stronie, aby wykryć obliczenia TM, które zakończyłyby się na lewym końcu, tak aby zakończyły się na prawym końcu.$K_{??\to ??}$

Języki te są zdefiniowane dla wszystkich kombinacji stanów i q oryginalnej maszyny Turinga. Reprezentują one wszystko, co można zaobserwować (stąd znane i obliczone) danych wejściowych przez TM.$p$$q$

Jeśli jest liczbą stanów, definiujemy zatem 4 k 2 języków K ? ? → ? ? i 2 k języków A ? ? , a zatem łącznie 4 k 2 + 2 k języków. W rzeczywistości niektóre z tych języków mogą być równe.$k$$4k^2$$K_{??\to ??}$$2k$$A_{??}$$4k^2+2k$

Są to jedyne możliwe obliczenia z ograniczeniami wejściowymi TM rozpoczynające się na jednym końcu wejścia. Dlatego obliczenia indukowane przez każdy ciąg wejściowy (poza sekcją wejściową taśmy) charakteryzują się zestawem takich języków, do których dane wejściowe należą lub nie należą, stąd przecięcie każdego z tych języków lub jego uzupełnienie w Σ ∗ . Wszystkie te przecięcia są skończonymi przecięciami regularnych języków r 4 k 2 + 2 k lub ich dopełnieniem, które są również regularne, a zatem regularne.$4k^2+2k$$\Sigma^*$$4k^2+2k$

W konsekwencji, zestaw tych skrzyżowaniach definiuje partycji o Ď * do co najwyżej 2 4 k 2 + 2 k regularnych języków ( co najwyżej , ponieważ niektóre początkowe języki mogą być równe, a niektóre mogą być zbyt skrzyżowań). Wszystkie ciągi należące do tej samej klasy równoważności mogą wytwarzać dokładnie takie samo zachowanie, jak widać na końcach danych wejściowych. Oznacza to, że nie można ich rozróżnić do obliczeń maszyny Turinga, jeśli oddzielisz to, co dzieje się w obszarze wejściowym tylko do odczytu.$\mathcal P$$\Sigma^*$$2^{4k^2+2k}$

$u$$v$$\mathcal P$$u$$v$$\mathcal P$

Aby być bardzo kompletnym, pominęliśmy wielkość liter pustego ciągu wejściowego. W tym przypadku mamy po prostu normalną bazę TM, która może czytać lub pisać w dowolnym miejscu. Jeśli osiągnie stan akceptacji, pusty ciąg znaków jest w języku, w przeciwnym razie nie. Ma to jednak niewielki wpływ na fakt, że rozpoznawany język jest prawidłowy.

Oczywiście nie jest rozstrzygalne, czy klasa równoważności jest w języku, czy nie (to samo dotyczy pustego łańcucha). To nie jest konstruktywny dowód.

CO BYŁO DO OKAZANIA

Maszyny Turing z taśmami tylko do odczytu akceptują tylko zwykłe języki

Jest to uwzględniane przez poprzedni wynik. Został zachowany, ponieważ używa innego podejścia, prawdopodobnie mniej eleganckiego, i pomógł mi znaleźć poprzedni dowód, rozumiejąc, co się liczy. Ale czytelnicy mogą go pominąć. Jednak jedną z zalet tego dowodu jest to, że jest to konstruktywny dowód produkujący FSA akceptujący język. Szkic podobnego dowodu podał Hendrik Jan w swojej odpowiedzi na poprzednie podobne pytanie , która zakłada, że ​​cała taśma była tylko do odczytu.

$\Box$

Pierwszym krokiem dowodu jest wykazanie, że głowa nigdy nie musi opuszczać obszaru wejściowego taśmy. W ten sposób analizujemy, co się stanie, gdy głowa zejdzie z najbardziej prawego symbolu wejściowego. Analiza przy wyjeździe z lewej jest identyczna.

$q$

1. TM nieprzerwanie wykonuje obliczenia, a głowa nigdy nie wraca na wejściową część taśmy;

2. TM osiąga (a) akceptuje lub (b) zatrzymuje się w stanie nieakceptującym;

3. $r$

$q$

$\Box$$1$$0$

$0$

Reprezentujemy odpowiednią część kontroli stanu skończonego za pomocą ukierunkowanego wykresu, w którym wierzchołki to stany TM, a krawędzie to puste przejścia, o wadze +1 lub -1 w zależności od tego, czy głowa ma się poruszać prawo czy lewo.

$A_R$$q$

$E_R$$(q,r)$$-1$$q$$r$

$\Box$

$q_A$

$p,a\mapsto R,q$$p,a\mapsto R,q_A$$q\in A_R$

$p,a\mapsto R,q$$(q,r)\in E_R$$p,a\mapsto S,r$$S$

$a$$F_a=\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto S,r\}$$F_a^*$$F_a$$r,a\mapsto L,s$$(p,r)\in F_a^*$$p,a\mapsto L,s$

$+1$$-1$

$q_A$

Musimy teraz dokonać kilku kosmetycznych zmian, aby ta TM zachowywała się dokładnie tak, jak NDA na dwa sposoby (akceptacja następuje tylko poprzez wyjście z wejścia po prawej stronie w stan eksciptyczny). Następnie możemy polegać na znanej równoważności między 2-NDA a FSA (patrz na przykład Hopcroft + Ullman 1979, strona 40), aby uzyskać dowód, że język jest prawidłowy.

CO BYŁO DO OKAZANIA

Poruszanie się w lewo lub w prawo nie stanowi problemu, ponieważ dwukierunkowe automaty skończone rozpoznają dokładnie zwykłe języki (nie jest to oczywiste). Jeśli jednak twoja TM może pisać poza częścią taśmy słowa wejściowego, myślę, że możesz użyć tej części taśmy do rozpoznawania w zwykłych językach. Może nie rozumiem dokładnie pytania.