Czy istnieją nierozstrzygalne właściwości niekompletnych automatów?

15

Czy istnieją nierozstrzygalne właściwości automatów z ograniczeniami liniowymi (unikanie sztuczki z pustym językiem ustawiania)? A co z deterministycznym automatem skończonym? (odłóż na bok trudność).

Chciałbym uzyskać przykład (jeśli to możliwe) niezdecydowanego problemu, który jest zdefiniowany bez jawnego używania maszyn Turinga .

Czy kompletność modelu Turinga jest niezbędna do obsługi problemów nieobliczalnych?

computability automata undecidability

— Hernan_eche
źródło

„Czy istnieje rozwiązanie dla tego układu równań diofantycznych?” Czy o to pytasz? Nie jest dla mnie jasne, czego chcesz. Ale problem, który podałem, jest nierozstrzygalny i nie wspomina o TM, więc, ściśle mówiąc, wydaje się, że spełnia wymogi twojego drugiego akapitu.

— rgrig

Decydowanie, czy dwa automaty wypychające rozpoznają te same słowa, jest nierozstrzygalna, podobnie jak inne problemy związane z automatami wypychającymi . Nie mogę wymyślić nierozstrzygniętych problemów związanych z DFA.

— jmad

1

Odpowiedź na pytanie „Czy można zbudować nierozstrzygalny problem dla automatu o mniejszej mocy niż maszyna Turinga” brzmi „ tak” . W rzeczywistości dla każdego rodzaju automatu zawsze można zidentyfikować nierozwiązywalny problem.

— Amelio Vazquez-Reina,

1

Biorąc pod uwagę przyjętą odpowiedź, sformułowałem pytanie, aby zapytać, czego chce OP (najwyraźniej).

— Raphael

15

Nierozstrzygalne problemy z gramatykami bezkontekstowymi, a zatem także z akceptorami push down, które są ograniczonymi bazami TM z Wikipedii ...

Biorąc pod uwagę CFG, czy generuje język wszystkich ciągów znaków nad alfabetem symboli końcowych używanych w jego regułach?
Biorąc pod uwagę dwa CFG, czy generują ten sam język?
Biorąc pod uwagę dwa CFG, czy pierwszy może wygenerować wszystkie ciągi, które drugi może wygenerować?

Istnieje wiele innych informacji na temat CFG / PDA, a także CSG / LBA i wielu innych modeli „prostszych niż TM”.

— David Lewis
źródło

+1, dziękuję, wciąż mam ochotę zapytać o prostsze niż CFG i tak dalej ... aby dowiedzieć się, który z pierwszych (prostszych) znanych automatów + problem jest nierozstrzygalny

— Hernan_eche

3

Aby znaleźć „prostszy” lub „najprostszy” problem, który jest nierozstrzygalny lub ma jakąkolwiek właściwość, potrzebujesz dokładnej definicji „prostego”, z których wiele jest możliwych. Ale klasyczny w automatach i językach formalnych to „poziom w hierarchii Chomsky'ego” (który nie jest tak naprawdę hierarchią, mówiąc matematycznie - pierwotnie był proponowany dla gramatyki języka naturalnego). FSA jest najniższy i jestem prawie pewien, że jakikolwiek nierozstrzygalny problem dla FSA musiałby w jakiś „istotny” sposób odnosić się do „mniej prostych” formalizmów (wszystkie wymagają dokładnej definicji). CFL / CFG jest następny najwyższy, więc wybrałem to.

— David Lewis

+1 Zgadzam się, stwierdzam, że minimalne jest również nierozstrzygalne, zaskakująco nie jest możliwe zbudowanie nierozstrzygalnego problemu dla FSA, to jest możliwe dla CFG, po prostu kusi, aby znaleźć coś pomiędzy, dzięki

— Hernan_eche

1

@Hernan_e - istnieje bardzo bogata struktura modeli i języków sub-CFL - na przykład pda / rodzina 1-licznikowa, która używa dodatniej liczby całkowitej „licznik” zamiast pda; n-turn pda, który pozwala tylko zwoje od zwiększenia do zmniejszenia stosu i uogólnienia tych. Istnieje wiele nierozstrzygniętych kwestii na ich temat, a także otwarte pytania dotyczące struktur, na przykład: czy istnieje „minimalna” nieregularna świetlówka kompaktowa w jakimś precyzyjnym pojęciu „minimalna”. Ale te rzeczy są zwykle na poziomie studiów i / lub badań.

— David Lewis,

7

Nie jest jasne, o co pytasz w dalszej części pytania, głównie dlatego, że „problem dotyczący modelu maszyny” nie jest zdefiniowany.

Chciałbym uzyskać przykład (jeśli to możliwe) nierozstrzygalnego problemu bez potrzeby korzystania z maszyny Turinga

Niech będzie klasą maszyn i pozwala używać jako kodu . Możemy zinterpretować również jako kod tej TM, a następnie zapytać, czy dane robi $\{M_i\}$ $i$ $M_i$ $i$ $i$ $M_i$ $i$ th halt TM? I ten problem o $M_i$ s jest nierozstrzygalny.

Język jest tylko zbiorem ciągów, a interpretacja przypisywana ciągom nie ma wpływu na rozstrzygalność języka. O ile formalnie nie zdefiniujesz, co masz na myśli przez model maszyny i problem dotyczący tych maszyn, na twoje późniejsze pytania nie będzie można odpowiedzieć.

Czy Turing jest kompletną maszyną do obsługi nierozstrzygniętego problemu?

Ponownie obowiązuje punkt, o którym wspomniałem powyżej. Bardziej rozsądnym pytaniem byłoby: czy wszystkie dowody nierozstrzygalności przechodzą przez coś podobnego do nierozstrzygalności problemu zatrzymania dla baz TM? (Odpowiedź brzmi: są inne sposoby).

Innym możliwym pytaniem jest: jaki jest najmniejszy podzbiór baz TM, w którym problem zatrzymania jest dla nich nierozstrzygalny. Oczywiście taka klasa powinna zawierać problemy, które się nie zatrzymują (w przeciwnym razie problem można w prosty sposób rozstrzygnąć). Możemy łatwo tworzyć sztuczne podzbiory baz TM, w których problem zatrzymania nie jest rozstrzygalny bez możliwości obliczenia czegokolwiek przydatnego. Bardziej interesujące pytanie dotyczy dużych rozstrzygalnych zestawów baz TM, w których decyduje o nich zatrzymanie.

Oto kolejna kwestia: gdy tylko będziesz mieć bardzo małą zdolność do manipulowania bitami (np. Wielomianowy rozmiar ), możesz stworzyć maszynę z trzema wejściami: , i tak że wyprowadza 1 iff jest a wstrzymanie przyjmowania obliczeń TM na wejściu . Następnie możesz zadać pytania, takie jak: czy istnieje st wynosi 1? co jest nierozstrzygalnym problemem. $\mathsf{CNF}$ $N$ $e$ $x$ $c$ $c$ $M_e$ $x$ $c$ $N(e,x,c)$

— Kaveh
źródło

5

Istnieje bardzo prosty nierozstrzygalny problem dla automatów skończonych. Podziel alfabet na dwie połowy , przy czym litery są „przedawnionymi” kopiami. Teraz, biorąc pod uwagę automat skończony nad zdecyduj, czy akceptuje ciąg taki, że część bez zakazy równa się części z zakratowaniem (jeśli zignorujemy paski). Np. Napis będzie w porządku (obie części przeliterują $\Sigma \cup \bar\Sigma$ $\bar\Sigma$ $A$ $\Sigma\cup\bar\Sigma$ $a a \bar a \bar a b\bar b \bar aa$ $aaba$ ).

Tak, to jest problem korespondencyjny ukryty w automacie skończonym. Kompletność Turinga nie jest w tym pytaniu oczywista. Jest tam, w tle, gdy dwie kopie (bez ograniczeń i z zakazem) razem kodują kolejkę, która sama w sobie ma moc Turinga.

— Hendrik Jan
źródło

masz na to ref? nie jest od razu oczywiste, jak przekonwertować PCP na to. fyi są też nierozstrzygalne problemy z „przetwornikami” FSM.

— vzn

1

(u_{1}, \dots, u_{n})

$(u_1,\dots,u_n)$

(v_{1}, \dots, v_{n})

$(v_1,\dots,v_n)$

{u_{1} {\bar{v}}_{1}, \dots, u_{n} {\bar{v}}_{n}}^{+}

$\{ u_1\bar v_1, \dots, u_n\bar v_n \}^+$

\bar{v}

$\bar v$

v

$v$

3

„Czy można zbudować nierozstrzygalny problem dla automatu słabszego niż maszyna Turinga?”

Tak. Automat jest konsekwentnym aksjomatycznym sformułowaniem teorii liczb (np. Patrz (1) ), dlatego też według pierwszego twierdzenia Gödela o niepełności musi zawierać zdania nierozstrzygalne.

Przykład:

Każdy problem nierozstrzygalny dla TM jest również nierozstrzygalny dla każdego automatu, który TM może symulować. Dlaczego? Ponieważ jeśli automat, który jest mniej wydajny niż TM, może zadecydować o języku, którego nie może zdecydować TM, TM powinna być w stanie zdecydować o tym, symulując automat za pomocą sprzeczności.

— Amelio Vazquez-Reina
źródło

2

Pytanie, czy LBA zatrzymuje się, jest również rozstrzygalne dla TM, więc nie było to częścią przykładów, które podałem w mojej odpowiedzi. Każdy problem nierozstrzygalny dla TM jest również nierozstrzygalny dla LBA.

— Amelio Vazquez-Reina,

1

Drugie zdanie jest fałszywe dla każdej interpretacji, ponieważ problem zatrzymania jest rekurencyjny dla LBA, ale nie dla TM. W przypadku baz TM jest to rekurencyjnie wyliczalne, a jeśli chcesz rozszerzyć terminologię i nazwać oba „rozstrzygalne”, to weź pod uwagę problem wstrzymania dla obu - rekurencyjny dla LBA, ale nawet rekurencyjnie wymienny dla TM. Jeśli chodzi o pierwsze zdanie, wszystko, co „nieskonstruowane” dla automatów skończonych jest rekurencyjne. Zawsze możemy użyć „Czy to FSA akceptuje dokładnie

{T | T M T h a l t s o n i n p u t T}

$\{T|TM T halts on input T\}$ co oczywiście nie jest rozstrzygalne, ale jest wymyślone. Można to prawdopodobnie sformalizować.

— David Lewis,

1

@roseck - najpierw poprawka:

{T | TM T (T) halts}

$\{T|\text{ TM } T(T) \text{ halts}\}$ . Po drugie, jestem dość zdezorientowany twoim stwierdzeniem i odpowiedzią - żaden z twoich linków nie uzasadnia wyświetlanych oświadczeń; oba są artykułami ogólnymi.

— David Lewis,

1

@DavidLewis roseck nie twierdzi, że nierozstrzygalny problem dotyczący baz TM jest nadal nierozstrzygalny, jeśli zinterpretujesz go jako związany z LBA. roseck po prostu stwierdza, że jeśli nie jest to problem, który nie może zostać podjęta decyzja o bazach wtedy identyczny problem bez reinterpretacji również nie może być określana przez cokolwiek TM może symulować. Problem zatrzymywania TM i zatrzymywania LBA to dwa różne problemy.

— Ben

1

@Ben -- if so, then "...undecidable for any automaton that..." would have to be "by". But that is a trivial statement.

— David Lewis

1

Emil Post wanted to find the answer to exactly this question: Is there a non-recursive (non-computable) set which does not solve the halting problem. He succeeded only in part, but what he did, was create what is called simple sets.

From Wikipedia:

Podzbiór naturali nazywany jest prostym, jeśli jest nieskończony i rekurencyjnie wyliczalny, ale każdy nieskończony podzbiór jego dopełniacza nie jest wyliczany rekurencyjnie. Proste zestawy są przykładami zestawów rekurencyjnie wyliczalnych, które nie są rekurencyjne. Przeczytaj artykuł w Wikipedii, aby uzyskać więcej informacji i referencje, prosty zestaw .

— Pål GD
źródło